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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Insert)
Строка 26: Строка 26:
 
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.
 
Слияние выполняется выбором минимума из двух значений <tex>T_{min}</tex> и добавлением в приоритетную очередь второго <tex> BPQ </tex>.
 
<code>
 
<code>
  '''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''bpq'''<tex> \rangle </tex>):
+
  '''BPQ''' merge(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, <tex> \langle </tex>y:'''int''', r:'''BPQ'''<tex> \rangle </tex>):
 
     '''if''' x < y
 
     '''if''' x < y
 
         '''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))
 
         '''return''' (x, insert(q, <tex> \langle </tex>y, r<tex> \rangle </tex>))
Строка 37: Строка 37:
 
Это создание нового <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'''):
+
  '''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' insert(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>, y:'''BPQ'''):
 
     '''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))
 
     '''return''' merge(<tex> \langle </tex>x, q<tex> \rangle </tex>, create(y))
 
</code>
 
</code>
Строка 45: Строка 45:
 
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
 
Выполняется просто, так как <tex> BPQ </tex> хранит минимум.
 
<code>
 
<code>
  '''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):
+
  '''int''' getMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):
 
     '''return''' x
 
     '''return''' x
 
</code>
 
</code>
Строка 53: Строка 53:
 
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.  
 
Минимальный элемент хранится в верхнем <tex> BPQ </tex>, по этому его поиск не нужен. Требуется извлечение минимума из приоритетной очереди, состоящей из <tex> BPQ</tex>.  
 
<code>
 
<code>
  '''<tex> \langle </tex>int, bpq<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''bpq'''<tex> \rangle </tex>):
+
  '''<tex> \langle </tex>int, BPQ<tex> \rangle </tex>''' extractMin(<tex> \langle </tex>x:'''int''', q:'''BPQ'''<tex> \rangle </tex>):
 
     <tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)
 
     <tex> \langle </tex><tex> \langle </tex>y, r<tex> \rangle </tex>, t<tex> \rangle </tex> = extractMin(q)
 
     '''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex>
 
     '''return''' <tex> \langle </tex>y, merge(r, t)<tex> \rangle </tex>

Версия 09:15, 12 июня 2014

Куча Бродала-Окасаки (англ. 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]. Это можно записать так:

[math] BPQ \left \langle T_{min}, PQ \right \rangle = (T_{min}, PQ \left \langle BPQ \left \langle T_{min}, PQ\right \rangle \right \rangle)[/math]

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

[math] \mathrm{create} [/math][math](x) = BPQ \left \langle x, null\right \rangle[/math]

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

Операции

Merge

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

BPQ merge([math] \langle [/math]x:int, q:BPQ[math] \rangle [/math], [math] \langle [/math]y:int, r:BPQ[math] \rangle [/math]):
    if x < y
        return (x, insert(q, [math] \langle [/math]y, r[math] \rangle [/math]))
    else
        return (y, insert(r, [math] \langle [/math]x, q[math] \rangle [/math]))

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

Insert

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

[math] \langle [/math]int, BPQ[math] \rangle [/math] insert([math] \langle [/math]x:int, q:BPQ[math] \rangle [/math], y:BPQ):
    return merge([math] \langle [/math]x, q[math] \rangle [/math], create(y))

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

getMin

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

int getMin([math] \langle [/math]x:int, q:BPQ[math] \rangle [/math]):
    return x

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

extractMin

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

[math] \langle [/math]int, BPQ[math] \rangle [/math] extractMin([math] \langle [/math]x:int, q:BPQ[math] \rangle [/math]):
    [math] \langle [/math][math] \langle [/math]y, r[math] \rangle [/math], t[math] \rangle [/math] = extractMin(q)
    return [math] \langle [/math]y, merge(r, t)[math] \rangle [/math]

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

Возвращаем [math] BPQ [/math], где [math]y[/math] — новый минимальный элемент, и [math]\mathrm{merge}[/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].

Смотри также

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