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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Insert)
м (rollbackEdits.php mass rollback)
 
(не показано 27 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Куча Бродала-Окасаки''' (англ. ''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> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
+
'''Куча Бродала-Окасаки''' (англ. ''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>
Строка 24: Строка 29:
 
== Операции ==
 
== Операции ==
 
=== Merge ===
 
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.
+
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex>. Этот элемент и станет вершиной кучи. Это позволит в любой момент за константное время показать его при необходимости. Другой, больший элемент, будет вставлен в структуру кучи при помощи операции <math>\mathrm{insert}</math>.
 
<code>
 
<code>
  '''BPQ''' merge(<tex> \langle </tex>x : '''int''', q : '''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>:'''pair'''):
+
  '''BPQ''' merge('''<'''x:'''int''', q:'''PQ>''', '''<'''y:'''int''', r:'''PQ>'''):
 
     '''if''' x < y
 
     '''if''' x < y
         '''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))
+
         '''return''' <x, insert(q, <y, r>)>
 
     '''else'''
 
     '''else'''
         '''return''' (y, insert(r, <tex> \langle </tex>x, q<tex> \rangle </tex>))
+
         '''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 ===
 
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.
 
Это создание нового <tex> BPQ </tex> и <math>\mathrm{merge}</math> его с основным деревом.
 
<code>
 
<code>
  '''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, y:'''bpq'''):
+
  '''BPQ''' insert('''<'''x:'''int''', q:'''PQ>''', y:'''int'''):
     return merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))
+
     '''return''' merge(<x, q>, singleton(y))
 
</code>
 
</code>
Создание и <math>\mathrm{merge}</math> выполняются за <tex>O(1)</tex>, тогда <math>\mathrm{insert}</math> работает за <tex>O(1)</tex>.
+
По сути операция <math>\mathrm{insert}</math> - тот же самый <math>\mathrm{merge}</math>: создается дерево нулевого ранга за <tex>O(1)</tex>, а затем оно сливается с основным также за <tex>O(1)</tex>.
  
 
=== getMin ===
 
=== getMin ===
 
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
 
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
 
<code>
 
<code>
  '''int''' getMin((x:'''int''', q:'''bpq'''):'''pair'''):
+
  '''int''' getMin('''<'''x:'''int''', q:'''PQ>'''):
    return x;
+
    '''return''' x
 
</code>
 
</code>
 
Очевидно, работает за <tex>O(1)</tex>.
 
Очевидно, работает за <tex>O(1)</tex>.
  
 
=== extractMin ===
 
=== extractMin ===
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди <tex> BPQ</tex>ов.  
+
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, поэтому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.  
 
<code>
 
<code>
  '''pair (int, bpq)''' extractMin((x:'''int''', q:'''bpq'''):'''pair'''):
+
  '''<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>
Здесь <math>\mathrm{extractMin}</math>{{---}} это функция, извлекающая минимальный элемент типа <tex> BPQ </tex> из приоритетной очереди, она возвращает <tex>(y,r)</tex> {{---}} минимальный элемент типа <tex> BPQ </tex> и остаток от приоритетной очереди после извлечение минимума {{---}} <tex>t</tex>. <math>\mathrm{merge}</math> функция, выполняющая слияние двух приоритетных очередей.
+
Здесь <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>y</tex> {{---}} новый минимальный элемент, и <math>\mathrm{merge}</math> приоритетная очередь без элемента <tex>y</tex>.
+
Возвращаем минимум и <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>.
+
Так как <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]

Текущая версия на 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].

Смотри также

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