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

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

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

  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 выполнены автоматически.

Высота кучи определяется как высота двоичного дерева. То есть она равна количеству рёбер в самом длинном простом пути, соединяющем корень кучи с одним из её листьев. Высота кучи есть , где N — количество узлов дерева.

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

[править | править код]

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

  • Добавить элемент в кучу. Сложность
  • Исключить максимальный элемент из кучи. Время работы
  • Изменить значение любого элемента. Время работы

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

  • Превратить неупорядоченный массив элементов в кучу. Сложность
  • Отсортировать массив путём превращения его в кучу, а кучу в отсортированный массив. Время работы

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

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

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

[править | править код]

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

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

[править | править код]

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

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

Процедура выполняется за время .

Heapify(A, i)
  left ← 2i
  right ← 2i+1
  heap_size - количество элементов в куче
  largesti
  if leftA.heap_size и A[left] > A[largest]
    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, начиная (при нумерации с первого элемента) с -го и кончая первым.

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

И хотя здесь происходит n/2 вызовов функции Heapify со сложностью , можно показать, что время работы равно [1].

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

[править | править код]

Процедура Heapsort сортирует массив без привлечения дополнительной памяти за время .

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

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

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

[править | править код]

Процедура Heap_Increase_Key заменяет элемент кучи на новый ключ со значением, не меньшим значения исходного элемента. Обычно эта процедура используется для добавления произвольного элемента в кучу. Временная сложность .

Если элемент меньше своего отца, условие 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.

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

[править | править код]

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

Добавление произвольного элемента в конец кучи, и восстановление свойства упорядоченности с помощью 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)

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

[править | править код]

Выполняет извлечение максимального элемента из кучи за время .

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

  • значение корневого элемента (он и является максимальным) сохраняется для последующего возврата
  • последний элемент копируется в корень, после чего удаляется из кучи
  • вызывается 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. 1 2 Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 6. Пирамидальная сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 178 - 193. — ISBN 5-8459-0857-4.

Комментарии

[править | править код]
  1. Если задан противоположный порядок сортировки, то значение в любой вершине должно быть не больше, чем значения её потомков.