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

Пример полной двоичной max-heap

Пример полной двоичной минимальной кучи

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

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

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

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

Операции с кучей [ править ]

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

Вставить [ изменить ]

Чтобы добавить элемент в кучу, мы можем выполнить такой алгоритм:

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

Шаги 2 и 3, которые восстанавливают свойство кучи путем сравнения и, возможно, замены узла с его родительским узлом, называются операцией увеличения кучи (также известной как всплытие , фильтрация , просеивание , просачивание , всплытие). вверх , навалом или каскадом ).

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

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

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

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

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

Извлечь [ править ]

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

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

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

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

Снимаем 11 и заменяем на 4.

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

Перемещающийся вниз узел заменяется более крупным из своих дочерних узлов в максимальной куче (в минимальной куче он будет заменен на меньший дочерний узел ), пока он не удовлетворит свойство кучи в своей новой позиции. Эта функциональность достигается функцией 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 наибольшее ← i  если  left ≤ length ( A ) и  A [ left ]> A [ наибольшее ], то : наибольшее ← left, 
 если  right ≤ length ( A ) и  A [ right ]> A [ наибольшее ], то : наибольшее ← справа  если  наибольший ≠ i,  то : поменяйте местами  A [ i ] и A [ наибольший ] Max-Heapify ( A , наибольший )

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

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

Вставить, затем извлечь [ редактировать ]

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

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

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

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

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

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

Искать [ редактировать ]

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

Удалить [ редактировать ]

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

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

Клавиша уменьшения или увеличения [ править ]

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

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

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

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

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

Создание кучи [ править ]

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

Однако метод Вильямса не оптимален. Более быстрый метод (из-за Флойда ^[8] ) начинается с произвольного размещения элементов в двоичном дереве, соблюдая свойство формы (дерево может быть представлено массивом, см. Ниже). Затем, начиная с самого нижнего уровня и двигаясь вверх, просеивайте корень каждого поддерева вниз, как в алгоритме удаления, пока свойство кучи не будет восстановлено. Более конкретно, если все поддеревья, начинающиеся на некоторой высоте , уже были «нагромождены» (самый нижний уровень, соответствующий ), деревья на высоте могут быть скопированы, отправив их корень вниз по пути максимальных значений дочерних элементов при построении максимальной кучи, или минимальные дочерние элементы при построении минимальной кучи. Этот процесс занимает${\ displaystyle h}$${\ displaystyle h = 0}$${\ displaystyle h + 1}$${\ Displaystyle О (ч)}$операций (свопов) на узел. В этом методе большая часть нагромождения происходит на нижних уровнях. Так как высота кучи равна , количество узлов на высоте равно . Следовательно, стоимость накопления всех поддеревьев составляет:${\ Displaystyle \ lfloor \ журнал п \ rfloor}$${\ displaystyle h}$${\ 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 _ {я = 0} ^ {\ infty} я / 2 ^ {я}}$

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

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

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

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

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

Build-Max-Heap ( A ): для каждого индекса i  от  этажа ( длина ( A ) / 2) до 1 do:  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).

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

Затем операции upheap / downheap могут быть сформулированы в терминах массива следующим образом: предположим, что свойство heap выполняется для индексов b , b +1, ..., e . Функция sift-down расширяет свойство heap до 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 . Функция отсеивания вниз применяется хвостовой рекурсивно к индексу j до тех пор, пока свойство кучи не будет установлено для всех элементов.

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

Для больших куч и использования виртуальной памяти хранение элементов в массиве по указанной выше схеме неэффективно: (почти) каждый уровень находится на отдельной странице . 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] Для этого строки чередуются между минимальной кучей и максимальной кучей. Алгоритмы примерно одинаковы, но на каждом шаге необходимо рассматривать чередующиеся строки с чередующимися сравнениями. Производительность примерно такая же, как у обычной однонаправленной кучи. Эту идею можно обобщить для кучи min-max-median. О {\ displaystyle O} ${\ Displaystyle (\ журнал п)}$

Вывод индексных уравнений [ править ]

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

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

Дочерние узлы [ править ]

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

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

${\displaystyle {\text{last}}(l)=(2^{l+1}-1)-1=2^{l+1}-2}$

Пусть в слое L есть узлы после узла , такие что${\displaystyle j}$${\displaystyle i}$

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

У каждого из этих узлов должно быть ровно 2 дочерних элемента , поэтому должны быть узлы, отделяющие правый дочерний элемент от конца его слоя ( ).${\displaystyle j}$${\displaystyle 2j}$${\displaystyle i}$${\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}$

Родительский узел [ править ]

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

1. ${\displaystyle i=2\times ({\text{parent}})+1}$
2. ${\displaystyle i=2\times ({\text{parent}})+2}$

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

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

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

Если node является левым дочерним элементом, это дает результат немедленно, однако он также дает правильный результат, если node является правым дочерним элементом. В этом случае должно быть четным, а значит, должно быть нечетным.${\displaystyle i}$${\displaystyle i}$${\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 }$

Связанные структуры [ править ]

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

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

Сводка времени работы [ править ]

Вот временные сложности ^[17] различных структур данных кучи. Имена функций предполагают минимальную кучу. Для значения " O ( F )" и " thetas ; ( е )" см Big O нотацию .

См. Также [ править ]

• Куча
• Heapsort

Ссылки [ править ]

Внешние ссылки [ править ]

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