Условие

Отсортируйте данный массив. Используйте пирамидальную сортировку.

Примеры

Ввод: 1 1 Вывод: 1

Ввод: 2 3 1 Вывод: 1 3

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun heapSort(arr: IntArray) {
    buildMaxHeap(arr) // Преобразуем массив в кучу
    for (i in arr.lastIndex downTo 1) {
        arr.swap(0, i) // Меняем корень (максимальный элемент) с последним
        heapify(arr, 0, i) // Восстанавливаем свойства кучи
    }
}

fun buildMaxHeap(arr: IntArray) {
    for (i in arr.size / 2 - 1 downTo 0) {
        heapify(arr, i, arr.size)
    }
}

fun heapify(arr: IntArray, index: Int, heapSize: Int) {
    var largest = index
    val left = 2 * index + 1
    val right = 2 * index + 2

    if (left < heapSize && arr[left] > arr[largest]) largest = left
    if (right < heapSize && arr[right] > arr[largest]) largest = right

    if (largest != index) {
        arr.swap(index, largest)
        heapify(arr, largest, heapSize)
    }
}

fun IntArray.swap(i: Int, j: Int) {
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    val n = reader.readLine().toInt()
    val arr = reader.readLine().split(" ").map(String::toInt).toIntArray()
    
    heapSort(arr) // Применяем пирамидальную сортировку
    
    writer.write(arr.joinToString(" "))
    reader.close()
    writer.close()
}