Условие

В этой задаче вам необходимо самостоятельно (не используя соответствующие классы и функции стандартной библиотеки) организовать структуру данных Heap для хранения целых чисел, над которой определены следующие операции:

a) Insert(k) – добавить в Heap число k ;

b) Extract достать из Heap наибольшее число (удалив его при этом).

Примеры

Ввод: 2 0 10000 1 Вывод: 10000

Ввод: 14 0 1 0 345 1 0 4346 1 0 2435 1 0 235 0 5 0 365 1 1 1 1 Вывод: 345 4346 2435 365 235 5 1

Решение

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

// Класс для реализации max-кучи
class MaxHeap {
    private val heap = mutableListOf<Int>() // Список для хранения элементов кучи

    // Добавление элемента в кучу
    fun insert(value: Int) {
        heap.add(value) // Добавляем элемент в конец
        siftUp(heap.size - 1) // Восстанавливаем свойства кучи
    }

    // Извлечение максимального элемента
    fun extract(): Int {
        if (heap.isEmpty()) throw NoSuchElementException("Heap is empty")
        val max = heap[0] // Максимальный элемент (корень кучи)
        if (heap.size == 1) {
            return heap.removeAt(0) // Если элемент один, просто удаляем его
        }
        heap[0] = heap.removeAt(heap.size - 1) // Перемещаем последний элемент наверх
        siftDown(0) // Восстанавливаем свойства кучи
        return max
    }

    // Просеивание вверх для восстановления свойств max-кучи
    private fun siftUp(index: Int) {
        var i = index
        while (i > 0) {
            val parent = (i - 1) / 2
            if (heap[i] <= heap[parent]) break // Если порядок верный, прерываем
            heap.swap(i, parent) // Меняем местами текущий элемент с родителем
            i = parent
        }
    }

    // Просеивание вниз для восстановления свойств max-кучи
    private fun siftDown(index: Int) {
        var i = index
        while (2 * i + 1 < heap.size) { // Пока у элемента есть потомки
            var largest = 2 * i + 1 // Левый потомок
            val right = 2 * i + 2 // Правый потомок
            if (right < heap.size && heap[right] > heap[largest]) largest = right // Выбираем большего
            if (heap[i] >= heap[largest]) break // Если порядок верный, прерываем
            heap.swap(i, largest) // Меняем местами
            i = largest
        }
    }

    // Функция для обмена двух элементов в списке
    private fun MutableList<Int>.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 heap = MaxHeap() // Создаём экземпляр max-кучи

    val n = reader.readLine().toInt() // Читаем количество команд
    repeat(n) {
        val command = reader.readLine().split(" ")
        if (command[0] == "0") {
            heap.insert(command[1].toInt()) // Добавляем элемент в кучу
        } else {
            writer.write("${heap.extract()}\\n") // Извлекаем максимальный элемент
        }
    }
    
    reader.close()
    writer.close()
}