fun buildHeap(array: MutableList<Int>, n: Int) {
    for (i in 1 until n) {
        var parentIndex = (i - 1) / 2
        var j = i
 
        while (j > 0 && array[j] > array[parentIndex]) {
            val tmp = array[j]
            array[j] = array[parentIndex]
            array[parentIndex] = tmp
            j = parentIndex
            parentIndex = (j - 1) / 2
        }
    }
}
 
 
fun heapSort(array: MutableList<Int>) {
    for (i in array.count() - 1 downTo 1) {
        buildHeap(array, i + 1)
        val tmp = array[0]
        array[0] = array[i]
        array[i] = tmp
    }
}
 
fun main() {
    val array = mutableListOf(7, 3, 0, 1, 5, 2, 5, 19, 10, 5)
 
    heapSort(array)
 
    println(array)
}

ZnVuIGJ1aWxkSGVhcChhcnJheTogTXV0YWJsZUxpc3Q8SW50PiwgbjogSW50KSB7CiAgICBmb3IgKGkgaW4gMSB1bnRpbCBuKSB7CiAgICAgICAgdmFyIHBhcmVudEluZGV4ID0gKGkgLSAxKSAvIDIKICAgICAgICB2YXIgaiA9IGkKICAgICAgICAKICAgICAgICB3aGlsZSAoaiA+IDAgJiYgYXJyYXlbal0gPiBhcnJheVtwYXJlbnRJbmRleF0pIHsKICAgICAgICAgICAgdmFsIHRtcCA9IGFycmF5W2pdCiAgICAgICAgICAgIGFycmF5W2pdID0gYXJyYXlbcGFyZW50SW5kZXhdCiAgICAgICAgICAgIGFycmF5W3BhcmVudEluZGV4XSA9IHRtcAogICAgICAgICAgICBqID0gcGFyZW50SW5kZXgKICAgICAgICAgICAgcGFyZW50SW5kZXggPSAoaiAtIDEpIC8gMgogICAgICAgIH0KICAgIH0KfQogICAgICAgICAgICAKCmZ1biBoZWFwU29ydChhcnJheTogTXV0YWJsZUxpc3Q8SW50PikgewogICAgZm9yIChpIGluIGFycmF5LmNvdW50KCkgLSAxIGRvd25UbyAxKSB7CiAgICAgICAgYnVpbGRIZWFwKGFycmF5LCBpICsgMSkKICAgICAgICB2YWwgdG1wID0gYXJyYXlbMF0KICAgICAgICBhcnJheVswXSA9IGFycmF5W2ldCiAgICAgICAgYXJyYXlbaV0gPSB0bXAKICAgIH0KfQoKZnVuIG1haW4oKSB7CiAgICB2YWwgYXJyYXkgPSBtdXRhYmxlTGlzdE9mKDcsIDMsIDAsIDEsIDUsIDIsIDUsIDE5LCAxMCwgNSkKCiAgICBoZWFwU29ydChhcnJheSkKCiAgICBwcmludGxuKGFycmF5KQp9