Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Кучи сопряжения
Типкуча
Изобретенный1986 г.
ИзобретенныйМайкл Л. Фредман, Роберт Седжвик, Дэниел Слейтор и Роберт Эндре Тарджан
Сложность времени в большой нотации O
АлгоритмВ среднемХудший случай
ВставлятьΘ (1)
Find-minΘ (1) 
Удалить мин.O (журнал n ) 
Клавиша уменьшенияO (журнал n )
ОбъединитьΘ (1) 

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

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

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

Когда также добавляется операция уменьшения ключа , определение точного асимптотического времени работы парных куч оказалось затруднительным. Первоначально на эмпирических основаниях предполагалось, что временная сложность этой операции составляет O (1) , [4], но Фредман доказал, что амортизированное время на клавишу уменьшения составляет по крайней мере для некоторых последовательностей операций. [5] Используя другой аргумент амортизации, Петти затем доказал, что вставка , объединение и уменьшение ключа выполняются в течение амортизированного времени, то есть . [6]Позже Элмасри представил разработки парных куч (ленивый, консолидированный), для которых прогоны с уменьшением ключа за амортизированное время и другие операции имеют оптимальные амортизированные границы [7] [8], но точные границы для исходной структуры данных неизвестны. [3] [6]

Хотя асимптотическая производительность объединения куч хуже, чем у других алгоритмов очередей с приоритетом, таких как кучи Фибоначчи , которые выполняют функцию уменьшения ключа за амортизированное время, на практике производительность превосходна. Джонс [9] и Ларкин, Сен и Тарджан [10] провели эксперименты по объединению куч и других структур данных кучи. Они пришли к выводу, что динамические кучи, такие как двоичные кучи, работают быстрее, чем все другие реализации кучи, когда операция уменьшения ключа не требуется (и, следовательно, нет необходимости извне отслеживать местоположение узлов в куче), но что при уменьшении -ключнеобходимо сопряжение кучи часто быстрее, чем d-ary кучи, и почти всегда быстрее, чем другие кучи на основе указателей, включая структуры данных, такие как кучи Фибоначчи , которые теоретически более эффективны. Chen et al. [11] исследовали приоритетные очереди специально для использования с алгоритмом Дейкстры и пришли к выводу, что в обычных случаях использование динамической кучи без ключа уменьшения (вместо дублирования узлов в куче и игнорирования избыточных экземпляров) приводит к лучшей производительности, несмотря на худшую теоретическую производительность. гарантии.

Структура [ править ]

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

type PairingTree [Elem] = Куча (elem: Elem, subheaps: List [PairingTree [Elem]]) тип PairingHeap [Elem] = Пусто | PairingTree [Elem]

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

Операции [ править ]

find-min [ править ]

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

function find-min (heap: PairingHeap [Elem]) -> Elem, если куча пуста, ошибка  иначе  вернуть heap.elem

объединить [ править ]

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

function meld (heap1, heap2: PairingHeap [Elem]) -> PairingHeap [Elem], если heap1 пуста 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)

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

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

функция insert (elem: Elem, heap: PairingHeap [Elem]) -> PairingHeap [Elem] return meld (Heap (elem, []), heap)

delete-min [ редактировать ]

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

функция delete-min (heap: PairingHeap [Elem]) -> PairingHeap [Elem], если куча пуста, ошибка  иначе  возвращает пары слияния (heap.subheaps)

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

функция слияния пар (список: List [PairingTree [Elem]]) -> PairingHeap [Elem] if length (list) == 0 return Empty elsif length (list) == 1 return list [0] else  return meld (meld ( список [0], список [1]), пары слияния (список [2 ..]))

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

 пары слияния ([H1, H2, H3, H4, H5, H6, H7])=> объединить (объединить (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 )" и " thetas ; ( е )" см Big O нотацию .

Операцияfind-mindelete-minвставлятьклавиша уменьшенияобъединить
Двоичный [12]Θ (1)Θ (журнал  n )O (журнал  n )O (журнал  n )Θ ( п )
ЛевыйΘ (1)Θ (журнал n )Θ (журнал n )O (журнал n )Θ (журнал n )
Биномиальный [12] [13]Θ (1)Θ (журнал n )Θ (1) [а]Θ (журнал n )O (log  n ) [b]
Фибоначчи [12] [14]Θ (1)O (log  n ) [a]Θ (1)Θ (1) [а]Θ (1)
Сопряжение [3]Θ (1)O (log n ) [a]Θ (1)о (журнал  п ) [а] [с]Θ (1)
Бродал [17] [d]Θ (1)O (журнал  n )Θ (1)Θ (1)Θ (1)
Ранговые пары [19]Θ (1)O (log n ) [a]Θ (1)Θ (1) [а]Θ (1)
Строгий Фибоначчи [20]Θ (1)O (журнал n )Θ (1)Θ (1)Θ (1)
2–3 кучи [21]O (журнал n )O (log n ) [a]O (log n ) [a]Θ (1)?
  1. ^ a b c d e f g h i Амортизированное время.
  2. ^ n - размер большей кучи.
  3. ^ Нижняя оценка [15] верхняя оценка [16]
  4. ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). [18]

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

  1. ^ a b c Фредман, Майкл Л .; Седжвик, Роберт ; Слейтор, Дэниел Д .; Тарджан, Роберт Э. (1986). «Кучка сопряжения: новая форма саморегулирующейся кучи» (PDF) . Алгоритмика . 1 (1–4): 111–129. DOI : 10.1007 / BF01840439 . S2CID  23664143 .
  2. ^ Мельхорн, Курт ; Сандерс, Питер (2008). Алгоритмы и структуры данных: Basic Toolbox (PDF) . Springer. п. 231.
  3. ^ a b c Яконо, Джон (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
  4. ^ Стаско, Джон Т .; Виттер, Джеффри С. (1987), "спаривание куч: эксперименты и анализ" (PDF) , коммуникации ACM , 30 (3): 234-249, CiteSeerX 10.1.1.106.2988 , DOI : 10,1145 / 214748,214759 , S2CID 17811811   
  5. ^ Фредман, Майкл Л. (1999). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал ACM . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 . S2CID 16115266 . Архивировано из оригинального (PDF) 21 июля 2011 года . Проверено 3 мая 2011 .  
  6. ^ a b Петти, Сет (2005), «К окончательному анализу парных куч» (PDF) , Proc. Сорок шестой ежегодный IEEE симпозиум по Основы информатики (PDF) ., Стр 174-183, DOI : 10,1109 / SFCS.2005.75 , ISBN  0-7695-2468-0, S2CID  2717102
  7. ^ Элмасри, Амр (2009), «Соединение куч с O (log log n ) снижает стоимость» (PDF) , Proc. 20-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 471–476, CiteSeerX 10.1.1.502.6706 , doi : 10.1137 / 1.9781611973068.52  
  8. ^ Elmasry, Амр (ноябрь 2017). «К оптимальным саморегулирующимся отвалам» . ACM-транзакции по алгоритмам . 13 (4): 1–14. DOI : 10.1145 / 3147138 . S2CID 1182235 . 
  9. ^ Джонс, Дуглас В. (1986). «Эмпирическое сравнение реализаций очередей с приоритетами и наборов событий». Коммуникации ACM . 29 (4): 300–311. CiteSeerX 10.1.1.117.9380 . DOI : 10.1145 / 5684.5686 . S2CID 43650389 .  
  10. ^ Ларкин, Дэниел Х .; Сен, Сиддхартха; Тарьян, Роберт Э. (2014), «Эмпирическое исследование приоритетных очередей на основе основ», Труды 16-го семинара по разработке алгоритмов и экспериментам , стр. 61–72, arXiv : 1403.0252 , doi : 10.1137 / 1.9781611973198. 7 , S2CID 15216766 
  11. ^ Чен, Мо; Чоудхури, Резаул Алам; Рамачандран, Виджая; Рош, Дэвид Лан; Тонг, Линглинг (12 октября 2007 г.). Приоритетные очереди и алгоритм Дейкстры (PDF) (Технический отчет). Техасский университет. ТР-07-54. CS1 maint: дата и год ( ссылка )
  12. ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
  13. ^ "Биномиальная куча | Блестящая математика и наука вики" . brilliant.org . Проверено 30 сентября 2019 .
  14. ^ Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .  
  15. ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .
  16. ^ Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. С. 174–183. CiteSeerX 10.1.1.549.471 . DOI : 10.1109 / SFCS.2005.75 . ISBN   0-7695-2468-0.
  17. ^ Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
  18. ^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
  19. ^ Haeupler, Бернхард; Сен, Сиддхартха; Тарджан, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .
  20. ^ Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN   978-1-4503-1245-5.
  21. ^ Такаок, Тадао (1999), Теория 2-3 куч (PDF) , стр. 12

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

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