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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и структуры данных Bootstrapping. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
+
'''Куча Бродала-Окасаки''' (англ. ''Brodal's and Okasaki's Priority Queue'') - основана на использовании [[Биномиальная куча|биномиальной кучи]] без каскадных ссылок, добавлении минимального элемента и идеи Data-structural bootstrapping. Поддерживает поиск минимума, вставку, слияние за <tex>O(1)</tex> в худшем случае и удаление минимума за <tex>O(log N)</tex> в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.
  
 
== Структура ==
 
== Структура ==
Используем структуру данных, которую Тарьян и Буксбаум называют Bootstrapping.  
+
Используем идею, которую Тарьян и Буксбаум называют Data-structural bootstrapping.  
 
{{Определение
 
{{Определение
 
|neat = 0
 
|neat = 0
|definition= Bootstrapping - это структура данных, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
+
|definition= Data-structural bootstrapping - это идея, позволяющая снизить время <tex>merge</tex> до <tex>O(1)</tex> путем разрешения хранить в очереди другую очередь.
 
}}
 
}}
  
Строка 25: Строка 25:
 
== Операции ==
 
== Операции ==
 
=== Merge ===
 
=== Merge ===
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго Bootstrapping.
+
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго BPQ.
 
<pre>
 
<pre>
 
merge((x,q), (y,r))
 
merge((x,q), (y,r))
Строка 35: Строка 35:
 
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>.
 
Здесь <tex>insert</tex> это добавление в приоритетную очередь работает за <tex>O(1)</tex>, тогда <tex>merge</tex> работает за <tex>O(1)</tex>.
 
=== Insert ===
 
=== Insert ===
Это создание нового Bootstrapping и <tex>merge</tex> его с основным деревом.
+
Это создание нового BPQ и <tex>merge</tex> его с основным деревом.
 
<pre>
 
<pre>
 
insert((x,q), y)
 
insert((x,q), y)
Строка 50: Строка 50:
  
 
=== extractMin ===
 
=== extractMin ===
Минимальный элемент хранится в верхнем Bootstrapping, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди Bootstrapping'ов.  
+
Минимальный элемент хранится в верхнем BPQ, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди BPQ'ов.  
 
<pre>
 
<pre>
 
extractMin((x,q))
 
extractMin((x,q))
Строка 56: Строка 56:
 
   return (y, merge(r, t))
 
   return (y, merge(r, t))
 
</pre>
 
</pre>
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа Bootstrapping из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа Bootstrapping и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.
+
Здесь <tex>extractMin(q)</tex> {{---}} это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает <tex>(y,r)</tex> - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - <tex>t</tex>. <tex>merge</tex> {{---}} функция, выполняющая слияние двух приоритетных очередей.
  
Возвращаем Bootstrapping, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
+
Возвращаем BPQ, где <tex>y</tex> {{---}} новый минимальный элемент, и <tex>merge(r, t)</tex> приоритетная очередь без элемента <tex>y</tex>.
  
 
Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</tex> выполняется за <tex>O(log N)</tex>.
 
Так как <tex>extractMin</tex> и <tex>merge</tex> выполняются за <tex>O(log N)</tex>, тогда <tex>extractMin</tex> выполняется за <tex>O(log N)</tex>.

Версия 11:43, 11 июня 2013

Куча Бродала-Окасаки (англ. Brodal's and Okasaki's Priority Queue) - основана на использовании биномиальной кучи без каскадных ссылок, добавлении минимального элемента и идеи Data-structural bootstrapping. Поддерживает поиск минимума, вставку, слияние за [math]O(1)[/math] в худшем случае и удаление минимума за [math]O(log N)[/math] в худшем случае. Эти оценки являются асимптотически оптимальными среди всех основанных на сравнении приоритетных очередей.

Структура

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

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




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

[math] BPQ\lt T_{min}, PQ\gt = (T_{min}, PQ\lt BPQ\lt T_{min}, PQ\gt \gt )[/math]

Куча из одного элемента будет выглядеть так

[math]create(x) = BPQ\lt x, null\gt [/math]

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

Операции

Merge

Слияние выполняется выбором минимума из двух значений [math]T_{min}[/math] и добавлением в приоритетную очередь второго BPQ.

merge((x,q), (y,r))
  if x<y
    return (x, insert(q, (y,r)))
  else
    return (y, insert(r, (x,q)))

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

Insert

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

insert((x,q), y)
  return merge((x,q), create(y))

Создание и [math]merge[/math] выполняются за [math]O(1)[/math], тогда [math]insert[/math] работает за [math]O(1)[/math].

getMin

Выполняется просто, так как Bootstrapping хранит минимум.

getMin((x,q))
  return x;

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

extractMin

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

extractMin((x,q))
  ((y,r), t) = extractMin(q)
  return (y, merge(r, t))

Здесь [math]extractMin(q)[/math] — это функция, извлекающая минимальный элемент типа BPQ из приоритетной очереди, она возвращает [math](y,r)[/math] - минимальный элемент типа BPQ и остаток от приоритетной очереди после извлечение минимума - [math]t[/math]. [math]merge[/math] — функция, выполняющая слияние двух приоритетных очередей.

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

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

Смотри также

Ссылки

Лекция А.С. Станкевича по приоритетным очередям

Optimal Purely Functional Priority Queues