Куча сопряжения
Парная куча — это тип кучи структуры данных с относительно простой реализацией и превосходной практической амортизированной производительностью, представленный Майклом Фредманом , Робертом Седжвиком , Дэниелом Слиатором и Робертом Тарджаном в 1986 году. [1] Парные кучи представляют собой , упорядоченные по куче многонаправленные древовидные структуры , и их можно считать упрощенными кучами Фибоначчи . Они считаются «надежным выбором» для реализации таких алгоритмов, как алгоритм MST Прима , [2] и поддерживают следующие операции (при условии минимальной кучи):
- find-min : просто вернуть верхний элемент кучи.
- meld : сравнить два корневых элемента, меньший остается корнем результата, больший элемент и его поддерево добавляются как дочерние элементы этого корня.
- Insert : создать новую кучу для вставленного элемента и объединить ее с исходной кучей.
- уменьшите-ключ (необязательно): удалите поддерево, основанное на ключе, который нужно уменьшить, замените ключ меньшим ключом, затем объедините результат обратно в кучу.
- delete-min : удалить корень и выполнять повторные объединения его поддеревьев, пока не останется одно дерево. Используются различные стратегии слияния.
Анализ временной сложности парных куч изначально был вдохновлен анализом расширенных деревьев . [1] Амортизированное время на одну минуту удаления равно O (log n ) , а операции find-min , meld и вставки выполняются за время O (1) . [3]
Когда также добавляется операция уменьшения ключа , определение точного асимптотического времени работы спариваемых куч оказывается затруднительным. Первоначально временная сложность этой операции предполагалась на эмпирических основаниях равной O (1) , [4] но Фредман доказал, что амортизированное время на одну клавишу уменьшения не менее для некоторых последовательностей операций. [5] Используя другой аргумент амортизации, Петти затем доказал, что команды Insert , Meld и уменьшать-ключи работают в амортизированное время, которое . [6] Позже Элмасри представил разработку парных куч (ленивая, консолидация), для которых с уменьшающим ключом . выполняются прогоны амортизированное время и другие операции имеют оптимальные амортизированные границы, [7] [8] но не туго Bound известен исходной структурой данных. [3] [6]
Хотя асимптотическая производительность парных куч хуже, чем у других алгоритмов очереди с приоритетами, таких как кучи Фибоначчи , которые выполняют уменьшение ключа в амортизированное время, производительность на практике отличная. Джонс [9] и Ларкин, Сен и Тарьян [10] проводил эксперименты по объединению куч и других структур данных кучи. Они пришли к выводу, что d-арные кучи, такие как двоичные кучи, работают быстрее, чем все другие реализации кучи, когда операция уменьшения ключа не требуется (и, следовательно, нет необходимости внешне отслеживать расположение узлов в куче), но что при уменьшении -ключ. Требуется Парные кучи часто работают быстрее, чем d-арные кучи, и почти всегда быстрее, чем другие кучи на основе указателей, включая структуры данных, такие как кучи Фибоначчи , которые теоретически более эффективны. Чен и др. [11] исследовал очереди приоритетов специально для использования с алгоритмом Дейкстры и пришел к выводу, что в обычных случаях использование d-арной кучи без ключа уменьшения (вместо дублирования узлов в куче и игнорирования избыточных экземпляров) приводит к повышению производительности, несмотря на худшие теоретические гарантии производительности.
Структура [ править ]
Куча спаривания — это либо пустая куча, либо дерево спаривания, состоящее из корневого элемента и, возможно, пустого списка деревьев спаривания. Свойство упорядочения кучи требует, чтобы родительский элемент любого узла был не больше самого узла. Следующее описание предполагает чисто функциональную кучу, которая не поддерживает операцию уменьшения ключа .
тип PairingTree[Elem] = Куча(elem: Elem, подкучи: List[PairingTree[Elem]]) введите PairingHeap[Elem] = Empty | СопряжениеДерево[Элем]
Реализация на основе указателей для машин с оперативной памятью , поддерживающая уменьшение ключа , может быть достигнута с использованием трех указателей на каждый узел, представляя дочерние элементы узла двусвязным списком : указатель на первого дочернего узла узла, один на его следующего родственного брата. и один — его предыдущему брату (или, если самый левый брат, его родителю). Его также можно рассматривать как вариант двоичного дерева с левым дочерним и правым сестринским элементом с дополнительным указателем на родителя узла (который представляет его предыдущего родственного узла или фактического родителя для самого левого родственного узла). Альтернативно, указатель предыдущего элемента можно опустить, позволив последнему дочернему элементу указывать обратно на родительский элемент, если добавлен один логический флаг, обозначающий «конец списка». Это обеспечивает более компактную структуру за счет постоянного коэффициента накладных расходов на каждую операцию. [1]
Операции [ править ]
Слиться [ править ]
Объединение с пустой кучей возвращает другую кучу, в противном случае возвращается новая куча, имеющая минимум из двух корневых элементов в качестве корневого элемента и просто добавляющая кучу с большим корнем в список подкуч:
функция meld(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] если куча1 пуста вернуть кучу2 elsif heap2 пуст вернуть кучу1 elsif heap1.elem < heap2.elem return Heap(heap1.elem, heap2 :: heap1.subheaps) иначе return Heap(heap2.elem, heap1 :: heap2.subheaps)
Вставить [ править ]
Самый простой способ вставить элемент в кучу — объединить кучу с новой кучей, содержащей только этот элемент и пустой список подкуч:
функция вставки(elem: Elem, куча: PairingHeap[Elem]) -> PairingHeap[Elem] return meld(Куча(elem, []), куча)
Найти-мин [ править ]
Функция find-min просто возвращает корневой элемент кучи:
функция find-min(куча: PairingHeap[Elem]) -> Elem если куча пуста ошибка иначе вернуть кучу.елем
Удалить-мин [ изменить ]
Единственная нетривиальная фундаментальная операция — удаление минимального элемента из кучи. Это требует выполнения повторных объединений дочерних элементов до тех пор, пока не останется только одно дерево. Стандартная стратегия сначала объединяет подкучи в пары (это шаг, который дал название этой структуре данных) слева направо, а затем объединяет результирующий список куч справа налево:
функция delete-min(куча: PairingHeap[Elem]) -> PairingHeap[Elem] если куча пуста ошибка , иначе верните пары слияния (куча.подкучи)
При этом используется вспомогательная функция merge-pairs :
функция merge-pairs(list: List[PairingTree[Elem]]) -> PairingHeap[Elem] если длина (список) == 0 вернуть Пусто длина elsif (список) == 1 список возврата [0] иначе return meld(meld(list[0], list[1]), merge-pairs(list[2..]))
То, что это действительно реализует описанную стратегию слияния с двумя проходами слева направо, а затем справа налево, можно увидеть из этого сокращения:
пары слияния ([H1, H2, H3, H4, H5, H6, H7])=> meld(meld(H1, H2), слияние пар([H3, H4, H5, H6, H7])) # объединяем H1 и H2 с H12, затем оставшуюся часть списка=> объединение( H12 , объединение(объединение(H3, H4), объединение пар([H5, H6, H7]))) # объединить H3 и H4 с H34, а затем остальную часть списка=> объединить(H12, объединить( H34 , объединить(объединить(H5, H6), объединить пары([H7])))) # объединить H5 и H6 с H56, а затем оставшуюся часть списка=> объединить(H12, объединить(H34, объединить( H56 , H7))) # переключить направление, объединить две последние получившиеся кучи, получив H567=> объединить (H12, объединить (H34, H567 )) # объединяем две последние кучи, получая H34567=> объединить (H12, H34567 ) # наконец, объединяем первую пару с результатом слияния остальных=> H1234567
Сводка времени работы [ править ]
Вот временные сложности [12] различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. .
| Операция | найти-мин | удаление-мин | вставлять | клавиша уменьшения | сливаться |
|---|---|---|---|---|---|
| Двоичный [12] | я (1) | Θ (логарифм n ) | О (логарифм n ) | О (логарифм n ) | Θ ( н ) |
| Левый | я (1) | Θ (логарифм n ) | Θ (логарифм n ) | О (логарифм n ) | Θ (логарифм n ) |
| Биномиальный [12] [13] | я (1) | Θ (логарифм n ) | я (1) [а] | Θ (логарифм n ) | О (логарифм n ) |
| Наклонный бином [14] | я (1) | Θ (логарифм n ) | я (1) | Θ (логарифм n ) | О (логарифм n ) [б] |
| Сопряжение [3] | я (1) | О (логарифм n ) [а] | я (1) | о (логарифм n ) [а] [с] | я (1) |
| Сопряжение по рангам [17] | я (1) | О (логарифм n ) [а] | я (1) | я (1) [а] | я (1) |
| Фибоначчи [12] [18] | я (1) | О (логарифм n ) [а] | я (1) | я (1) [а] | я (1) |
| Строгий Фибоначчи [19] | я (1) | О (логарифм n ) | я (1) | я (1) | я (1) |
| Мостовая долина [20] [д] | я (1) | О (логарифм n ) | я (1) | я (1) | я (1) |
| 2–3 кучи [22] | я (1) | О (логарифм n ) [а] | я (1) [а] | я (1) | О (логарифм n ) |
- ^ Перейти обратно: а б с д и ж г час я Амортизированное время.
- ^ в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).
- ^ Нижняя граница [15] верхняя граница [16]
- ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается.Кучи с n элементами могут быть построены снизу вверх за O ( n ). [21]
Ссылки [ править ]
- ^ Перейти обратно: а б с Фредман, Майкл Л .; Седжвик, Роберт ; Слитор, Дэниел Д .; Тарьян, Роберт Э. (1986). «Парная куча: новая форма саморегулирующейся кучи» (PDF) . Алгоритмика . 1 (1–4): 111–129. дои : 10.1007/BF01840439 . S2CID 23664143 .
- ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF) . Спрингер. п. 231.
- ^ Перейти обратно: а б с Яконо, Джон (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 г.
- ^ Перейти обратно: а б Петти, Сет (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: дата и год ( ссылка ) - ^ Перейти обратно: а б с д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (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).
- Пейринг кучи , Сартадж Сахни