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

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

Смотри также

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