package sort

fun heapify(a: IntArray, i: Int, size: Int){ //从a[i]向下进行堆调整

var left_child = 2*i+1 //左孩子索引

var right_child = 2*i+2 //右孩子索引

var max = i //选出当前结点与其左右孩子三者之中的最大值

if (left_child < size && a[left_child] > a[max])

max = left_child

if (right_child < size && a[right_child] > a[max])

max = right_child

if (max != i){

swap(a,i,max) //把当前结点和它的最大(直接)子节点进行交换

heapify(a,max,size) //递归调用，继续从当前结点向下进行堆调整

}

}

fun buildHeap(a: IntArray, n: Int): Int{ //建堆

var heap_size = n

for (i in heap_size /2 -1 downTo 0){ //从每一个非叶结点开始向下进行堆调整

heapify(a,i,heap_size)

}

return heap_size

}

fun heapSort(a: IntArray,n: Int){

var heap_size = buildHeap(a,n) //建立一个最大堆

while (heap_size > 1){ //堆(无序号)元素个数大于1，未完成排序

//将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素

//此处交换操作很有可能把后面元素的稳定性打乱，所以堆排序是不稳定的排序算法

swap(a,0,--heap_size)

heapify(a,0,heap_size) //从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn)

}

}

fun main(args: Array<String>) {

val array: IntArray = intArrayOf(3,5,1,8,6,6,9,8,7,6,2)

val n: Int = array.size

heapSort(array,n)

println("堆排序结果:")

for (i in 0 until n){

print(array[i].toString() + ",")

}

}