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

Двоичная куча — это структура данных кучи , которая принимает форму двоичного дерева . Двоичные кучи являются распространенным способом реализации приоритетных очередей . ^{[1] : 162–163} Двоичная куча была введена Дж. У. Дж. Уильямсом в 1964 году как структура данных для реализации пирамидальной сортировки . ^[2]

Двоичная куча определяется как двоичное дерево с двумя дополнительными ограничениями: ^[3]

• Свойство формы: двоичная куча представляет собой полное двоичное дерево ; то есть все уровни дерева, за исключением, возможно, последнего (самого глубокого), полностью заполнены, и, если последний уровень дерева не заполнен, узлы этого уровня заполняются слева направо.
• Свойство кучи: ключ, хранящийся в каждом узле, либо больше или равен (≥), либо меньше или равен (≤) ключам в дочерних узлах, в соответствии с некоторым общим порядком .

Кучи, где родительский ключ больше или равен (≥) дочерним ключам, называются max-heaps ; те, где он меньше или равен (≤), называются min-heaps . Эффективные (то есть логарифмические по времени ) алгоритмы известны для двух операций, необходимых для реализации приоритетной очереди на двоичной куче:

• Вставка элемента;
• Удаление наименьшего или наибольшего элемента из (соответственно) min-heap или max-heap.

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

Обе операции — вставка и удаление — сначала изменяют кучу, чтобы сохранить свойство формы, добавляя или удаляя с конца кучи. Затем свойство кучи восстанавливается путем перемещения вверх или вниз по куче. Обе операции занимают время O(log n ) .

Чтобы вставить элемент в кучу, мы выполняем следующие шаги:

1. Добавьте элемент на нижний уровень кучи в самое левое открытое пространство.
2. Сравните добавленный элемент с его родителем; если они в правильном порядке, остановитесь.
3. Если нет, поменяйте местами элемент с его родительским и вернитесь к предыдущему шагу.

Шаги 2 и 3, которые восстанавливают свойство кучи путем сравнения и возможной замены узла на его родительский узел, называются операцией up-heap (также известной как bubble-up , percolate-up , sift-up , trickle-up , swim-up , heapify-up , cascade-up или fix-up ).

Количество требуемых операций зависит только от количества уровней, на которые должен подняться новый элемент, чтобы удовлетворить свойству кучи. Таким образом, операция вставки имеет наихудшую временную сложность O(log n ) . Для случайной кучи и для повторных вставок операция вставки имеет среднюю временную сложность O(1). ^{[4] [5]}

В качестве примера вставки двоичной кучи предположим, что у нас есть максимальная куча

и мы хотим добавить в кучу число 15. Сначала мы помещаем 15 в позицию, отмеченную X. Однако свойство кучи нарушается, поскольку 15 > 8 , поэтому нам нужно поменять местами 15 и 8. Итак, после первой замены куча выглядит следующим образом:

Однако свойство кучи все еще нарушается, поскольку 15 > 11 , поэтому нам нужно снова выполнить замену:

что является допустимой max-heap. Нет необходимости проверять левого потомка после этого последнего шага: в начале max-heap был допустимым, то есть корень уже был больше своего левого потомка, поэтому замена корня еще большим значением сохранит свойство, что каждый узел больше своих потомков ( 11 > 5 ; если 15 > 11 и 11 > 5 , то 15 > 5 из-за транзитивного отношения ).

Процедура удаления корня из кучи (фактически извлечение максимального элемента в max-куче или минимального элемента в min-куче) с сохранением свойства кучи выглядит следующим образом:

1. Замените корень кучи последним элементом на последнем уровне.
2. Сравните новый корень с его дочерними элементами; если они расположены в правильном порядке, остановитесь.
3. Если нет, поменяйте элемент с одним из его дочерних элементов и вернитесь к предыдущему шагу. (Поменяйте местами его меньший дочерний элемент в минимальной куче и его больший дочерний элемент в максимальной куче.)

Шаги 2 и 3, которые восстанавливают свойство кучи путем сравнения и возможной замены узла на один из его дочерних узлов, называются операцией down-heap (также известной как bubble-down , percolate-down , sift-down , sink-down , trickle down , heapify-down , cascade-down , fix-down , extract-min или extract-max или просто heapify ).

Итак, если у нас та же максимальная куча, что и раньше

Удаляем 11 и заменяем его на 4.

Теперь свойство кучи нарушено, поскольку 8 больше 4. В этом случае для восстановления свойства кучи достаточно поменять местами два элемента, 4 и 8, и нам не нужно менять элементы местами дальше:

Узел, движущийся вниз, меняется местами с большим из своих потомков в max-heap (в min-heap он будет меняться местами со своим меньшим потомком), пока он не удовлетворит свойству кучи в своем новом положении. Эта функциональность достигается функцией Max -Heapify , как определено ниже в псевдокоде для кучи с поддержкой массива A длины length ( A ) . A индексируется, начиная с 1.

// Выполнить операцию down-heap или heapify-down для max-heap// A : массив, представляющий кучу, индексированный начиная с 1// i : индекс, с которого следует начать при пирамидальной разбивке Max-Heapify ( A , i ): left ← 2× i  right ← 2× i + 1 largest ← i  если  лево ≤ длина ( A ) и  A [ лево ] > A [ наибольший ] тогда : наибольший ← лево 
 если  право ≤ длина ( A ) и  A [ право ] > A [ наибольший ] тогда : наибольший ← право  если  largest ≠ i,  то : поменять местами  A [ i ] и A [ largest ] Max-Heapify ( A , largest )

Для того, чтобы приведенный выше алгоритм правильно переделал массив в кучу, ни один узел, кроме узла с индексом i и его двух прямых потомков, не может нарушить свойство кучи. Операция down-heap (без предшествующего обмена) также может использоваться для изменения значения корня, даже если элемент не удаляется.

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

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

1. Сравнить, больше ли элемент, который мы выдвигаем, или элемент, который находится наверху кучи (предполагая, что куча максимальная)
2. Если корень кучи больше:
   1. Заменить корень новым элементом
   2. Down-heapify, начиная с корня
3. В противном случае верните товар, который мы продвигаем.

Python предоставляет такую ​​функцию для вставки, а затем извлечения, называемую «heappushpop», которая перефразирована ниже. ^{[6] [7]} Предполагается, что массив кучи имеет первый элемент с индексом 1.

// Помещаем новый элемент в (максимальную) кучу, а затем извлекаем корень полученной кучи.// куча : массив, представляющий кучу, индексированный с 1// item : элемент для вставки// Возвращает большее из двух значений между элементом и корнем кучи . Push-Pop ( heap : List<T>, item : T) -> T: если  куча не пуста и heap[1] > item  тогда : // < if min heap поменять местами  heap [1] и item _downheap( heap, начиная с индекса 1) return  item

Аналогичную функцию можно определить для извлечения и последующей вставки, что в Python называется «heapreplace»:

// Извлечь корень кучи и добавить новый элемент// куча : массив, представляющий кучу, индексированный с 1// item : элемент для вставки// Возвращает текущий корень кучи Replace ( heap : List<T>, item : T) -> T: поменять местами  кучу [1] и элемент _downheap( heap , начиная с индекса 1) return  item

Нахождение произвольного элемента занимает O(n) времени.

Удаление произвольного элемента можно выполнить следующим образом:

1. Найдите индекс элемента, который мы хотим удалить.${\displaystyle я}$
2. Поменять этот элемент с последним элементом. Удалить последний элемент после обмена.
3. Down-heapify или up-heapify для восстановления свойства кучи. В max-heap (min-heap) up-heapify требуется только тогда, когда новый ключ элемента больше (меньше) предыдущего, потому что может быть нарушено только свойство кучи родительского элемента. Предполагая, что свойство кучи было действительным между элементом и его дочерними элементами до обмена элементами, оно не может быть нарушено теперь большим (меньшим) значением ключа. Когда новый ключ меньше (больше) предыдущего, то требуется только down-heapify, потому что свойство кучи может быть нарушено только в дочерних элементах.${\displaystyle я}$${\displaystyle я}$

Операция уменьшения ключа заменяет значение узла с заданным значением на меньшее значение, а операция увеличения ключа делает то же самое, но с большим значением. Это включает в себя поиск узла с заданным значением, изменение значения, а затем down-heapifying или up-heapifying для восстановления свойства кучи.

Уменьшить клавишу можно следующим образом:

1. Найдите индекс элемента, который мы хотим изменить.
2. Уменьшить значение узла
3. Down-heapify (предполагая максимальную кучу) для восстановления свойства кучи

Увеличить ключ можно следующим образом:

1. Найдите индекс элемента, который мы хотим изменить.
2. Увеличить ценность узла
3. Up-heapify (предполагая максимальную кучу) для восстановления свойства кучи

Построение кучи из массива из n входных элементов можно осуществить, начав с пустой кучи, а затем последовательно вставляя каждый элемент. Этот подход, называемый методом Уильямса в честь изобретателя двоичных куч, легко можно увидеть работающим за время O ( n log n ) : он выполняет n вставок по стоимости O (log n ) каждая. ^[a]

Однако метод Уильямса неоптимален. Более быстрый метод (благодаря Флойду ^[8] ) начинается с произвольного размещения элементов на бинарном дереве, учитывая свойство формы (дерево может быть представлено массивом, см. ниже). Затем, начиная с самого нижнего уровня и двигаясь вверх, просеиваем корень каждого поддерева вниз, как в алгоритме удаления, пока не будет восстановлено свойство кучи. Более конкретно, если все поддеревья, начинающиеся с некоторой высоты, уже были «кучированы» (самый нижний уровень соответствует ), деревья на высоте могут быть кучированы, отправив их корень вниз по пути максимально значимых потомков при построении максимальной кучи или минимально значимых потомков при построении минимальной кучи. Этот процесс занимает операций (обменов) на узел. В этом методе большая часть кучообразования происходит на нижних уровнях. Поскольку высота кучи равна , количество узлов на высоте равно . Следовательно, стоимость кучообразования всех поддеревьев равна:${\displaystyle ч}$${\displaystyle h=0}$${\displaystyle h+1}$${\displaystyle O(h)}$${\displaystyle \lfloor \log n\rfloor }$${\displaystyle ч}$${\displaystyle \leq {\frac {2^{\lfloor \log n\rfloor }}{2^{h}}}\leq {\frac {n}{2^{h}}}}$

${\displaystyle {\begin{align}\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {n}{2^{h}}}O(h)&=O\left(n\sum _{h=0}^{\lfloor \log n\rfloor }{\frac {h}{2^{h}}}\right)\\&=O\left(n\sum _{h=0}^{\infty }{\frac {h}{2^{h}}}\right)\\&=O(n)\end{align}}}$

При этом используется тот факт, что заданный бесконечный ряд сходится .${\textstyle \sum _{i=0}^{\infty }i/2^{i}}$

Известно, что точное значение вышеприведенного выражения (наихудшее число сравнений при построении кучи) равно:

${\displaystyle 2n-2s_{2}(n)-e_{2}(n)}$, ^{[9] [б]}

где s ₂ ( n ) — сумма всех цифр двоичного представления числа n , а e ₂ ( n ) — показатель степени числа 2 в разложении числа n на простые множители .

Средний случай сложнее для анализа, но можно показать, что он асимптотически приближается к 1,8814  n − 2 log ₂ n + O (1) сравнений. ^{[10] [11]}

Следующая функция Build-Max-Heap преобразует массив A , который хранит полное двоичное дерево с n узлами, в max-heap, многократно используя Max-Heapify (down-heapify для max-heap) снизу вверх. Элементы массива, индексированные floor ( n /2) + 1 , floor ( n /2) + 2 , ..., n , являются листьями дерева (предполагая, что индексы начинаются с 1) — таким образом, каждый из них является кучей из одного элемента и не нуждается в down-heapify. Build-Max-Heap запускает Max-Heapify на каждом из оставшихся узлов дерева.

Build-Max-Heap ( A ): для каждого индекса i  от  пола ( длина ( A )/2) до 1 выполнить:  Max-Heapify ( A , i )

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

Пусть n будет числом элементов в куче, а i будет произвольным допустимым индексом массива, хранящего кучу. Если корень дерева находится в индексе 0, с допустимыми индексами от 0 до n − 1, то каждый элемент a в индексе i имеет

• дети с индексами 2 i + 1 и 2 i + 2
• его родительский элемент на индексном этаже (( i − 1) / 2).

В качестве альтернативы, если корень дерева находится в индексе 1 с допустимыми индексами от 1 до n , то каждый элемент a в индексе i имеет

• дети с индексами 2 i и 2 i +1
• его родительский элемент на индексном этаже ( i / 2).

Эта реализация используется в алгоритме пирамидальной сортировки , который повторно использует пространство, выделенное входному массиву, для хранения кучи (т.е. алгоритм выполняется на месте ). Эта реализация также полезна в качестве очереди с приоритетами . При использовании динамического массива возможна вставка неограниченного количества элементов.

Операции upheapor downheapмогут быть сформулированы в терминах массива следующим образом: предположим, что свойство кучи выполняется для индексов b , b +1, ..., e . Функция sift-down расширяет свойство кучи до b −1, b , b +1, ..., e . Только индекс i = b −1 может нарушить свойство кучи. Пусть j будет индексом наибольшего дочернего элемента a [ i ] (для max-heap или наименьшего дочернего элемента для min-heap) в диапазоне b , ..., e . (Если такого индекса не существует, потому что 2 i > e , то свойство кучи выполняется для нового расширенного диапазона, и ничего делать не нужно.) При перестановке значений a [ i ] и a [ j ] свойство кучи для позиции i устанавливается. На этом этапе единственная проблема заключается в том, что свойство кучи может не выполняться для индекса j . Функция sift-down применяется хвостовой рекурсией к индексу j до тех пор, пока свойство кучи не будет установлено для всех элементов.

Функция просеивания работает быстро. На каждом шаге ей нужно всего два сравнения и один обмен. Значение индекса, где она работает, удваивается на каждой итерации, так что требуется максимум log ₂ e шагов.

Для больших куч и использования виртуальной памяти хранение элементов в массиве по вышеприведенной схеме неэффективно: (почти) каждый уровень находится на другой странице . B-кучи — это двоичные кучи, которые хранят поддеревья на одной странице, уменьшая количество страниц, к которым осуществляется доступ, вплоть до десятикратного. ^[12]

Операция слияния двух двоичных куч занимает Θ( n ) для куч одинакового размера. Лучшее, что вы можете сделать, это (в случае реализации массива) просто объединить два массива куч и построить кучу результата. ^[13] Кучу из n элементов можно объединить с кучей из k элементов, используя O(log n log k ) сравнений ключей, или, в случае реализации на основе указателей, за время O(log n log k ). ^[14] Алгоритм разделения кучи из n элементов на две кучи по k и nk элементов соответственно, основанный на новом представлении о кучах как упорядоченных коллекциях подкуч, был представлен в. ^[15] Алгоритм требует O(log n * log n ) сравнений. Представление также представляет новый и концептуально простой алгоритм слияния куч. Если слияние является распространенной задачей, рекомендуется использовать другую реализацию кучи, например, биномиальную кучи , которую можно объединить за O(log n ).

Кроме того, двоичная куча может быть реализована с помощью традиционной структуры данных двоичного дерева, но при добавлении элемента возникает проблема с поиском соседнего элемента на последнем уровне двоичной кучи. Этот элемент может быть определен алгоритмически или путем добавления дополнительных данных к узлам, что называется «разбиением» дерева — вместо того, чтобы просто хранить ссылки на потомков, мы также сохраняем инпорядоченного преемника узла.

Можно изменить структуру кучи, чтобы сделать возможным извлечение как наименьшего, так и наибольшего элемента за определенное время. ^[16] Для этого строки чередуются между минимальной кучей и максимальной кучей. Алгоритмы примерно одинаковы, но на каждом шаге необходимо учитывать чередующиеся строки с чередующимися сравнениями. Производительность примерно такая же, как у обычной однонаправленной кучи. Эту идею можно обобщить до минимально-максимально-медианной кучи.${\displaystyle О}$${\displaystyle (\log n)}$

В куче на основе массива дочерние и родительские элементы узла могут быть найдены с помощью простой арифметики по индексу узла. В этом разделе выводятся соответствующие уравнения для куч с корнем в индексе 0, с дополнительными примечаниями по кучам с корнем в индексе 1.

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

Для общего узла, расположенного по индексу i (начиная с 0), сначала выведем индекс его правого потомка, .${\displaystyle {\text{right}}=2i+2}$

Пусть узел i находится на уровне L , и обратите внимание, что любой уровень l содержит ровно узлов. Более того, ровно узлов содержится в слоях до слоя l включительно (представьте себе двоичную арифметику; 0111...111 = 1000...000 - 1). Поскольку корень хранится в 0, узел k будет храниться в индексе . Объединение этих наблюдений дает следующее выражение для индекса последнего узла в слое l .${\displaystyle 2^{л}}$${\displaystyle 2^{l+1}-1}$${\displaystyle (k-1)}$

${\displaystyle {\text{последний}}(л)=(2^{л+1}-1)-1=2^{л+1}-2}$

Пусть после узла i в слое L имеется j узлов , таких что

${\displaystyle {\begin{alignedat}{2}i=&\quad {\text{last}}(L)-j\\=&\quad (2^{L+1}-2)-j\\\end{alignedat}}}$

Каждый из этих j узлов должен иметь ровно 2 дочерних узла, поэтому должны быть узлы, отделяющие правого дочернего узла i от конца его слоя ( ).${\displaystyle 2j}$${\displaystyle L+1}$

${\displaystyle {\begin{alignedat}{2}{\text{right}}=&\quad {\text{last(L + 1)}}-2j\\=&\quad (2^{L+2}-2)-2j\\=&\quad 2(2^{L+1}-2-j)+2\\=&\quad 2i+2\end{alignedat}}}$

Заметив, что левый дочерний элемент любого узла всегда находится на 1 позицию раньше своего правого дочернего элемента, получаем .${\displaystyle {\text{left}}=2i+1}$

Если корень расположен в индексе 1 вместо 0, последний узел на каждом уровне находится в индексе . Использование этого повсюду приводит к и для куч с корнем в 1.${\displaystyle 2^{l+1}-1}$${\displaystyle {\text{left}}=2i}$${\displaystyle {\text{right}}=2i+1}$

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

• ${\displaystyle i=2\times ({\text{родитель}})+1}$
• ${\displaystyle i=2\times ({\text{родитель}})+2}$

Следовательно,

${\displaystyle {\text{parent}}={\frac {i-1}{2}}\;{\textrm {or}}\;{\frac {i-2}{2}}}$

Теперь рассмотрим выражение .${\displaystyle \left\lfloor {\dfrac {i-1}{2}}\right\rfloor }$

Если узел является левым потомком, это дает результат немедленно, однако, это также дает правильный результат, если узел является правым потомком. В этом случае должно быть четным, и, следовательно, должно быть нечетным.${\displaystyle я}$${\displaystyle я}$${\displaystyle (i-2)}$${\displaystyle (i-1)}$

${\displaystyle {\begin{alignedat}{2}\left\lfloor {\dfrac {i-1}{2}}\right\rfloor =&\quad \left\lfloor {\dfrac {i-2}{2}}+{\dfrac {1}{2}}\right\rfloor \\=&\quad {\frac {i-2}{2}}\\=&\quad {\text{parent}}\end{alignedat}}}$

Поэтому, независимо от того, является ли узел левым или правым потомком, его родителя можно найти с помощью выражения:

${\displaystyle {\text{parent}}=\left\lfloor {\dfrac {i-1}{2}}\right\rfloor }$

Поскольку порядок родственных элементов в куче не определяется свойством кучи, два дочерних элемента одного узла могут свободно меняться местами, если только это не нарушает свойство формы (сравните с treap ). Обратите внимание, однако, что в общей куче на основе массива простая замена дочерних элементов может также потребовать перемещения узлов поддерева дочерних элементов для сохранения свойства кучи.

Двоичная куча является частным случаем d-арной кучи, в которой d = 2.

Вот временные сложности ^[17] различных структур данных кучи. Сокращение am. указывает на то, что данная сложность амортизирована, в противном случае это сложность наихудшего случая. Для значения " O ( f )" и " Θ ( f )" см . нотацию Big O. Имена операций предполагают минимальную кучу.

• Открытые структуры данных - Раздел 10.1 - BinaryHeap: неявное двоичное дерево, Пэт Морин
• Реализация двоичной максимальной кучи на языке C Робина Томаса
• Реализация двоичной минимальной кучи на языке C Робином Томасом