Широкая очередь

Широкая очередь
Широкая очередь
Тип	Куча / приоритетная очередь
Изобретенный	1996
Изобретён	Герт Столтинг Бродал
Операция
Временная сложность в обозначении большого О
Операция	Средний
Пространственная сложность

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

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

Сводка времени работы [ править ]

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

Операция	найти-мин	удаление-мин	вставлять	клавиша уменьшения	сливаться
Двоичный ^[3]	я (1)	Θ (логарифм n )	О (логарифм n )	О (логарифм n )	Θ ( н )
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	О (логарифм n )	Θ (логарифм n )
Биномиальный ^[3]^[4]	я (1)	Θ (логарифм n )	я (1) ^[а]	Θ (логарифм n )	О (логарифм n )
Наклонный бином ^[5]	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О (логарифм n ) ^[б]
Сопряжение ^[6]	я (1)	О (логарифм n ) ^[а]	я (1)	о (логарифм n ) ^[а]^[с]	я (1)
Сопряжение по рангам ^[9]	я (1)	О (логарифм n ) ^[а]	я (1)	я (1) ^[а]	я (1)
Фибоначчи ^[3]^[10]	я (1)	О (логарифм n ) ^[а]	я (1)	я (1) ^[а]	я (1)
Строгий Фибоначчи ^[11]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
Мостовая долина ^[12]^[д]	я (1)	О (логарифм n )	я (1)	я (1)	я (1)
2–3 кучи ^[14]	я (1)	О (логарифм n ) ^[а]	я (1) ^[а]	я (1)	О (логарифм n )

↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Амортизированное время.
^ в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).
^ Нижняя граница $\Omega (\log \log n),$ ^[7] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[8]
^ Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается.Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[13]

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

↑ Перейти обратно: Перейти обратно: ^а ^б Герт Столтинг Бродал (1996). Эффективные приоритетные очереди в худшем случае. Учеб. 7-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 52–58.
^ Герт Столтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные очереди с приоритетами . Журнал функционального программирования.
↑ Перейти обратно: Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (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
^ Яконо, Джон (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. дои : 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

Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее .

[amortized-5] Перейти обратно: Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Амортизированное время.

[7] в наихудшем случае Бродал и Окасаки описывают метод уменьшения сложности объединения до Θ (1); этот метод применим к любой структуре данных кучи, которая имеет вставку в Θ (1) и find-min , delete-min , объединение в O (log n ).

[pairingdecreasekey-11] Нижняя граница $\Omega (\log \log n),$ ^[7] верхняя граница $O(2^{2{\sqrt {\log \log n}}}).$ ^[8]

[brodal-17] Бродал и Окасаки позже описывают постоянный вариант с теми же границами, за исключением клавиши уменьшения, которая не поддерживается.Кучи с n элементами могут быть построены снизу вверх за O ( n ). ^[13]

[Brodal-1] Перейти обратно: Перейти обратно: ^а ^б Герт Столтинг Бродал (1996). Эффективные приоритетные очереди в худшем случае. Учеб. 7-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 52–58.

[BrodalOkasaki-2] Герт Столтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные очереди с приоритетами . Журнал функционального программирования.

[CLRS-3] Перейти обратно: Перейти обратно: ^а ^б ^с ^д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8 .

[4] «Биномиальная куча | Блестящая вики по математике и естественным наукам» . блестящий.орг . Проверено 30 сентября 2019 г.

[6] Бродал, Герт Столтинг; Окасаки, Крис (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди приоритетов», Journal of Functional Programming , 6 (6): 839–857, doi : 10.1017/s095679680000201x

[Iacono-8] Яконо, Джон (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

[Fredman1999-9] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности объединения куч и связанных структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473–501. дои : 10.1145/320211.320214 .

[10] Петти, Сет (2005). К окончательному анализу парных куч (PDF) . FOCS '05 Материалы 46-го ежегодного симпозиума IEEE по основам информатики. стр. 174–183. CiteSeerX 10.1.1.549.471 . дои : 10.1109/SFCS.2005.75 . ISBN 0-7695-2468-0 .

[12] Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485. дои : 10.1137/100785351 .

[Fredman_And_Tarjan-13] Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596–615. CiteSeerX 10.1.1.309.8927 . дои : 10.1145/28869.28874 .

[14] Бродал, Герт Столтинг ; Лагояннис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Материалы 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184. CiteSeerX 10.1.1.233.1740 . дои : 10.1145/2213977.2214082 . ISBN 978-1-4503-1245-5 .

[15] Бродал, Герт С. (1996), «Эффективные приоритетные очереди для наихудшего случая» (PDF) , Proc. 7-й ежегодный симпозиум ACM-SIAM по дискретным алгоритмам , стр. 52–58.

[16] Гудрич, Майкл Т .; Тамассия, Роберто (2004). «7.3.6. Построение кучи снизу вверх». Структуры данных и алгоритмы в Java (3-е изд.). стр. 338–341. ISBN 0-471-46983-1 .

[18] Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12

[1]

[2]

[3]

[4]

[а]

[5]

[б]

[6]

[с]

[9]

[10]

[11]

[12]

[д]

[14]

[7]

[8]

[13]