pyramid-sort-subheap-approach

fun <T : Any> Array<T>.pyramidSort(comparator: Comparator<T>) {
    // Построение дочерних куч, начиная с последнего элемента, который является родителем
    for (i in size / 2 - 1 downTo 0) {
        subHeap(i, size, comparator)
    }
    // здесь массив стал бинарной кучей, где наибольший элемент находится на [0]
    for (i in size - 1 downTo 0) {
        swap(0, i)
        // формируется дочерняя куча без последнего элемента
        subHeap(0, i, comparator)
    }
}

fun <T : Any> Array<T>.subHeap(parentIndex: Int, n: Int, comparator: Comparator<T>) {
    var largestIndex = parentIndex
    val leftChildIndex = 2 * parentIndex + 1
    val rightChildIndex = 2 * parentIndex + 2

    if (leftChildIndex < n && comparator.compare(this[leftChildIndex], this[largestIndex]) > 0) {
        largestIndex = leftChildIndex
    }
    if (rightChildIndex < n && comparator.compare(this[rightChildIndex], this[largestIndex]) > 0) {
        largestIndex = rightChildIndex
    }

    if (largestIndex > parentIndex) {
        swap(parentIndex, largestIndex)
        subHeap(largestIndex, n, comparator)
    }
}

private fun <T: Any> Array<T>.swap(left: Int, right: Int) {
    val temp = this[right]
    this[right] = this[left]
    this[left] = temp
}

/**
 * Представление стажёра.
 */
data class Intern (
    val name: String,
    val taskCount: Int,
    val penalty: Int
)

fun main() {
    val reader = System.`in`.bufferedReader()
    val writer = System.out.bufferedWriter()
    val count = reader.readLine().toInt()

    val comparator = compareByDescending<Intern> { it.taskCount }
        .thenBy { it.penalty }
        .thenBy { it.name }

    val array = Array(count) {
        val (name, taskCount, penalty) = reader.readLine().split(" ")
        Intern(name, taskCount.toInt(), penalty.toInt())
    }
    array.pyramidSort(comparator)

    with(writer) {
        array.forEach {
            println(it.name)
        }
        flush()
    }
}