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

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

Оптимальная структура данных для операций приоритетной очереди

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

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

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

Вот временные сложности ^[3] различных структур данных кучи. Сокращение am. указывает на то, что данная сложность амортизирована, в противном случае это сложность наихудшего случая. Для значения " O ( f )" и " Θ ( f )" см . нотацию Big O. Имена операций предполагают минимальную кучу.

Операция	найти-мин	удалить-мин	клавиша уменьшения	вставлять	сливаться	сделать-кучу ^[а]
Двоичный ^[3]	Θ (1)	Θ (log n )	Θ (log n )	Θ (log n )	Θ ( н )	Θ ( н )
Наклон ^[4]	Θ (1)	О (лог н ) утра.	О (лог н ) утра.	О (лог н ) утра.	О (лог н ) утра.	Θ ( н ) ам.
Левый ^[5]	Θ (1)	Θ (log n )	Θ (log n )	Θ (log n )	Θ (log n )	Θ ( н )
Биномиальный ^[3]^[7]	Θ (1)	Θ (log n )	Θ (log n )	Θ (1) утра.	Θ (log n ) ^[б]	Θ ( н )
Косой бином ^[8]	Θ (1)	Θ (log n )	Θ (log n )	Θ (1)	Θ (log n ) ^[б]	Θ ( н )
2–3 кучи ^[10]	Θ (1)	О (лог н ) утра.	Θ (1)	Θ (1) утра.	О (log n ) ^[б]	Θ ( н )
Перекос снизу вверх ^[4]	Θ (1)	О (лог н ) утра.	О (лог н ) утра.	Θ (1) утра.	Θ (1) утра.	Θ ( н ) ам.
Сопряжение ^[11]	Θ (1)	О (лог н ) утра.	о (log n ) am. ^[c]	Θ (1)	Θ (1)	Θ ( н )
Ранг-пары ^[14]	Θ (1)	О (лог н ) утра.	Θ (1) утра.	Θ (1)	Θ (1)	Θ ( н )
Фибоначчи ^[3]^[15]	Θ (1)	О (лог н ) утра.	Θ (1) утра.	Θ (1)	Θ (1)	Θ ( н )
Строгий Фибоначчи ^[16]^[d]	Θ (1)	Θ (log n )	Θ (1)	Θ (1)	Θ (1)	Θ ( н )
Бродал ^[17]^[д]	Θ (1)	Θ (log n )	Θ (1)	Θ (1)	Θ (1)	Θ ( н ) ^[18]

^ make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Она может быть выполнена за время Θ ( n ), когда meld выполняется за время O (log n ) (где обе сложности могут быть амортизированы). ^[4]^[5] Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[6]
^ abc Для постоянных куч (не поддерживающих reduce-key ) общее преобразование снижает стоимость meld до стоимости insert , в то время как новая стоимость delete-min является суммой старых стоимостей delete-min и meld . ^[9] Здесь это заставляет meld работать за Θ (1) время (амортизированное, если стоимость insert равна ), в то время как delete-min по-прежнему работает за O (log n ). Применительно к перекошенным биномиальным кучам это дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью в худшем случае. ^[8]
^ Нижняя граница ^[12] верхняя граница ^[13] $\Омега (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$
^ ab Очереди Бродала и строгие кучи Фибоначчи достигают оптимальных сложностей в худшем случае для куч. Они были впервые описаны как императивные структуры данных. Очередь Бродала-Окасаки — это постоянная структура данных, достигающая того же оптимума, за исключением того, что ключ уменьшения не поддерживается.

Герт Столтинг Бродал

Герт Столтинг Бродал — профессор Орхусского университета , Дания . ^[19] Он наиболее известен благодаря очереди Бродала.

Ссылки

^ ab Gerth Stølting Brodal (1996). Эффективные очереди с приоритетами в худшем случае. Труды 7-го симпозиума ACM-SIAM по дискретным алгоритмам, стр. 52–58
^ Герт Столтинг Бродал и Крис Окасаки (1996). Оптимальные чисто функциональные очереди с приоритетами. Журнал функционального программирования.
^ abcd Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. (1990). Введение в алгоритмы (1-е изд.). MIT Press и McGraw-Hill. ISBN 0-262-03141-8.
^ abc Sleator, Daniel Dominic ; Tarjan, Robert Endre (февраль 1986 г.). «Саморегулирующиеся кучи». SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN 0097-5397.
^ ab Tarjan, Robert (1983). "3.3. Левые кучи". Структуры данных и сетевые алгоритмы . С. 38–42 . doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.
^ Хейворд, Райан; МакДиармид, Колин (1991). "Анализ среднего случая построения кучи путем повторной вставки" (PDF) . J. Algorithms . 12 : 126– 153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Архивировано из оригинала (PDF) 2016-02-05 . Получено 2016-01-28 .
^ "Биномиальная куча | Brilliant Math & Science Wiki". brilliant.org . Получено 2019-09-30 .
^ ab Brodal, Gerth Stølting; Okasaki, Chris (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди с приоритетами», Journal of Functional Programming , 6 (6): 839–857 , doi : 10.1017/s095679680000201x
^ Окасаки, Крис (1998). "10.2. Структурная абстракция". Чисто функциональные структуры данных (1-е изд.). С. 158–162 . ISBN 9780521631242.
^ Такаока, Тадао (1999), Теория 2–3 куч (PDF) , стр. 12
^ Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Труды 7-го Скандинавского семинара по теории алгоритмов (PDF) , Lecture Notes in Computer Science, т. 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.
^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF) . Труды FOCS '05 46-го ежегодного симпозиума IEEE по основам компьютерной науки. стр. 174–183 . CiteSeerX 10.1.1.549.471 . doi :10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
^ Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485 . doi : 10.1137/100785351.
^ Фредман, Майкл Лоуренс ; Тарьян, Роберт Э. (июль 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах сетевой оптимизации» (PDF) . Журнал Ассоциации вычислительной техники . 34 (3): 596– 615. CiteSeerX 10.1.1.309.8927 . doi :10.1145/28869.28874.
^ Бродал, Герт Столтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (2012). Строгие кучи Фибоначчи (PDF) . Труды 44-го симпозиума по теории вычислений - STOC '12. стр. 1177–1184 . CiteSeerX 10.1.1.233.1740 . doi :10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
^ Бродал, Герт С. (1996), «Эффективные очереди с приоритетами в наихудшем случае» (PDF) , Труды 7-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 52–58
^ Гудрич, Майкл Т .; Тамассиа, Роберто (2004). "7.3.6. Построение кучи снизу вверх". Структуры данных и алгоритмы в Java (3-е изд.). С. 338–341 . ISBN 0-471-46983-1.
^ "Веб-сайт Герта Столтинга Бродала из Орхусского университета" . Проверено 18 февраля 2016 г.

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

[7] make-heap — это операция построения кучи из последовательности из n неотсортированных элементов. Она может быть выполнена за время Θ ( n ), когда meld выполняется за время O (log n ) (где обе сложности могут быть амортизированы). ^[4]^[5] Другой алгоритм достигает Θ ( n ) для двоичных куч. ^[6]

[bootstrap-meld-9] Для постоянных куч (не поддерживающих reduce-key ) общее преобразование снижает стоимость meld до стоимости insert , в то время как новая стоимость delete-min является суммой старых стоимостей delete-min и meld . ^[9] Здесь это заставляет meld работать за Θ (1) время (амортизированное, если стоимость insert равна ), в то время как delete-min по-прежнему работает за O (log n ). Применительно к перекошенным биномиальным кучам это дает очереди Бродала-Окасаки, постоянные кучи с оптимальной сложностью в худшем случае. ^[8]

[pairingdecreasekey-16] Нижняя граница ^[12] верхняя граница ^[13] $\Омега (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$

[optimum-20] Очереди Бродала и строгие кучи Фибоначчи достигают оптимальных сложностей в худшем случае для куч. Они были впервые описаны как императивные структуры данных. Очередь Бродала-Окасаки — это постоянная структура данных, достигающая того же оптимума, за исключением того, что ключ уменьшения не поддерживается.

[Brodal-1] Gerth Stølting Brodal (1996). Эффективные очереди с приоритетами в худшем случае. Труды 7-го симпозиума ACM-SIAM по дискретным алгоритмам, стр. 52–58

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

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

[sleator-tarjan-skew-4] Sleator, Daniel Dominic ; Tarjan, Robert Endre (февраль 1986 г.). «Саморегулирующиеся кучи». SIAM Journal on Computing . 15 (1): 52– 69. CiteSeerX 10.1.1.93.6678 . doi :10.1137/0215004. ISSN 0097-5397.

[tarjan-leftist-5] Tarjan, Robert (1983). "3.3. Левые кучи". Структуры данных и сетевые алгоритмы . С. 38–42 . doi :10.1137/1.9781611970265. ISBN 978-0-89871-187-5.

[hayward-mcdiarmid-heap-build-6] Хейворд, Райан; МакДиармид, Колин (1991). "Анализ среднего случая построения кучи путем повторной вставки" (PDF) . J. Algorithms . 12 : 126– 153. CiteSeerX 10.1.1.353.7888 . doi :10.1016/0196-6774(91)90027-v. Архивировано из оригинала (PDF) 2016-02-05 . Получено 2016-01-28 .

[8] "Биномиальная куча | Brilliant Math & Science Wiki". brilliant.org . Получено 2019-09-30 .

[brodal-okasaki-10] Brodal, Gerth Stølting; Okasaki, Chris (ноябрь 1996 г.), «Оптимальные чисто функциональные очереди с приоритетами», Journal of Functional Programming , 6 (6): 839–857 , doi : 10.1017/s095679680000201x

[11] Окасаки, Крис (1998). "10.2. Структурная абстракция". Чисто функциональные структуры данных (1-е изд.). С. 158–162 . ISBN 9780521631242.

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

[Iacono-13] Яконо, Джон (2000), «Улучшенные верхние границы для парных куч», Труды 7-го Скандинавского семинара по теории алгоритмов (PDF) , Lecture Notes in Computer Science, т. 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-14] Фредман, Майкл Лоуренс (июль 1999 г.). «Об эффективности парных куч и связанных с ними структур данных» (PDF) . Журнал Ассоциации вычислительной техники . 46 (4): 473– 501. doi :10.1145/320211.320214.

[15] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (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] Хёплер, Бернхард; Сен, Сиддхартха; Тарьян, Роберт Э. (ноябрь 2011 г.). «Кучи ранговых пар» (PDF) . СИАМ Дж. Компьютерные технологии . 40 (6): 1463–1485 . doi : 10.1137/100785351.

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

[19] Бродал, Герт Столтинг ; Лагогианнис, Джордж; Тарьян, Роберт Э. (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] Бродал, Герт С. (1996), «Эффективные очереди с приоритетами в наихудшем случае» (PDF) , Труды 7-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , стр. 52–58

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

[23] "Веб-сайт Герта Столтинга Бродала из Орхусского университета" . Проверено 18 февраля 2016 г.