В информатике , то Бродал очередь это куча / приоритетная очередь структура с очень низким худшем случае время по часам : для вставки, найти-минимум, объединить (объединить две очереди) и уменьшить ключ и для минимального удаления и общего удаления. Это первый навороченный вариант, позволяющий достичь этих пределов, не прибегая к амортизации операционных затрат. Очереди Brodal названы в честь их изобретателя Герта Стёльтинга Бродала . [1]
Имея лучшие асимптотические границы, чем другие структуры очередей с приоритетами, они, по словам самого Бродала, «довольно сложны» и «[не] применимы на практике». [1] Бродал и Окасаки описывают постоянную ( чисто функциональную ) версию очередей Бродала. [2]
Сводка времени работы
Вот временные сложности [3] различных структур данных кучи. Имена функций предполагают минимальную кучу. Для значения " O ( F )" и " thetas ; ( е )" см Big O нотацию .
Операция | find-min | delete-min | вставлять | клавиша уменьшения | объединить |
---|---|---|---|---|---|
Двоичный [3] | Θ (1) | Θ (журнал n ) | O (журнал n ) | O (журнал n ) | Θ ( п ) |
Левый | Θ (1) | Θ (журнал n ) | Θ (журнал n ) | O (журнал n ) | Θ (журнал n ) |
Биномиальный [3] [4] | Θ (1) | Θ (журнал n ) | Θ (1) [а] | Θ (журнал n ) | O (log n ) [b] |
Фибоначчи [3] [5] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [а] | Θ (1) |
Спаривание [6] | Θ (1) | O (log n ) [a] | Θ (1) | о (журнал п ) [а] [с] | Θ (1) |
Бродал [9] [d] | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
Сочетание рангов [11] | Θ (1) | O (log n ) [a] | Θ (1) | Θ (1) [а] | Θ (1) |
Строгий Фибоначчи [12] | Θ (1) | O (журнал n ) | Θ (1) | Θ (1) | Θ (1) |
2–3 кучи [13] | O (журнал n ) | O (log n ) [a] | O (log n ) [a] | Θ (1) | ? |
- ^ a b c d e f g h i Амортизированное время.
- ^ n - размер большей кучи.
- ^ Нижняя граница[7] верхняя граница[8]
- ^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением ключа уменьшения, который не поддерживается. Кучи с n элементами могут быть построены снизу вверх за O ( n ). [10]
Рекомендации
- ^ a b Герт Стёльтинг Бродал (1996). Очереди с приоритетом наихудшего случая. Proc. 7-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 52–58.
- ^ Герт Стёлтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные приоритетные очереди . Журнал функционального программирования.
- ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
- ^ "Бином Heap | Brilliant Math & Science Wiki" . brilliant.org . Проверено 30 сентября 2019 .
- ^ Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . DOI : 10.1145 / 28869.28874 .
- ^ Яконо, Джон (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
- ^ Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. DOI : 10.1145 / 320211.320214 .
- ^ Петти, Сет (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.
- ^ Бродал, Герт С. (1996), "Эффективные приоритетные очереди наихудшего случая" (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.
- ^ Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Строительство кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341. ISBN 0-471-46983-1.
- ^ Хёуплер, Бернхард; Сен, Сиддхартха; Тарджан, Роберт Э. (ноябрь 2011 г.). "Куча ранговых пар" (PDF) . SIAM J. Computing . 40 (6): 1463–1485. DOI : 10.1137 / 100785351 .
- ^ Бродал, Герт Стёльтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740 . DOI : 10.1145 / 2213977.2214082 . ISBN 978-1-4503-1245-5.
- ^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12