Куча Бродала-Окасаки — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Смотри также)
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 6 участников)
Строка 1: Строка 1:
'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') {{---}} основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, что позволяет делать <tex>insert</tex> за <tex>O(1)</tex>, добавлении минимального элемента, позволяет получать минимальный элемент за <tex>O(1)</tex>, и идеи Data-structural bootstrapping, позволяющей выполнить <tex>merge</tex> за <tex>O(1)</tex>. Удаление минимума работает за <tex>O(\log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
+
'''Куча Бродала-Окасаки''' (англ. ''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> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
  
 
== Структура ==
 
== Структура ==
Строка 5: Строка 5:
 
{{Определение
 
{{Определение
 
|neat = 0
 
|neat = 0
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
+
|definition= '''Data-structural bootstrapping''' {{---}} это идея, позволяющая снизить время <math>\mathrm{merge}</math> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
 
}}
 
}}
  
Строка 12: Строка 12:
  
  
 +
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>:
  
Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента <tex>T_{min}</tex> и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по <tex>T_{min}</tex>. Это можно записать так:
+
<code>
 +
'''BPQ''' = '''<int, PQ'''('''BPQ''')'''>'''
 +
</code>
  
<tex> BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)</tex>
+
Куча из одного элемента создается так:
  
Куча из одного элемента будет выглядеть так
+
<code>
 +
'''BPQ''' singleton'(x:'''int'''):
 +
    '''return''' <x, null>
 +
</code>
  
<tex>create(x) = BPQ \left \langle x, null\right \rangle</tex>
+
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}.</tex>
 
 
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <tex>T_{min}</tex>.
 
  
 
== Операции ==
 
== Операции ==
 
=== Merge ===
 
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
+
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex>. Этот элемент и станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <math>\mathrm{insert}</math>.
 
<code>
 
<code>
  '''pair''' merge((x : '''int''', q : '''bpq''') : '''pair''', (y : '''int''', r : '''bpq''') : '''pair''')
+
  '''BPQ''' merge('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''):
    if x < y
+
    '''if''' x < y
         '''return''' (x, insert(q, (y, r)))
+
         '''return''' <x, insert(q, <y, r>)>
     else
+
     '''else'''
         '''return''' (y, insert(r, (x, q)))
+
         '''return''' <y, insert(r, <x, q>)>
 
</code>
 
</code>
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>.
+
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь. Если оно работает за <tex>O(1)</tex>, то <math>\mathrm{merge}</math> работает за <tex>O(1)</tex>.
  
 
=== Insert ===
 
=== Insert ===
Это создание нового BPQ и <tex>merge</tex> его с основным деревом.
+
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.
 
<code>
 
<code>
  '''pair(int, bpq)''' insert((x : '''int''', q : '''bpq'''), y : '''bpq''')
+
  '''BPQ''' insert('''<'''x:'''int''', q:'''PQ>''', y:'''int'''):
     return merge((x,q), create(y))
+
     '''return''' merge(<x, q>, singleton(y))
 
</code>
 
</code>
Создание и <tex>merge</tex> выполняются за <tex>O(1)</tex>, тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
+
По сути операция <math>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</math>: создается дерево нулевого ранга за <tex>O(1)</tex>, а затем оно сливается с основным также за <tex>O(1)</tex>.
  
 
=== getMin ===
 
=== getMin ===
Выполняется просто, так как BPQ хранит минимум.
+
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
 
<code>
 
<code>
  '''int''' getMin((x : '''int''', q : '''bpq'''))
+
  '''int''' getMin('''<'''x:'''int''', q:'''PQ>'''):
     return x;
+
     '''return''' x
 
</code>
 
</code>
Очевидно, работает за <tex>O(1)</tex>
+
Очевидно, работает за <tex>O(1)</tex>.
  
 
=== extractMin ===
 
=== extractMin ===
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.  
+
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.  
 
<code>
 
<code>
  '''pair (int, bpq)''' extractMin('''pair'''(x : '''int''', q : '''bpq'''))
+
  '''<int, BPQ>''' extractMin('''<'''x:'''int''', q:'''PQ>'''):
     ((y,r), t) = extractMin(q)
+
     <<y, r>, t> = extractMin(q)
'''return''' (y, merge(r, t))
+
    '''return''' <x, <y, merge(r, t)>>
</pre>
+
</code>
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.
+
Здесь <math>\mathrm{extractMin}</math> {{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>\langle y,r \rangle</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. Соответственно, <math>\mathrm{merge}</math> {{---}} функция, выполняющая слияние двух приоритетных очередей.
  
Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
+
Возвращаем минимум и <tex> BPQ </tex>, где <tex>x</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}(r,t)</math> {{---}} приоритетная очередь без элементов <tex>x</tex> и <tex>y</tex>.
  
Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(\log N)</tex>, тогда <tex>extractMin</tex> выполняется за <tex>O(\log N)</tex>.
+
Так как <math>\mathrm{extractMin}</math> и <math>\mathrm{merge}</math> выполняются за <tex>O(\log N)</tex>, то <math>\mathrm{extractMin}</math> выполняется за <tex>O(\log N)</tex>.
  
=== Смотри также ===
+
== Смотри также ==
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
 
* [[Очередь]]
 
* [[Очередь]]
Строка 71: Строка 75:
  
 
== Источники информации ==
 
== Источники информации ==
* [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. Первое позволяет делать [math]\mathrm{insert}[/math] за [math]O(1)[/math], второе позволяет получать минимальный элемент за [math]O(1)[/math], а третье — позволяющей выполнить [math]\mathrm{merge}[/math] за [math]O(1)[/math]. Удаление минимума работает за [math]O(\log N)[/math] в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

Структура

Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.

Определение:
Data-structural bootstrapping — это идея, позволяющая снизить время [math]\mathrm{merge}[/math] до [math]O(1)[/math] путем разрешения хранить в очереди другую очередь.




Создадим структуру Bootstrapping Priority Queues, которая будет хранить пару из минимального элемента [math]T_{min}[/math] и приоритетную очередь. Элементами приоритетной очереди будут Bootstrapping Priority Queues упорядоченные по [math]T_{min}[/math]:

BPQ = <int, PQ(BPQ)> 

Куча из одного элемента создается так:

BPQ singleton'(x:int):
    return <x, null>

Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений [math]T_{min}.[/math]

Операции

Merge

Слияние выполняется выбором минимума из двух значений [math]T_{min}[/math]. Этот элемент и станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции [math]\mathrm{insert}[/math].

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>)>

Здесь [math]\mathrm{insert}[/math] это добавление в приоритетную очередь. Если оно работает за [math]O(1)[/math], то [math]\mathrm{merge}[/math] работает за [math]O(1)[/math].

Insert

Это создание нового [math] BPQ [/math] и [math]\mathrm{merge}[/math] его с основным деревом.

BPQ insert(<x:int, q:PQ>, y:int):
    return merge(<x, q>, singleton(y))

По сути операция [math]\mathrm{insert}[/math] - тот же самый [math]\mathrm{merge}[/math]: создается дерево нулевого ранга за [math]O(1)[/math], а затем оно сливается с основным также за [math]O(1)[/math].

getMin

Выполняется просто, так как [math] BPQ [/math] хранит минимум.

int getMin(<x:int, q:PQ>):
    return x

Очевидно, работает за [math]O(1)[/math].

extractMin

Минимальный элемент хранится в верхнем [math] BPQ [/math], поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из [math] BPQ[/math].

<int, BPQ> extractMin(<x:int, q:PQ>):
    <<y, r>, t> = extractMin(q)
    return <x, <y, merge(r, t)>>

Здесь [math]\mathrm{extractMin}[/math] — это функция, извлекающая минимальный элемент типа [math] BPQ [/math] из приоритетной очереди, она возвращает [math]\langle y,r \rangle[/math] — минимальный элемент типа [math] BPQ [/math] и остаток от приоритетной очереди после извлечение минимума — [math]t[/math]. Соответственно, [math]\mathrm{merge}[/math] — функция, выполняющая слияние двух приоритетных очередей.

Возвращаем минимум и [math] BPQ [/math], где [math]x[/math] — новый минимальный элемент, и [math]\mathrm{merge}(r,t)[/math] — приоритетная очередь без элементов [math]x[/math] и [math]y[/math].

Так как [math]\mathrm{extractMin}[/math] и [math]\mathrm{merge}[/math] выполняются за [math]O(\log N)[/math], то [math]\mathrm{extractMin}[/math] выполняется за [math]O(\log N)[/math].

Смотри также

Источники информации