Куча сопряжения
Парная куча — это тип кучи структуры данных с относительно простой реализацией и превосходной практической амортизированной производительностью, представленный Майклом Фредманом , Робертом Седжвиком , Дэниелом Слиатором и Робертом Тарджаном в 1986 году. [1] Парные кучи представляют собой , упорядоченные по куче многонаправленные древовидные структуры , и их можно считать упрощенными кучами Фибоначчи . Они считаются «надежным выбором» для реализации таких алгоритмов, как алгоритм Prim MST , [2] и поддерживают следующие операции (при условии минимальной кучи):
- find-min : просто вернуть верхний элемент кучи.
- meld : сравнить два корневых элемента, меньший остается корнем результата, больший элемент и его поддерево добавляются как дочерние элементы этого корня.
- Insert : создать новую кучу для вставленного элемента и объединить ее с исходной кучей.
- уменьшите-ключ (необязательно): удалите поддерево, основанное на ключе, который нужно уменьшить, замените ключ меньшим ключом, затем объедините результат обратно в кучу.
- delete-min : удалить корень и выполнять повторные объединения его поддеревьев, пока не останется одно дерево. Используются различные стратегии слияния.
Анализ временной сложности парных куч изначально был вдохновлен анализом расширенных деревьев . [1] Амортизированное время на удаление-минуту равно O (log n ) , а операции find-min , meld и Insert выполняются за время O (1) . [3]
Когда также добавляется операция уменьшения ключа , определение точного асимптотического времени работы спариваемых куч оказывается затруднительным. Первоначально временная сложность этой операции предполагалась на эмпирических основаниях равной O (1) , [4] но Фредман доказал, что амортизированное время на одну клавишу уменьшения не менее для некоторых последовательностей операций. [5] Используя другой аргумент амортизации, Петти затем доказал, что команды Insert , Meld и уменьшать-ключи работают в амортизированное время, которое . [6] Позже Эльмасри представил разработку парных куч (ленивая, консолидация), для которых с уменьшающим ключом . выполняются прогоны амортизированное время и другие операции имеют оптимальные амортизированные границы, [7] [8] но не туго Bound известен исходной структурой данных. [3] [6]
Хотя асимптотическая производительность парных куч хуже, чем у других алгоритмов очереди с приоритетом, таких как кучи Фибоначчи , которые выполняют уменьшение ключа в амортизированное время, производительность на практике отличная. Джонс [9] и Ларкин, Сен и Тарьян [10] проводил эксперименты по объединению куч и других структур данных кучи. Они пришли к выводу, что д-арные кучи, такие как двоичные кучи, работают быстрее, чем все другие реализации кучи, когда операция уменьшения ключа не требуется (и, следовательно, нет необходимости внешне отслеживать расположение узлов в куче), но что при уменьшении -ключ. Требуется Парные кучи часто работают быстрее, чем d-арные кучи, и почти всегда быстрее, чем другие кучи на основе указателей, включая структуры данных, такие как кучи Фибоначчи , которые теоретически более эффективны. Чен и др. [11] исследовал очереди приоритетов специально для использования с алгоритмом Дейкстры и пришел к выводу, что в обычных случаях использование d-арной кучи без ключа уменьшения (вместо дублирования узлов в куче и игнорирования избыточных экземпляров) приводит к повышению производительности, несмотря на худшие теоретические гарантии производительности.
Структура [ править ]
Куча спаривания — это либо пустая куча, либо дерево спаривания, состоящее из корневого элемента и, возможно, пустого списка деревьев спаривания. Свойство упорядочения кучи требует, чтобы родительский элемент любого узла был не больше самого узла. Следующее описание предполагает чисто функциональную кучу, которая не поддерживает операцию уменьшения ключа .
type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) type PairingHeap[Elem] = Empty | PairingTree[Elem]
Реализация на основе указателей для машин с оперативной памятью , поддерживающая уменьшение ключа , может быть достигнута с использованием трех указателей на узел, представляя дочерние элементы узла двусвязным списком : указатель на первого дочернего узла узла, один на его следующего брата. и один — его предыдущему брату (или, если самый левый брат, его родителю). Его также можно рассматривать как вариант двоичного дерева с левым дочерним и правым сестринским элементом с дополнительным указателем на родителя узла (который представляет его предыдущего родственного узла или фактического родителя для самого левого родственного узла). В качестве альтернативы, указатель предыдущего элемента можно опустить, позволив последнему дочернему элементу указывать обратно на родительский элемент, если добавлен один логический флаг, обозначающий «конец списка». Это обеспечивает более компактную структуру за счет постоянного коэффициента накладных расходов на операцию. [1]
Операции [ править ]
Отчет [ править ]
Объединение с пустой кучей возвращает другую кучу, в противном случае возвращается новая куча, имеющая минимум из двух корневых элементов в качестве корневого элемента и просто добавляющая кучу с большим корнем в список подкуч:
function meld(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem]
if heap1 is Empty
return heap2
elsif heap2 is Empty
return heap1
elsif heap1.elem < heap2.elem
return Heap(heap1.elem, heap2 :: heap1.subheaps)
else
return Heap(heap2.elem, heap1 :: heap2.subheaps)
Вставить [ править ]
Самый простой способ вставить элемент в кучу — объединить кучу с новой кучей, содержащей только этот элемент и пустой список подкуч:
function insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem]
return meld(Heap(elem, []), heap)
Найти-мин [ править ]
Функция find-min просто возвращает корневой элемент кучи:
function find-min(heap: PairingHeap[Elem]) -> Elem
if heap is Empty
error
else
return heap.elem
Удалить-моё [ изменить ]
Единственная нетривиальная фундаментальная операция — удаление минимального элемента из кучи. Это требует выполнения повторных объединений дочерних элементов до тех пор, пока не останется только одно дерево. Стандартная стратегия сначала объединяет подкучи в пары (это шаг, который дал название этой структуре данных) слева направо, а затем объединяет полученный список куч справа налево:
function delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem]
if heap is Empty
error
else
return merge-pairs(heap.subheaps)
При этом используется вспомогательная функция merge-pairs :
function merge-pairs(list: List[PairingTree[Elem]]) -> 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])
=> meld(meld(H1, H2), merge-pairs([H3, H4, H5, H6, H7]))
# meld H1 and H2 to H12, then the rest of the list
=> meld(H12, meld(meld(H3, H4), merge-pairs([H5, H6, H7])))
# meld H3 and H4 to H34, then the rest of the list
=> meld(H12, meld(H34, meld(meld(H5, H6), merge-pairs([H7]))))
# meld H5 and H6 to H56, then the rest of the list
=> meld(H12, meld(H34, meld(H56, H7)))
# switch direction, meld the last two resulting heaps, giving H567
=> meld(H12, meld(H34, H567))
# meld the last two resulting heaps, giving H34567
=> meld(H12, H34567)
# finally, meld the first pair with the result of merging the rest
=> H1234567
Сводка времени работы [ править ]
Вот временные сложности [12] различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. .
| Операция | найти-мин | удаление-мин | вставлять | клавиша уменьшения | сливаться |
|---|---|---|---|---|---|
| Двоичный [12] | я (1) | Θ (логарифм n ) | О ( войти ) | О ( войти ) | Θ ( н ) |
| Левый | я (1) | Θ (логарифм n ) | Θ (логарифм n ) | О ( войти ) | Θ (логарифм n ) |
| Биномиальный [12] [13] | я (1) | Θ (логарифм n ) | я (1) [а] | Θ (логарифм n ) | О ( войти ) |
| Наклонный бином [14] | я (1) | Θ (логарифм n ) | я (1) | Θ (логарифм n ) | О ( войти ) [б] |
| Сопряжение [3] | я (1) | О ( войти ) [а] | я (1) | о ( войти ) [а] [с] | я (1) |
| Сопряжение по рангам [17] | я (1) | О ( войти ) [а] | я (1) | я (1) [а] | я (1) |
| Фибоначчи [12] [18] | я (1) | О ( войти ) [а] | я (1) | я (1) [а] | я (1) |
| Строгий Фибоначчи [19] | я (1) | О ( войти ) | я (1) | я (1) | я (1) |
| Мостовая долина [20] [д] | я (1) | О ( войти ) | я (1) | я (1) | я (1) |
| 2–3 кучи [22] | я (1) | О ( войти ) [а] | я (1) [а] | я (1) | О ( войти ) |
- ^ Jump up to: а б с д и ж г час я Амортизированное время.
- ^ в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).
- ^ Нижняя граница [15] верхняя граница [16]
- ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). [21]
Ссылки [ править ]
- ^ Jump up to: а б с Фредман, Майкл Л .; Седжвик, Роберт ; Слитор, Дэниел Д .; Тарьян, Роберт Э. (1986). «Парная куча: новая форма саморегулирующейся кучи» (PDF) . Алгоритмика . 1 (1–4): 111–129. дои : 10.1007/BF01840439 . S2CID 23664143 .
- ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер. п. 231.
- ^ Jump up to: а б с Яконо, Джон (2000), «Улучшенные верхние границы для спаривания куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF) , Конспекты лекций по информатике, том. 1851, Springer-Verlag, стр. 63–77, arXiv : 1110.4428 , CiteSeerX 10.1.1.748.7812 , doi : 10.1007/3-540-44985-X_5 , ISBN 3-540-67690-2
- ^ Стаско, Джон Т .; Виттер, Джеффри С. (1987), «Сопряжение куч: эксперименты и анализ» (PDF) , Communications of the ACM , 30 (3): 234–249, CiteSeerX 10.1.1.106.2988 , doi : 10.1145/214748.214759 , S2CID 17811811
- ^ Фредман, Майкл Л. (1999). «Об эффективности объединения куч и связанных с ними структур данных» (PDF) . Журнал АКМ . 46 (4): 473–501. дои : 10.1145/320211.320214 . S2CID 16115266 . Архивировано из оригинала (PDF) 21 июля 2011 г. Проверено 3 мая 2011 г.
- ^ Jump up to: а б Петти, Сет (2005), «К окончательному анализу парных куч» (PDF) , Proc. 46-й ежегодный симпозиум IEEE по основам информатики (PDF) , стр. 174–183, doi : 10.1109/SFCS.2005.75 , ISBN 0-7695-2468-0 , S2CID 2717102
- ^ Элмасри, Амр (2009), «Сопряжение кучи с O (log log n ) снижает стоимость» (PDF) , Proc. 20-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 471–476, CiteSeerX 10.1.1.502.6706 , doi : 10.1137/1.9781611973068.52
- ^ Эльмасри, Амр (ноябрь 2017 г.). «На пути к оптимальным саморегулирующимся отвалам» . Транзакции ACM на алгоритмах . 13 (4): 1–14. дои : 10.1145/3147138 . S2CID 1182235 .
- ^ Джонс, Дуглас В. (1986). «Эмпирическое сравнение реализаций очереди приоритетов и наборов событий». Коммуникации АКМ . 29 (4): 300–311. CiteSeerX 10.1.1.117.9380 . дои : 10.1145/5684.5686 . S2CID 43650389 .
- ^ Ларкин, Дэниел Х.; Сен, Сиддхартха; Тарьян, Роберт Э. (2014), «Эмпирическое исследование приоритетных очередей, возвращающееся к основам», Труды 16-го семинара по разработке алгоритмов и экспериментам , стр. 61–72, arXiv : 1403.0252 , doi : 10.1137/1.9781611973198. 7 , ISBN 978-1-61197-319-8 , S2CID 15216766
- ^ Чен, Мо; Чоудхури, Резаул Алам; Рамачандран, Виджая; Рош, Дэвид Лан; Тонг, Линлинг (12 октября 2007 г.). Приоритетные очереди и алгоритм Дейкстры (PDF) (Технический отчет). Техасский университет. ТР-07-54.
{{cite tech report}}: CS1 maint: дата и год ( ссылка ) - ^ Jump up to: а б с д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .
- ^ «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.
- ^ Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x
- ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .
- ^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .
- ^ Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .
- ^ Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .
- ^ Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .
- ^ Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
- ^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .
- ^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
Внешние ссылки [ править ]
- Луи Вассерман обсуждает парные кучи и их реализацию в Haskell в The Monad Reader, выпуск 16 (стр. 37–52).
- Пейринг кучи , Сартадж Сахни