heap

Куча (Heap)

Предпосылки: оценка сложности в O(…), бинарное дерево (left/right, лист, внутренний узел, полнота), BST (поддерживает полный порядок, в худшем случае вырождается до O(n)), абстрактный тип данных, массив (индексация, формула адреса), указатели/ссылки, базовое чтение Ruby (методы, блоки, массивы и хеши).

← Бинарное дерево

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

BST умеет и то, и другое, но платит за лишнее: он держит полный порядок между всеми элементами, а планировщику весь порядок не нужен — нужен только экстремум, наибольший элемент. К тому же BST в худшем случае вырождается в цепочку, и обе операции деградируют до O(n). Структура, которая держит на виду только максимум и за это гарантирует O(log n) без риска вырождения, называется кучей.

Heap: память против структуры данных

Слово «heap» в программировании встречается в двух несвязанных смыслах. Heap в контексте памяти — область, откуда программа берёт место под данные, размер которых известен только во время работы (в противоположность стеку вызовов). Heap как структура данных — бинарное дерево с особым правилом расположения значений, о котором эта заметка. Общего между ними — только название.

Два свойства кучи

Куче нужно держать максимум на известном месте, чтобы извлекать его мгновенно. Самое удобное известное место — корень дерева. Чтобы максимум всегда оказывался именно там, достаточно одного локального правила.

Свойство кучи (heap property): каждый родитель не меньше своих детей. Если это выполнено в каждом узле, то корень не меньше своих детей, те — не меньше своих, и так далее: наибольший элемент всплывает к корню сам собой. Такую кучу называют max-heap — на вершине максимум. Зеркальное правило «родитель не больше детей» даёт min-heap, где на вершине минимум; всё дальнейшее симметрично, поэтому разбираем max-heap.

Заметим, чего правило не требует: между соседними поддеревьями порядка нет, левый ребёнок может быть и больше, и меньше правого. Это и есть та экономия по сравнению с BST — куча поддерживает ровно столько порядка, сколько нужно для быстрого доступа к экстремуму, и ни каплей больше.

Второе правило задаёт форму дерева.

Свойство формы (shape property): дерево завершённое — все уровни заполнены, кроме последнего, который заполняется слева направо, без дыр.

Зачем такая жёсткая форма? Завершённое дерево из n узлов всегда имеет высоту ≈ log₂(n) (почему именно log₂) — то есть глубина, на которую придётся опускаться при операциях, остаётся логарифмической независимо от порядка вставок. Вырождаться в цепочку, как BST, такому дереву просто негде. И раз дыр в заполнении нет, дерево укладывается в массив подряд, уровень за уровнем, — хранить отдельные узлы и связи-указатели между ними не нужно:

        90              Массив: [90, 60, 70, 30, 40, 50]
       /  \             Индекс:   0   1   2   3   4   5
      60   70
     / \   /
    30 40 50

Раз связей нет, переход «родитель ↔ ребёнок» — это арифметика над индексами. Для узла в ячейке parent его дети лежат в parent * 2 + 1 и parent * 2 + 2, а родитель ребёнка из ячейки child — в (child - 1) / 2 (деление целочисленное, дробная часть отбрасывается):

left_child  = parent * 2 + 1
right_child = parent * 2 + 2
parent      = floor((child - 1) / 2)

Операции

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

Вставка («всплытие», sift up): новый элемент кладём в конец массива. Конец массива — это первая свободная ячейка последнего уровня слева направо, то есть ровно то место, куда завершённое дерево растёт следующим, — форма не нарушается. Но новичок может оказаться больше своего родителя. Пока это так, меняем его с родителем местами: элемент «всплывает» вверх, пока не упрётся в родителя не меньше себя или не станет корнем. Путь от листа к корню — это высота дерева, значит O(log n).

Вставляем 95:
[90, 60, 70, 30, 40, 50, 95]     95 > 70 (родитель) -> обмен
[90, 60, 95, 30, 40, 50, 70]     95 > 90 (родитель) -> обмен
[95, 60, 90, 30, 40, 50, 70]     95 — корень, стоп
 
        95
       /  \
      60   90
     / \   / \
    30 40 50 70

Извлечение максимума («погружение», sift down): максимум лежит в корне, его и возвращаем. Но просто убрать корень нельзя — образуется дыра в форме. Поэтому дыру закрывают последним элементом массива (он на краю формы, его изъятие форму не ломает): переносим его на место корня. Теперь свойство кучи нарушено сверху: бывший последний элемент, как правило, меньше своих новых детей. Пока он меньше большего из детей, меняем его с этим бо́льшим ребёнком. Почему именно с бо́льшим: после обмена этот ребёнок становится новым родителем и должен оказаться не меньше второго ребёнка — гарантировать это может только наибольший из двух. Элемент «тонет» вниз, пока не станет не меньше обоих детей либо не достигнет узла без детей. Снова путь высотой дерева — O(log n).

Извлекаем 95, ставим 70 на его место:
[70, 60, 90, 30, 40, 50]         70 < 90 (больший ребёнок) -> обмен
[90, 60, 70, 30, 40, 50]         у 70 один ребёнок, 50; 70 > 50 -> стоп
 
        90
       /  \
      60   70
     / \   /
    30 40 50

Остановка наступает, когда у элемента нет детей больше него — либо детей вовсе не осталось (как у 70 во втором шаге был лишь один ребёнок 50, и тот меньше), либо оба ребёнка не больше.

Просмотр максимума (peek): максимум всегда в корне, поэтому узнать его, не извлекая, стоит O(1) — просто читаем нулевую ячейку. Эта операция бесплатна именно потому, что свойство кучи держит экстремум на фиксированном месте; ради неё куча и строилась.

Сравнение с другими структурами

Для планировщика с 1000 процессов высота кучи ≈ log₂(1000) ≈ 10, и вставка с извлечением проходят примерно по 10 уровней — около 10 сравнений «родитель против ребёнка» на операцию. Насколько это хорошо рядом с альтернативами?

Структура	Добавить	Извлечь макс.
Неотсорт. массив	O(1)	O(n)
Отсорт. массив	O(n)	O(1)
BST (средний)	O(log n)	O(log n)
BST (худший)	O(n)	O(n)
Куча	O(log n)	O(log n)

Неотсортированный массив дёшев на вставку, но извлечение максимума требует просмотра всех элементов; отсортированный — наоборот. BST сбалансирован обе операции делает за O(log n), но вырожденный скатывается к O(n). Куча — единственная строка без слабого места: гарантированный O(log n) на обе операции, без риска вырождения, потому что свойство формы не даёт дереву превратиться в цепочку.

Построение кучи из готового массива

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

Листья (узлы без детей) трогать незачем — у одиночного узла нарушать нечего, свойство кучи на нём выполнено само собой. А листья занимают примерно половину завершённого дерева: его нижний уровень. Значит работать нужно только с внутренними узлами (теми, у кого есть дети) — это верхняя половина массива, и последний из них стоит в ячейке n/2 − 1 (всё, что правее, — листья). Идём от него к корню, на каждом узле делаем погружение.

Полная сложность здесь не O(n log n), а O(n). Узлы близко ко дну (а их большинство) погружаются на 0–1 уровень; лишь немногие узлы у вершины проходят все log n уровней. Сумма этих коротких путей по всему дереву складывается в O(n), а не в O(n log n): дорогих длинных погружений слишком мало, чтобы определять итог.

Heapsort: сортировка через кучу

Куча даёт почти готовый алгоритм сортировки. Построить max-heap из массива стоит O(n); дальше n раз извлекаем максимум за O(log n) каждый — элементы выходят по убыванию. Итого O(n log n).

Сортировка получается на месте, без дополнительной памяти под второй массив, и это та же арифметика индексов, что и в извлечении. При каждом извлечении куча отдаёт одну ячейку с конца (последний элемент уехал наверх), и именно туда — в освободившийся хвост — кладётся извлечённый максимум. Граница между «кучей» и «уже отсортированным хвостом» сдвигается на один шаг влево за извлечение:

[95 90 70 60 40 50 30]  куча из 7; извлекаем 95 -> в хвост
[90 ... 60 ...      | 95]  куча из 6, 95 на месте 7
[70 ...            | 90 95] куча из 5, отсортированный хвост растёт
 ...
[30 | 40 50 60 70 90 95]  куча из 1, весь хвост отсортирован

Когда куча сжимается до одного элемента, весь массив отсортирован по возрастанию — а второго массива не понадобилось.

Приоритетная очередь

Heapsort применяет кучу разово, для сортировки. Но чаще куча нужна как постоянное хранилище — реализация приоритетной очереди. Приоритетная очередь — это абстрактный тип данных: набор операций без указания, как они устроены внутри. Её операции — добавить элемент с приоритетом и извлечь элемент с наивысшим приоритетом. Тип данных описывает, что делает структура; куча отвечает на как — и отвечает эффективно, ровно теми вставкой и извлечением за O(log n), что разобраны выше. Max-heap годится, когда выше приоритет = больше число; min-heap — когда выше приоритет = меньше число.

Планировщик ОС, с которого началась эта задача, и есть приоритетная очередь: процессы поступают с разными приоритетами, планировщик извлекает наиболее приоритетный. Та же абстракция всплывает там, где из растущего набора постоянно нужен экстремум: в алгоритме Дейкстры (поиск кратчайших путей — на каждом шаге извлекается вершина с наименьшим известным расстоянием) и в event loop (цикл обработки событий — выбирается ближайший по времени таймер).

Реализация max-heap на Ruby

Хранилище — обычный массив; вся работа сводится к двум приватным методам, всплытию и погружению, поверх арифметики индексов из начала заметки.

class Heap
  def initialize
    @values = []
  end
 
  def peek
    @values[0]
  end
 
  def insert(value)
    @values << value     # в конец — следующая свободная позиция формы
    sift_up(@values.size - 1)
  end
 
  def extract_max
    return nil if @values.empty?
 
    maximum = @values[0]
    last = @values.pop
    unless @values.empty?
      @values[0] = last    # дыру в корне закрываем последним элементом
      sift_down(0)
    end
    maximum
  end
 
  private
 
  def sift_up(i)
    while i > 0
      parent = (i - 1) / 2
      break if @values[parent] >= @values[i]
      @values[i], @values[parent] = @values[parent], @values[i]
      i = parent
    end
  end
 
  def sift_down(i)
    size = @values.size
    loop do
      left  = i * 2 + 1
      right = i * 2 + 2
      largest = i
      largest = left  if left  < size && @values[left]  > @values[largest]
      largest = right if right < size && @values[right] > @values[largest]
      break if largest == i
      @values[i], @values[largest] = @values[largest], @values[i]
      i = largest
    end
  end
end

Для min-heap достаточно перевернуть сравнения: во всплытии менять местами, пока родитель больше ребёнка, а в погружении выбирать меньшего ребёнка и обменивать, пока родитель больше него.

Дубликаты

В отличие от BST, где для равных значений приходится отдельно выбирать правило «налево или направо», куча допускает дубликаты сама собой. Свойство «родитель не меньше детей» выполняется и при равенстве (50 ≥ 50), так что одинаковые приоритеты просто сосуществуют на соседних уровнях. При извлечении обе копии выйдут по очереди.

Sources

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed. (binary heap, build-heap за O(n), heapsort, priority queue).

---

← Бинарное дерево