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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Merge)
м (Insert: Typo)
(не показаны 42 промежуточные версии 4 участников)
Строка 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> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
  
 
== Структура ==
 
== Структура ==
Строка 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>:
  
<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''' = '''<int, PQ'''('''BPQ''')'''>'''
 +
</code>
  
Куча из одного элемента будет выглядеть так
+
Куча из одного элемента создается так:
  
<math> \mathrm{create} </math><tex>(x) = BPQ \left \langle x, null\right \rangle</tex>
+
<code>
 +
'''BPQ''' singleton'(x:'''int'''):
 +
    '''return''' <x, null>
 +
</code>
  
Данная структура не будет бесконечной, так как каждый раз в приоритетной очереди будет храниться на один элемент меньше, таким образом образуя иерархическую структуру. Каждое значение храниться в одном из значений <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(int, bpq)''' 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>
Здесь <math>\mathrm{insert}</math> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <math>\mathrm{merge}</math> работает за <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)>>
 
</code>
 
</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>.
  
 
== Смотри также ==
 
== Смотри также ==
Строка 70: Строка 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]

Версия 18:52, 28 октября 2016

Куча Бродала-Окасаки (англ. 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].

Смотри также

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