Очередь с приоритетами: контракт и вставка в кучу

Если ты отличаешь контракт очереди с приоритетами от его реализаций, уверенно пишешь просеивание вверх и знаешь, почему оно вдвое дешевле просеивания вниз, листай до «Теперь сам».

Как думаешь, зачем разделять очередь и кучу

Прежде чем читать дальше, ответь: зачем вообще нужны два слова - «очередь с приоритетами» и «двоичная куча», - если на практике вторая почти всегда реализует первую? Подсказка: в следующей главе появятся биномиальная куча и куча Фибоначчи, а в разделе про графы - алгоритм Дейкстры, который формулируется через контракт и работает с любой реализацией, меняя лишь итоговую оценку времени. Разделение отделяет «что мне нужно» от «чем я за это плачу».

На что это похоже

Регистратура и способ хранения карточек. Регистратура обещает: принять пациента и вызвать самого срочного. Это контракт - его видит пациент. Как именно карточки лежат внутри (стопкой, в картотеке по алфавиту, в хитром шкафу), дело регистратуры, и от этого зависит только скорость. Заменят шкаф - обещание не изменится. И наоборот: если пациент попросит «найдите мою карточку и поменяйте в ней срочность», выяснится, что обещание такого не включало и шкаф под такую просьбу не приспособлен.

Механизм: контракт, его цена и просеивание вверх

push(x)      - положить элемент               O(log n)
peek()       - посмотреть экстремум           O(1)
pop()        - забрать экстремум              O(log n)
build(a)     - собрать очередь из массива     O(n)
size(), empty()                               O(1)

Вставка - единственная операция кучи, которой не было в сортировке (там кучу строили целиком и только разбирали). Работает она зеркально просеиванию вниз:

push(x):
    a.append(x)                    # в конец: дерево остаётся полным, без дыр
    i = len(a) - 1
    пока i > 0 и a[(i-1)//2] < a[i]:
        поменять a[i] и a[(i-1)//2]
        i = (i-1)//2               # поднялись к родителю

Почему именно в конец, а не на «подходящее место»: полное дерево заполнено по уровням слева направо без дыр, и единственная позиция, куда можно добавить узел, не порвав форму, - следующая свободная ячейка массива. Форму чинить нечем, её сохраняют по построению; а порядок потом восстанавливают обменами вдоль одного пути.

Правило

Очередь с приоритетами - контракт (push, peek, pop экстремума); двоичная куча - его реализация ценой O(log n) / O(1) / O(log n) и построением O(n). Вставка кладёт элемент в конец массива и просеивает ВВЕРХ, пока он больше родителя: не больше ⌊log₂ n⌋ обменов и ОДНО сравнение на уровень (против двух при просеивании вниз). Куча не ищет по ключу, не обходит по порядку и не сливается дёшево - в контракте этого нет.

Разбор: вставляем 50 и считаем работу

Куча [42, 28, 35, 14, 22, 9, 31]. Добавляем 50.

1. В конец: [42, 28, 35, 14, 22, 9, 31, 50], индекс нового элемента i = 7.
2. Родитель (7−1)//2 = 3, там 14. Сравнение 1: 14 < 50 - обмен. Массив: [42, 28, 35, 50, 22, 9, 31, 14], i = 3.
3. Родитель (3−1)//2 = 1, там 28. Сравнение 2: 28 < 50 - обмен. Массив: [42, 50, 35, 28, 22, 9, 31, 14], i = 1.
4. Родитель (1−1)//2 = 0, там 42. Сравнение 3: 42 < 50 - обмен. Массив: [50, 42, 35, 28, 22, 9, 31, 14], i = 0. Корень, стоп.

Три сравнения, три обмена. Заметь, чего НЕ произошло: числа 9, 31, 22 не сдвинулись и даже не участвовали в сравнениях - им безразлично, кто наверху. В отсортированном по убыванию массиве 50 встало бы в самое начало и сдвинуло ВСЕ семь элементов; здесь работа идёт вдоль одного пути длиной ⌊log₂ 8⌋ = 3.

Разбор: почему вверх дешевле, чем вниз

Обе операции идут по одному пути и обе O(log n), но константа у них разная. При просеивании ВВЕРХ на каждом уровне одно сравнение: элемент против родителя, второго кандидата нет. При просеивании ВНИЗ сравнений два: сначала левый ребёнок против правого (кто больше), затем победитель против родителя. Итого log₂ n против 2·log₂ n.

Вторая разница - в типичной длине пути, и она перевешивает первую. Элемент, вставляемый в случайном порядке, почти наверняка остановится через шаг-другой: чтобы подняться на k уровней, надо оказаться больше k своих предков, то есть быть наибольшим среди всех элементов своего пути; при случайном порядке вставок шанс на это падает примерно вдвое с каждым уровнем, а сумма 1/2 + 1/4 + 1/8 + ... даёт в среднем меньше двух обменов на вставку. Поэтому n случайных вставок обходятся примерно в O(n), хотя каждая по отдельности оценивается как O(log n). А при извлечении наоборот: в корень мы ставим ПОСЛЕДНИЙ элемент - он лежал у самого дна и потому, скорее всего, мал, ему предстоит опуститься почти до низа. Худший случай для pop - не редкая неудача, а обычный ход дел. Отсюда практический вывод: очередь с преобладанием вставок дешевле, чем кажется по асимптотике, а очередь с преобладанием извлечений - ровно такая, как обещает оценка.

И отдельно про n ВОЗРАСТАЮЩИХ вставок (каждая новая больше всех предыдущих): тут каждый элемент всплывает до корня, и получаются честные Θ(n·log n). Именно поэтому, когда все данные уже есть, кучу строят целиком за O(n) (heapify), а не наполняют циклом из push.

Что ломается без этого

Первое: вставка «на подходящее место» в середину массива - дерево перестаёт быть полным, и арифметика индексов начинает указывать в пустоту. Второе: забытая остановка на i > 0 - при i = 0 формула (0−1)//2 в Python даёт −1, то есть последний элемент массива, и элемент начинает сравниваться сам с хвостом кучи; ошибка не падает, а тихо портит структуру. Третье: push в цикле вместо build на готовых данных - потеря линейности. Четвёртое: ожидание, что куча после вставок окажется отсортированной: [50, 42, 35, 28, 22, 9, 31, 14] - корректная куча, в которой 9 стоит перед 31. Пятое: pop на пустой очереди - самый частый источник падений в реальном коде, пустоту проверяют до чтения a[0].

Зачем это в работе

Контракт «дай самое срочное прямо сейчас» встречается чаще, чем кажется: планировщики задач и потоков, таймеры и колёса событий, очереди сообщений с приоритетами, A* и Дейкстра в навигации и в играх, слияние k отсортированных потоков (шарды базы, лог-файлы, внешняя сортировка), top-k по частоте в аналитике, сжатие Хаффмана. Полезная привычка при выборе структуры - задать себе два вопроса: какие операции мне ДЕЙСТВИТЕЛЬНО нужны (только экстремум или ещё поиск, слияние, изменение ключа) и сколько будет каждой. Нужен только экстремум - двоичная куча, и сложнее искать не надо. Нужны частые слияния или дешёвое уменьшение ключа - следующие два урока и следующая глава. В стандартных библиотеках контракт закрыт именно кучей: heapq в Python, PriorityQueue в Java, std::priority_queue в C++.

Теперь сам

В пустую max-кучу кладут по одному числа 10, 20, 5, 30. Выпиши массив после каждой вставки и посчитай обмены. Сколько обменов дало бы построение из готового массива [10, 20, 5, 30]?