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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Двоичная куча

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

  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 - количество элементов в куче
  largesti
  if leftA.heap_size и A[left] > A[i]
    then largestleft
  if rightA.heap_size и A[right] > A[largest]
    then largestright
  if largesti
    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]-го и кончая первым.

Время работы равно O \left( n \right).

Build-Heap(A)
  A.heap_sizeA.length
  for i ← ⌊A.length/2⌋ downto 1
    do Heapify(A, i)

Пирамидальная сортировка[править | править исходный текст]

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

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

Heapsort(A)
  Build_Max_Heap(A)
  for iA.length downto 1
    do Обменять A[1] ↔ A[i]
       A.heap_sizeA.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_sizeA.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 "Куча пуста"
  maxA[1]
  A[1] ← A[A.heap_size]
  A.heap_sizeA.heap_size-1
  Heapify(A, 1)
  return max

См. также[править | править исходный текст]

Ссылки[править | править исходный текст]

  1. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 178 - 193. — ISBN 5-8459-0857-4