Куча и очередь приоритетов: выбирать следующий минимум

Обработчик выбирает самое срочное задание из тысяч ожидающих. Полная сортировка после каждого поступления делает лишнюю работу: нужен только лучший следующий элемент, а не порядок всего набора. Очередь приоритетов задаёт такой договор, а двоичная куча реализует его через частичный порядок.

Свойство кучи

В min-heap значение родителя не больше значений детей. Корень содержит минимум. Но элементы двух соседних поддеревьев могут располагаться в любом порядке. Срез кучи не обязан быть отсортирован целиком.

Полное двоичное дерево удобно хранить массивом. Для индекса i дети находятся на 2*i+1 и 2*i+2, родитель для i>0 — (i−1)/2. Полнота формы означает, что все уровни, кроме последнего, заполнены, а последний заполняется слева. Высота O(log n) получается из формы, а не из случайности ключей.

Добавление и извлечение

Новый элемент добавляется в конец и поднимается, пока меньше родителя. Нарушение могло возникнуть только на этом пути. Для удаления минимума переносим последний элемент в корень, сокращаем массив, затем опускаем корень к меньшему ребёнку. Выбор просто левого ребёнка не сохраняет свойство при меньшем правом.

Обе операции имеют O(log n) времени, чтение корня O(1). Построение кучи из массива снизу вверх стоит O(n): большинство узлов находятся близко к листьям и опускаются недалеко. Повторное добавление n элементов даёт более грубую O(n log n) границу.

Используем стандартный механизм правильно

В Go container/heap вызывает методы интерфейса вашего контейнера и выполняет восстановление свойства. Его метод Pop и операция heap.Pop — разные уровни. Пользовательский метод Pop удаляет последний элемент backing slice; библиотечная heap.Pop сначала переставляет корень и восстанавливает порядок.

// h реализует heap.Interface.
heap.Init(h)
heap.Push(h, 7)
minimum := heap.Pop(h).(int)

Полный тип с Len,Less,Swap,Push,Pop есть в reference/algorithms.go. Не заменяйте heap.Pop прямым вызовом собственного h.Pop: вы извлечёте последний элемент, а не минимум. Сравнение < делает min-heap; обратное сравнение выбирает максимум.

Сохраняем только k лучших

Для TopK крупнейших значений храните min-heap размером не больше k. Его корень — самый маленький среди пока отобранных. Если новый элемент не больше корня при полной куче, он не войдёт в k крупнейших. Иначе замените корень и восстановите свойство.

После просмотра префикса куча содержит k крупнейших элементов этого префикса либо все элементы, если их меньше k. Поиск на n входах стоит O(n log k) для k≥2, память O(k). При k=0 действий с кучей нет; при k=1 достаточно текущего максимума. Сортировка итогового ответа отдельно стоит O(k log k).

Самостоятельная лаборатория

Напишите TopK для целых значений. Договор: k от 0 доlen(a), повторы считаются отдельными элементами, ответ отсортирован по возрастанию, вход не изменяется. Для [5,1,9,9,3] и k=3 ответ [5,9,9]. Проверьте k=0,k=len(a), неправильный k и отрицательные значения.

Сравните результат с сортировкой копии входа и выбором последних k значений на случайных небольших массивах. Для собственного heap дополнительно проверяйте после каждого действия все отношения родитель≤ребёнок. Практика — 50 минут.

Критерии готовности: корень правильно выбран; размер ограничен k; кратность повторов сохранена; ответ не выдан за порядок внутри кучи; стоимость финальной сортировки учтена.

Разбор

Куча из [1,3,2] корректна, хотя срез не отсортирован. Это полезный контрпример к неверному тесту. Для k=3 на заданном входе min-heap постепенно исключит 1 и 3, оставив 5,9,9. Удаление случайной копии 9 недопустимо: TopK выбирает элементы с кратностью.

В дальнейшем куча станет способом выбора ближайшей ещё не обработанной вершины в алгоритме Дейкстры. Источники: Go: container/heap, Princeton: priority queues.