Очередь Бродала

редактировать

В информатика, очередь Бродала - это структура куча / очередь приоритета с очень низким худшим случаем временем границы : $O (1) {\ displaystyle O (1)}$ $O (1)$ для вставки, минимального поиска, объединения (слияние двух очередей) и клавиши уменьшения и $O (журнал (n)) {\ displaystyle O (\ mathrm {log} (n))}$ $O (\ mathrm {log} (n))$ для минимального удаления и общего удаления. Это первый кучный вариант, позволяющий достичь этих пределов, не прибегая к амортизации эксплуатационных расходов. Очереди Бродала названы в честь их изобретателя Герта Стёльтинга Бродала.

Имея лучшие асимптотические границы, чем другие структуры приоритетных очередей, они, по словам самого Бродала, «довольно сложны» и «[не] применимы на практике. " Бродал и Окасаки описывают постоянную (чисто функциональную ) версию очередей Бродала.

Сводка времени работы

Здесь временные сложности различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение «O (f)» и «Θ (f)» см. В нотации Big O.

Operation	find-min	delete-min	вставить	кнопка уменьшения	объединить
двоичный	Θ (1)	Θ (log n)	O (log n)	O (log n)	Θ (n)
Левый	Θ (1)	Θ (log n)	Θ (log n)	O (log n)	Θ (log n)
Биномиальный	Θ (1)	Θ (log n)	Θ(1)	Θ (log n)	O (log n)
Фибоначчи	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Сопряжение	Θ (1)	O (журнал n)	Θ (1)	o (журнал n)	Θ (1)
Brodal	Θ (1)	O (журнал n)	Θ (1)	Θ (1)	Θ (1)
	Θ (1)	O (log n)	Θ (1)	Θ(1)	Θ (1)
Строгий Фибоначчи	Θ (1)	O (журнал n)	Θ (1)	Θ (1)	Θ (1)
2-3 куча	O (log n)	O (log n)	O (log n)	Θ (1)	?

Ссылки

^ Герт Стёльтинг Бродал (1996). Очереди с приоритетом наихудшего случая. Proc. 7-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 52–58.
^Герт Стёльтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные очереди с приоритетом. Журнал функционального программирования.
^ Кормен, Томас Х. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
^«Биномиальная куча | Блестящая вики по математике и науке». brilliant.org. Проверено 30 сентября 2019 г.
^Фредман, Майкл Лоуренс ; Тарджан, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF). Журнал Ассоциации вычислительной техники. 34(3): 596–615. CiteSeerX 10.1.1.309.8927. doi : 10.1145 / 28869.28874.
^Иаконо, Джон (2000), «Улучшенные верхние границы для парных куч», Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, 1851, Springer-Verlag, pp. 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