object HeapSort:SortInterface {
    override fun <T : Comparable<T>> sort(arr: Array<T>) {
        for (i in arr.size / 2 downTo 0) {
            maxHeapify(arr, i)
        }
        for (i in arr.size - 1 downTo 1) {
            val tempMax = arr[0]
            arr[0] = arr[i]
            arr[i] = tempMax
            maxHeapifyWithRange(arr,0,i-1)
        }
    }

    private fun <T : Comparable<T>> maxHeapify(arr: Array<T>, i: Int) {
        var largest = if (i.left() < arr.size && arr[i.left()] > arr[i]) {
            i.left()
        } else {
            i
        }
        if (i.right() < arr.size && arr[i.right()] > arr[largest]) {
            largest = i.right()
        }
        if (largest != i) {
            val temp = arr[i]
            arr[i] = arr[largest]
            arr[largest] = temp
            maxHeapify(arr, largest)
        }
    }

    private fun <T : Comparable<T>> maxHeapifyWithRange(arr: Array<T>, i: Int, limit: Int) {
        var largest = if (i.left() <= limit && arr[i.left()] > arr[i]) {
            i.left()
        } else {
            i
        }
        if (i.right() <= limit && arr[i.right()] > arr[largest]) {
            largest = i.right()
        }
        if (largest != i) {
            val temp = arr[i]
            arr[i] = arr[largest]
            arr[largest] = temp
            maxHeapifyWithRange(arr, largest, limit)
        }
    }

    val left = fun Int.(): Int = 2 * this
    val right = fun Int.(): Int = 2 * this + 1
}