Куча сопряжения

Он просил вычислительную диаграмму или диаграмма быть включена в этой статье, чтобы улучшить ее качество. Конкретные иллюстрации, графики или диаграммы можно запросить в Graphic Lab. Для получения дополнительной информации см. Обсуждение на этой странице и / или листинг в Википедии: Запрошенные изображения.

Спаривание куча представляет собой тип кучи структуры данных с относительно простой реализации и отличным практическим амортизационной производительности, введенной Майкла Фридмана, Роберт Седжвик, Дэниел Слитор и Тарьян в 1986. Сопряжение отвалов являются кучи заказал многосторонние структуры деревьев, и может быть рассматриваются упрощенные кучи Фибоначчи. Они считаются «надежным выбором» для реализации таких алгоритмов, как алгоритм MST Прима, и поддерживают следующие операции (предполагая минимальную кучу):

• find-min : просто вернуть верхний элемент кучи.
• meld : сравните два корневых элемента, меньший остается корнем результата, больший элемент и его поддерево добавляются как дочерние к этому корню.
• вставить : создать новую кучу для вставленного элемента и объединить с исходной кучей.
• уменьшение-ключ (необязательно): удалите поддерево с корнем ключа, который нужно уменьшить, замените ключ ключом меньшего размера, затем слейте результат обратно в кучу.
• удаление-мин : удалить корень и не делать повторные собирая комбинации из его поддеревьев, пока остается один дерево. Используются различные стратегии слияния.

Первоначально анализ временной сложности парных куч был вдохновлен анализом растянутых деревьев. Амортизированное время на удаление-мин составляет O (log n ), а операции find-min, meld и insert выполняются за O (1) амортизированного времени.

Когда также добавляется операция уменьшения ключа, определение точного асимптотического времени работы парных куч оказалось затруднительным. Первоначально на эмпирических основаниях предполагалось, что временная сложность этой операции равна O (1), но Фредман доказал, что амортизированное время на клавишу уменьшения составляет, по крайней мере, для некоторых последовательностей операций. Затем, используя другой аргумент амортизации, Петти доказал, что вставка, объединение и уменьшение ключа выполняются в течение амортизированного времени, а именно. Позже Элмасри представил разработки парных куч (ленивый, консолидированный), для которых прогоны с уменьшением ключа за амортизированное время и другие операции имеют оптимальные амортизированные границы, но точные границы для исходной структуры данных неизвестны. ${\ Displaystyle \ Omega (\ журнал \ журнал п)}$${\ Displaystyle О (2 ^ {2 {\ sqrt {\ log \ log n}}})}$${\ Displaystyle о (\ журнал п)}$${\ Displaystyle О (\ журнал \ журнал п)}$${\ Displaystyle \ Theta (\ журнал \ журнал п)}$

Хотя асимптотическая производительность объединения куч хуже, чем у других алгоритмов очередей с приоритетом, таких как кучи Фибоначчи, которые выполняют функцию уменьшения ключа за амортизированное время, на практике производительность превосходна. Джонс и Ларкин, Сен и Тарджан провели эксперименты по объединению куч и других структур данных кучи. Они пришли к выводу, что динамические кучи, такие как двоичные кучи, работают быстрее, чем все другие реализации кучи, когда операция уменьшения ключа не требуется (и, следовательно, нет необходимости извне отслеживать местоположение узлов в куче), но что при уменьшении -key требуется объединение кучи часто быстрее, чем d-ary кучи, и почти всегда быстрее, чем другие кучи, основанные на указателях, включая структуры данных, такие как кучи Фибоначчи, которые теоретически более эффективны. Chen et al. исследовали приоритетные очереди специально для использования с алгоритмом Дейкстры и пришли к выводу, что в обычных случаях использование d-ary heap без ключа уменьшения (вместо дублирования узлов в куче и игнорирования избыточных экземпляров) приводит к лучшей производительности, несмотря на худшие теоретические гарантии производительности. ${\ displaystyle O (1)}$

• 1 Структура
• 2 Операции
  • 2.1 find-min
  • 2,2 MELD
  • 2.3 вставка
  • 2.4 удаление мин.
• 3 Сводка времени работы
• 4 ссылки
• 5 Внешние ссылки

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

type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) type PairingHeap[Elem] = Empty | PairingTree[Elem]

Реализация на основе указателей для машин RAM, поддерживающая клавишу уменьшения, может быть достигнута с использованием трех указателей на узел, путем представления дочерних узлов узла односвязным списком : указатель на первого дочернего узла узла, один на его следующего брата., а один - его предыдущему брату (или, для крайнего левого брата, его родителю). В качестве альтернативы, предыдущий указатель можно опустить, позволив последнему дочернему элементу указывать обратно на родителя, если добавлен единственный логический флаг, указывающий на «конец списка». Это позволяет получить более компактную структуру за счет постоянного коэффициента накладных расходов на операцию.

find-min

Функция find-min просто возвращает корневой элемент кучи:

function find-min(heap: PairingHeap[Elem]) -gt; Elem if heap is Empty error else return heap.elem

объединить

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

function meld(heap1, heap2: PairingHeap[Elem]) -gt; PairingHeap[Elem] if heap1 is Empty return heap2 elsif heap2 is Empty return heap1 elsif heap1.elem lt; heap2.elem return Heap(heap1.elem, heap2 :: heap1.subheaps) else return Heap(heap2.elem, heap1 :: heap2.subheaps)

вставлять

Самый простой способ вставить элемент в кучу - объединить кучу с новой кучей, содержащей только этот элемент и пустой список под кучей:

function insert(elem: Elem, heap: PairingHeap[Elem]) -gt; PairingHeap[Elem] return meld(Heap(elem, []), heap)

delete-min

Единственная нетривиальная фундаментальная операция - это удаление минимального элемента из кучи. Это требует повторных объединений его дочерних элементов, пока не останется только одно дерево. Стандартная стратегия сначала объединяет вспомогательные кучи попарно (это шаг, который дал название этой структуре данных) слева направо, а затем объединяет получившийся список куч справа налево:

function delete-min(heap: PairingHeap[Elem]) -gt; PairingHeap[Elem] if heap is Empty error else return merge-pairs(heap.subheaps)

Здесь используются пары слияния вспомогательной функции:

function merge-pairs(list: List[PairingTree[Elem]]) -gt; PairingHeap[Elem] if length(list) == 0 return Empty elsif length(list) == 1 return list[0] else return meld(meld(list[0], list[1]), merge-pairs(list[2..]))

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

 merge-pairs([H1, H2, H3, H4, H5, H6, H7]) =gt; meld(meld(H1, H2), merge-pairs([H3, H4, H5, H6, H7])) # meld H1 and H2 to H12, then the rest of the list =gt; meld(H12, meld(meld(H3, H4), merge-pairs([H5, H6, H7]))) # meld H3 and H4 to H34, then the rest of the list =gt; meld(H12, meld(H34, meld(meld(H5, H6), merge-pairs([H7])))) # meld H5 and H6 to H56, then the rest of the list =gt; meld(H12, meld(H34, meld(H56, H7))) # switch direction, meld the last two resulting heaps, giving H567 =gt; meld(H12, meld(H34, H567)) # meld the last two resulting heaps, giving H34567 =gt; meld(H12, H34567) # finally, meld the first pair with the result of merging the rest =gt; H1234567

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

• Луи Вассерман обсуждает объединение кучи и их реализацию в Haskell в The Monad Reader, выпуск 16 (стр. 37–52).
• парные кучи, Сартадж Сахни