Часто нужна не полная сортировка, а всего одно: быстро доставать наибольший (или наименьший) элемент, снова и снова, добавляя по пути новые. Именно это делает приоритетная очередь. Эффективно её реализуют на структуре, которую называют пирамидой или кучей (heap).

Слабая упорядоченность

Пирамида — это двоичное дерево, но с гораздо более мягким правилом, чем дерево поиска. Условие всего одно: ключ любого узла не меньше ключей его потомков (для max-кучи). Это называют слабой упорядоченностью: наибольший элемент гарантированно наверху, в корне, а вот левый-правый порядок между узлами не задан — куча не отсортирована целиком.

Такое послабление — не недостаток, а точная подгонка под задачу. Нам нужен только максимум, и он всегда под рукой — в корне. Не тратя усилий на полный порядок, куча делает вставку и выемку максимума дешёвыми.

Ещё одно требование: пирамида — полное дерево, то есть заполнено по уровням слева направо без пропусков. Это важно для хранения.

Хранение в массиве

Красота пирамиды в том, что её не хранят как дерево из узлов со ссылками — её кладут в обычный массив, по уровням. И тогда родственные связи вычисляются арифметикой по индексу:

  • потомки узла i — это ячейки 2i+1 и 2i+2;
  • родитель узла i — ячейка (i-1)/2.

Никаких ссылок и объектов-узлов — просто массив и формулы. Это экономит память и ускоряет доступ.

Всплытие и погружение

Две операции поддерживают правило кучи.

Вставка (всплытие, trickle up). Новый элемент кладут в конец массива (первое свободное место) и «поднимают»: пока он больше своего родителя — меняют их местами. Элемент всплывает наверх, пока не встанет на своё место. Путь — от листа до корня, то есть высота дерева, O(log N).

Выемка максимума (погружение, trickle down). Максимум — в корне, его забирают. Дырку в корне закрывают последним элементом массива, а затем «опускают» его: пока он меньше большего из потомков — меняют местами с ним. Элемент погружается, пока правило не восстановится. Тоже O(log N).

Итог: и добавить элемент, и достать наибольший — по O(log N). Именно поэтому куча — стандартная начинка приоритетной очереди, а через неё — многих алгоритмов, например поиска кратчайшего пути.

Пирамидальная сортировка

Из кучи вырастает и полноценный алгоритм сортировки — пирамидальная сортировка (heapsort). Идея прямая: свалить все элементы в кучу, а потом по одному доставать максимум — они выйдут по убыванию. Каждая выемка — O(log N), всего элементов N, отсюда O(N·log N) — на уровне быстрой сортировки.

Ловкий приём делает heapsort ещё и сортировкой «на месте», без дополнительной памяти: и куча, и отсортированный результат живут в одном массиве. Сначала массив превращают в кучу, а затем на каждом шаге меняют местами корень (максимум) с последним элементом кучи и уменьшают её размер — вынутые максимумы накапливаются в хвосте массива уже по порядку. В отличие от быстрой сортировки, heapsort гарантирует O(N·log N) даже в худшем случае.

Коротко

  • Пирамида (куча) — полное двоичное дерево со слабой упорядоченностью: наибольший элемент в корне, но целиком дерево не отсортировано.
  • Её хранят в массиве; связи узлов вычисляются по индексу (2i+1, 2i+2, (i-1)/2) без ссылок.
  • Вставка (всплытие) и выемка максимума (погружение) — обе O(log N). Это эффективная основа приоритетной очереди.
  • Пирамидальная сортировка строит кучу и достаёт максимумы — O(N·log N), «на месте», с гарантией даже в худшем случае.

Дальше — графы: структура для моделирования связей — маршрутов, сетей, зависимостей — и алгоритмы их обхода.