Куча Бродала-Окасаки — различия между версиями
Kris (обсуждение | вклад) |
м (rollbackEdits.php mass rollback) |
||
(не показано 67 промежуточных версий 10 участников) | |||
Строка 1: | Строка 1: | ||
− | '''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и | + | '''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и на идее Data-structural bootstrapping. Первое позволяет делать <math>\mathrm{insert}</math> за <tex>O(1)</tex>, второе позволяет получать минимальный элемент за <tex>O(1)</tex>, а третье {{---}} позволяющей выполнить <math>\mathrm{merge}</math> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей. |
== Структура == | == Структура == | ||
− | + | Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping. | |
− | Используем | ||
{{Определение | {{Определение | ||
|neat = 0 | |neat = 0 | ||
− | |definition= | + | |definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь. |
}} | }} | ||
Строка 13: | Строка 12: | ||
+ | Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>: | ||
− | + | <code> | |
− | + | '''BPQ''' = '''<int, PQ'''('''BPQ''')'''>''' | |
− | + | </code> | |
− | Куча из одного элемента | + | Куча из одного элемента создается так: |
− | < | + | <code> |
+ | '''BPQ''' singleton'(x:'''int'''): | ||
+ | '''return''' <x, null> | ||
+ | </code> | ||
− | Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}</tex> | + | Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex> |
== Операции == | == Операции == | ||
=== Merge === | === Merge === | ||
− | Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и | + | Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex>. Этот элемент и станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <math>\mathrm{insert}</math>. |
− | < | + | <code> |
− | merge( | + | '''BPQ''' merge('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''): |
− | + | '''if''' x < y | |
− | + | '''return''' <x, insert(q, <y, r>)> | |
− | + | '''else''' | |
− | + | '''return''' <y, insert(r, <x, q>)> | |
− | </ | + | </code> |
− | Здесь < | + | Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь. Если оно работает за <tex>O(1)</tex>, то <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>. |
+ | |||
=== Insert === | === Insert === | ||
− | Это создание нового | + | Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом. |
− | < | + | <code> |
− | insert( | + | '''BPQ''' insert('''<'''x:'''int''', q:'''PQ>''', y:'''int'''): |
− | + | '''return''' merge(<x, q>, singleton(y)) | |
− | </ | + | </code> |
− | + | По сути операция <math>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</math>: создается дерево нулевого ранга за <tex>O(1)</tex>, а затем оно сливается с основным также за <tex>O(1)</tex>. | |
+ | |||
=== getMin === | === getMin === | ||
− | Выполняется просто, так как | + | Выполняется просто, так как <tex> BPQ </tex> хранит минимум. |
− | < | + | <code> |
− | getMin( | + | '''int''' getMin('''<'''x:'''int''', q:'''PQ>'''): |
− | + | '''return''' x | |
− | </ | + | </code> |
+ | Очевидно, работает за <tex>O(1)</tex>. | ||
=== extractMin === | === extractMin === | ||
− | Минимальный элемент хранится в верхнем | + | Минимальный элемент хранится в верхнем <tex> BPQ </tex>, поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>. |
− | < | + | <code> |
− | extractMin( | + | '''<int, BPQ>''' extractMin('''<'''x:'''int''', q:'''PQ>'''): |
− | + | <<y, r>, t> = extractMin(q) | |
− | + | '''return''' <x, <y, merge(r, t)>> | |
− | </ | + | </code> |
− | Здесь < | + | Здесь <math>\mathrm{extractMin}</math> {{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>\langle y,r \rangle</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. Соответственно, <math>\mathrm{merge}</math> {{---}} функция, выполняющая слияние двух приоритетных очередей. |
− | Возвращаем | + | Возвращаем минимум и <tex> BPQ </tex>, где <tex>x</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}(r,t)</math> {{---}} приоритетная очередь без элементов <tex>x</tex> и <tex>y</tex>. |
− | Так как < | + | Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, то <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>. |
== Смотри также == | == Смотри также == | ||
Строка 68: | Строка 74: | ||
* [[Персистентная приоритетная очередь]] | * [[Персистентная приоритетная очередь]] | ||
− | == | + | == Источники информации == |
− | [http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям] | + | * [http://www.lektorium.tv/lecture/?id=14234 Lektorium {{---}} Лекция А.С. Станкевича по приоритетным очередям] |
− | [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues] | + | * [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.48.973 Optimal Purely Functional Priority Queues] |
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
[[Категория: Приоритетные очереди]] | [[Категория: Приоритетные очереди]] |
Текущая версия на 19:29, 4 сентября 2022
Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) — основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и на идее Data-structural bootstrapping. Первое позволяет делать за , второе позволяет получать минимальный элемент за , а третье — позволяющей выполнить за . Удаление минимума работает за в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
Содержание
Структура
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по :
BPQ = <int, PQ(BPQ)>
Куча из одного элемента создается так:
BPQ singleton'(x:int): return <x, null>
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений
Операции
Merge
Слияние выполняется выбором минимума из двух значений
BPQ merge(<x:int, q:PQ>, <y:int, r:PQ>): if x < y return <x, insert(q, <y, r>)> else return <y, insert(r, <x, q>)>
Здесь
это добавление в приоритетную очередь. Если оно работает за , то работает за .Insert
Это создание нового
BPQ insert(<x:int, q:PQ>, y:int): return merge(<x, q>, singleton(y))
По сути операция
- тот же самый : создается дерево нулевого ранга за , а затем оно сливается с основным также за .getMin
Выполняется просто, так как
int getMin(<x:int, q:PQ>): return x
Очевидно, работает за
.extractMin
Минимальный элемент хранится в верхнем
<int, BPQ> extractMin(<x:int, q:PQ>): <<y, r>, t> = extractMin(q) return <x, <y, merge(r, t)>>
Здесь
— это функция, извлекающая минимальный элемент типа из приоритетной очереди, она возвращает — минимальный элемент типа и остаток от приоритетной очереди после извлечение минимума — . Соответственно, — функция, выполняющая слияние двух приоритетных очередей.Возвращаем минимум и
, где — новый минимальный элемент, и — приоритетная очередь без элементов и .Так как
и выполняются за , то выполняется за .