Просмотр кода страницы Двоичная куча

{{Значения|Куча}}
{{wikibooks|Примеры реализации двоичной кучи}}
[[Файл:Сортирующее_дерево.svg|300px|right|thumb|Двоичная куча]]
'''Двои́чная ку́ча''', '''пирами́да'''<ref name=CLRS>{{Книга:CLRS|2005|часть = '''Глава 6. Пирамидальная сортировка'''|страницы = 178 - 193}}</ref>, или '''сортиру́ющее де́рево''' — такое [[двоичное дерево]], для которого выполнены три условия:
# Значение в любой вершине не меньше, чем значения её потомков<ref group=К>Если задан противоположный порядок сортировки, то значение в любой вершине должно быть ''не больше'', чем значения её потомков.</ref>.
# Глубина всех листьев (расстояние до корня) различается не более чем на 1 слой.
# Последний слой заполняется слева направо без «дырок».

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

[[Файл:Сортирующее дерево развернутое в массив.svg|400px|right|thumb|структура данных для хранения двоичной кучи]]

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

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

== Функциональность ==
Над кучей можно выполнять следующие операции:
* Добавить элемент в кучу. Сложность <math>O(\log{n})</math>
* Исключить максимальный элемент из кучи. Время работы <math>O(\log{n})</math>
* Изменить значение любого элемента. Время работы <math>O(\log{n})</math>

На основе этих операций можно выполнять следующие действия:
* Превратить неупорядоченный массив элементов в кучу. Сложность <math>O(n)</math>
* Отсортировать массив путём превращения его в кучу, а кучу в отсортированный массив. Время работы <math>O(n \log{n})</math>
Здесь <math>n</math> — количество элементов кучи. [[Пространственная сложность]] — <math>O(1)</math> для всех вышеперечисленных операций и действий.

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

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

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

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

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

 Heapify(''A'', ''i'')
   ''left'' &larr; 2''i+1''
   ''right'' &larr; 2''i''+2
   <font color="green">''heap_size - количество элементов в куче''</font>
   ''largest'' &larr; ''i''
   '''if''' ''left'' &le; ''A''.''heap_size'' и ''A''[''left''] > ''A''[''largest'']
     '''then''' ''largest'' &larr; ''left''
   '''if''' ''right'' &le; ''A''.''heap_size'' и ''A''[''right''] > ''A''[''largest'']
     '''then''' ''largest'' &larr; ''right''
   '''if''' ''largest'' &ne; ''i''
     '''then''' Обменять ''A''[''i''] &harr; ''A''[''largest'']
          Heapify(''A'', ''largest'')

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

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

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

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

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

 Build_Heap(''A'')
   ''A''.''heap_size'' &larr; ''A''.''length''
   '''for''' ''i'' &larr; &lfloor;''A''.''length''/2&rfloor; '''downto''' 1
     '''do''' Heapify(''A'', ''i'')
И хотя здесь происходит n/2 вызовов функции Heapify со сложностью  <math>O \left( \log{n} \right) </math>, можно показать, что время работы равно <math>O(n)</math><ref name=CLRS />.

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

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

 Heapsort(''A'')
   Build_Heap(''A'')
   '''for''' ''i'' &larr; ''A''.''length'' '''downto''' 1
     '''do''' Обменять ''A''[1] &harr; ''A''[''i'']
        ''A''.''heap_size'' &larr; ''A''.''heap_size''-1
        Heapify(''A'',1)

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

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

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

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

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

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

 Heap_Insert(''A'', ''key'')
   ''A''.''heap_size'' &larr; ''A''.''heap_size''+1
   ''A''[''A''.''heap_size''] &larr; -&infin;
   Heap_Increase_Key(''A'', ''A''.''heap_size'', key)

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

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

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

== См. также ==
* [[Очередь с приоритетом (программирование)|Очередь с приоритетом]]
* [[Фибоначчиева куча]]
* [[Биномиальная куча]]

== Ссылки ==
{{примечания}}

== Комментарии ==
<references group="К"/>

{{нет источников|дата=2012-10-07}}
{{Структуры данных}}
{{Деревья (структуры данных)}}

[[Категория:Кучи (структуры данных)]]