Двоичная куча

Двоичная куча

Двои́чная ку́ча, пирами́да, или сортиру́ющее де́рево — такое двоичное дерево, для которого выполнены три условия:

1. Значение в любой вершине не меньше, чем значения её потомков.
2. Глубина всех листьев (расстояние до корня) различается не более чем на 1 слой.
3. Последний слой заполняется слева направо без «дырок».

Существуют также кучи, где значение в любой вершине, наоборот, не больше, чем значения её потомков. Такие кучи называются min-heap, а кучи, описанные выше — max-heap. В дальнейшем рассматриваются только max-heap. Все действия с min-heap осуществляются аналогично.

структура данных для хранения двоичной кучи

Удобная структура данных для сортирующего дерева — массив A, у которого первый элемент, A[1] — элемент в корне, а потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого). При нумерации элементов с нулевого, корневой элемент — A[0], а потомки элемента A[i] — A[2i+1] и A[2i+2]. При таком способе хранения условия 2 и 3 выполнены автоматически.

Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть $\Theta \left(\log {N}\right)$, где N — количество узлов дерева.

Функциональность

Над кучей можно выполнять следующие операции:

• Добавить элемент в кучу. Сложность $O(\log {n})$
• Исключить максимальный элемент из кучи. Время работы $O(\log {n})$
• Изменить значение любого элемента. Время работы $O(\log {n})$

На основе этих операций можно выполнять следующие действия:

• Превратить неупорядоченный массив элементов в кучу. Сложность $O(n)$
• Отсортировать массив путём превращения его в кучу, а кучу в отсортированный массив. Время работы $O(n\log {n})$

Здесь $n$ — количество элементов кучи. Пространственная сложность — $O(1)$ для всех вышеперечисленных операций и действий.

Подробное описание и алгоритмы этих действий и процедуры Heapify, необходимой для их выполнения, приведены в следующем разделе.

Базовые процедуры

В этом разделе представлены основные процедуры для работы с кучей.

Восстановление свойств кучи

Если в куче изменяется один из элементов, то она может перестать удовлетворять свойству упорядоченности. Для восстановления этого свойства служит процедура Heapify. Она восстанавливает свойство кучи в дереве, у которого левое и правое поддеревья удовлетворяют ему. Эта процедура принимает на вход массив элементов A и индекс i. Она восстанавливает свойство упорядоченности во всём поддереве, корнем которого является элемент A[i].

Если i-й элемент больше, чем его сыновья, всё поддерево уже является кучей, и делать ничего не надо. В противном случае меняем местами i-й элемент с наибольшим из его сыновей, после чего выполняем Heapify для этого сына.

Процедура выполняется за время $O\left(\log {n}\right)$.

Heapify(A, i)
  left ← 2i
  right ← 2i+1
  heap_size - количество элементов в куче
  largest ← i
  if left ≤ A.heap_size и A[left] > A[largest]
    then largest ← left
  if right ≤ A.heap_size и A[right] > A[largest]
    then largest ← right
  if largest ≠ i
    then Обменять A[i] ↔ A[largest]
         Heapify(A, largest)

Для языков, не поддерживающих автоматическую оптимизацию хвостовой рекурсии, можно повысить эффективность реализации, если избавиться от рекурсии.

Построение кучи

Эта процедура предназначена для создания кучи из неупорядоченного массива входных данных.

Заметим, что если выполнить Heapify для всех элементов массива A, начиная с последнего и кончая первым, он станет кучей. В самом деле, легко доказать по индукции, что к моменту выполнения Heapify(A, i) все поддеревья, чьи корни имеют индекс больше i, - кучи, и, следовательно, после выполнения Heapify(A, i) кучей будут все поддеревья, чьи корни имеют индекс, не меньший i.

Кроме того, Heapify(A,i) не делает ничего, если i>N/2 (при нумерации с первого элемента), где N — количество элементов массива. В самом деле, у таких элементов нет потомков, следовательно, соответствующие поддеревья уже являются кучами, так как содержат всего один элемент.

Таким образом, достаточно вызвать Heapify для всех элементов массива A, начиная (при нумерации с первого элемента) с $[N/2]$-го и кончая первым.

Build_Heap(A)
  A.heap_size ← A.length
  for i ← ⌊A.length/2⌋ downto 1
    do Heapify(A, i)

И хотя здесь происходит n/2 вызовов функции Heapify со сложностью $O\left(\log {n}\right)$, можно показать, что время работы равно $O(n)$.

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

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

Процедура Heapsort сортирует массив без привлечения дополнительной памяти за время $O\left(n\log {n}\right)$.

Для понимания её работы можно представить, что мы обменяли первый элемент (то есть корень) с последним. Тогда последний элемент станет самым большим. Если после этого исключить последний элемент из кучи (то есть формально уменьшить её длину на 1), первые N-1 элементов будут удовлетворять условиям кучи все, за исключением, может быть, корня. Если вызвать Heapify, первые N-1 элементов станут кучей, а последний будет больше их всех. Повторяя эти действия N-1 раз, мы отсортируем массив.

Heapsort(A)
  Build_Heap(A)
  for i ← A.length downto 1
    do Обменять A[1] ↔ A[i]
       A.heap_size ← A.heap_size-1
       Heapify(A,1)

Изменение значения элемента

Процедура Heap_Increase_Key заменяет элемент кучи на новый ключ со значением, не меньшим значения исходного элемента. Обычно эта процедура используется для добавления произвольного элемента в кучу. Временная сложность $O\left(\log {n}\right)$.

Если элемент меньше своего отца, условие 1 соблюдено для всего дерева, и больше ничего делать не нужно. Если он больше, мы меняем местами его с отцом. Если после этого отец больше деда, мы меняем местами отца с дедом и так далее. Иными словами, слишком большой элемент всплывает наверх.

Heap_Increase_Key(A, i, key)
  if key < A[i]
    then error "Новый ключ меньше предыдущего"
  A[i] ← key
  while i > 1 и A[⌊i/2⌋] < A[i]
    do Обменять A[i] ↔ A[⌊i/2⌋]
      i ← ⌊i/2⌋

В случае, когда необходимо уменьшить значение элемента, можно вызвать Heapify.

Добавление элемента

Выполняет добавление элемента в кучу за время $O\left(\log {n}\right)$.

Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью Heap_Increase_Key.

Heap_Insert(A, key)
  A.heap_size ← A.heap_size+1
  A[A.heap_size] ← -∞
  Heap_Increase_Key(A, A.heap_size, key)

Извлечение максимального элемента

Выполняет извлечение максимального элемента из кучи за время $O\left(\log {n}\right)$.

Извлечение выполняется в четыре этапа:

• значение корневого элемента (он и является максимальным) сохраняется для последующего возврата
• последний элемент копируется в корень, после чего удаляется из кучи
• вызывается Heapify для корня
• сохранённый элемент возвращается

Heap_Extract_Max(A)
  if A.heap_size[A] < 1
    then error "Куча пуста"
  max ← A[1]
  A[1] ← A[A.heap_size]
  A.heap_size ← A.heap_size-1
  Heapify(A, 1)
  return max

См. также

• Очередь с приоритетом
• Фибоначчиева куча
• Биномиальная куча