WikiDer > Бродальская очередь
В Информатика, то Бродальская очередь это куча/приоритетная очередь структура с очень низким худший случай временные рамки: для вставки, найти-минимум, объединить (объединить две очереди) и уменьшить ключ и для минимального удаления и общего удаления. Это первый кучный вариант, позволяющий достичь этих пределов, не прибегая к амортизации эксплуатационных расходов. Очереди Brodal названы в честь их изобретателя Герт Стёльтинг Бродал.[1]
Имея лучшие асимптотические границы, чем другие структуры очередей с приоритетами, они, по словам самого Бродала, «довольно сложны» и «[не] применимы на практике».[1] Бродал и Окасаки описать настойчивый (чисто функциональный) версия очередей Бродала.[2]
Сводка времени работы
Вот временные сложности[3] различных структур данных кучи. Имена функций предполагают минимальную кучу. Для значения "О(ж)" и "Θ(ж)" видеть Обозначение Big O.
| Операция | find-min | delete-min | вставлять | клавиша уменьшения | объединить |
|---|---|---|---|---|---|
| Двоичный[3] | Θ(1) | Θ(бревноп) | О(бревноп) | О(бревноп) | Θ(п) |
| Левый | Θ(1) | Θ(бревно п) | Θ(бревно п) | О(бревно п) | Θ(бревно п) |
| Биномиальный[3][4] | Θ(1) | Θ(бревно п) | Θ(1)[а] | Θ(бревно п) | О(бревноп)[b] |
| Фибоначчи[3][5] | Θ(1) | О(бревноп)[а] | Θ(1) | Θ(1)[а] | Θ(1) |
| Сопряжение[6] | Θ(1) | О(бревно п)[а] | Θ(1) | о(бревноп)[а][c] | Θ(1) |
| Brodal[9][d] | Θ(1) | О(бревноп) | Θ(1) | Θ(1) | Θ(1) |
| Ранговые пары[11] | Θ(1) | О(бревно п)[а] | Θ(1) | Θ(1)[а] | Θ(1) |
| Строгий Фибоначчи[12] | Θ(1) | О(бревно п) | Θ(1) | Θ(1) | Θ(1) |
| 2–3 кучи[13] | О(бревно п) | О(бревно п)[а] | О(бревно п)[а] | Θ(1) | ? |
- ^ а б c d е ж грамм час я Амортизированное время.
- ^ п размер большей кучи.
- ^ Нижняя граница [7] верхняя граница [8]
- ^ Бродал и Окасаки позже описывают настойчивый вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается. п элементы могут быть построены снизу вверх в О(п).[10]
Рекомендации
- ^ а б Герт Стёльтинг Бродал (1996). Очереди с приоритетом наихудшего случая. Proc. 7-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 52–58.
- ^ Герт Стёлтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные очереди с приоритетом. Журнал функционального программирования.
- ^ а б c d Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
- ^ "Биномиальная куча | Блестящая вики по математике и науке". brilliant.org. Получено 2019-09-30.
- ^ Фредман, Майкл Лоуренс; Тарджан, Роберт Э. (Июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF). Журнал Ассоциации вычислительной техники. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. Дои:10.1145/28869.28874.
- ^ Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Proc. 7-й скандинавский семинар по теории алгоритмов (PDF), Конспект лекций по информатике, 1851, Springer-Verlag, стр. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, Дои:10.1007 / 3-540-44985-X_5, ISBN 3-540-67690-2
- ^ Фредман, Майкл Лоуренс (Июль 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.
- ^ Бродал, Герт С. (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. Дои:10.1137/100785351.
- ^ Бродал, Герт Стёльтинг; Лагогианнис, Джордж; Тарджан, Роберт Э. (2012). Строгие груды Фибоначчи (PDF). Материалы 44-го симпозиума по теории вычислений - STOC '12. С. 1177–1184. CiteSeerX 10.1.1.233.1740. Дои:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
- ^ Такаока, Тадао (1999), Теория 2–3 куч (PDF), п. 12
 | Этот алгоритмы или же структуры данных-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. |