Персистентная приоритетная очередь — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Merge)
(insert)
(не показано 18 промежуточных версий 2 участников)
Строка 1: Строка 1:
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') - это приоритетная очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям.
+
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') {{---}} [[Приоритетные очереди|приоритетная очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям.
== Основная идея ==
+
 
 +
== Реализация с помощью дерева отрезков ==
 +
 
 +
=== Идея ===
 +
 
 +
Известно, что на основе [[Дерево отрезков. Построение|дерева отрезков]] можно построить полностью [[Персистентные структуры данных|персистентную структуру данных]]. Поэтому используем его, модифицируя операцию изменения на случай вставки и удаления элементов очереди.
 +
 
 +
=== Реализация ===
 +
 
 +
Будем хранить явные указатели на дочерние элементы. Тогда структура узла дерева примет следующий вид:
 +
 
 +
<code>
 +
'''struct''' Node:
 +
  '''Node''' left
 +
  '''Node''' right
 +
  '''T''' key
 +
  Node(val : '''T''')                              <font color="darkgreen">// конструктор для листов</font>
 +
  Node(leftChild : '''Node''', rightChild : '''Node''')  <font color="darkgreen">// конструктор для узлов (присваивает полю key минимальное среди leftChild и rightChild)</font>
 +
</code>
 +
 
 +
Реализуем следующие функции:
 +
* <tex>\mathrm{build}</tex> {{---}} построение дерева,
 +
* <tex>\mathrm{insert}</tex> {{---}} вставка нового элемента очереди,
 +
* <tex>\mathrm{extractMin}</tex> {{---}} удаление минимального элемента очереди,
 +
* <tex>\mathrm{merge}</tex> {{---}} слияние.
 +
 
 +
Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива.
 +
 
 +
==== build ====
 +
 
 +
Дерево будет построено фиксированного размера. Стоит отметить, что при создании нескольких деревьев необходимо придерживаться одного максимального размера. Асимптотика построения дерева отрезков составит <tex>O(n)</tex>.
 +
 
 +
<code>
 +
'''Node''' build(left : '''uint''', right : '''uint'''):
 +
  '''if''' left == right
 +
    '''return''' Node(<tex>\infty</tex>)
 +
  '''uint''' mid = (left + right) / 2
 +
  '''return''' Node(build(left, mid), build(mid + 1, right))
 +
</code>
 +
 
 +
==== insert ====
 +
 
 +
Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершин и время его работы <tex>O(n)</tex>.
 +
 
 +
<code>
 +
'''Node''' insert(currentNode : '''Node''', newVal : '''T'''):
 +
  '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val != <tex>\infty</tex> <font color="darkgreen">//если лист занят</font>
 +
    '''return''' ''null''
 +
  '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val == <tex>\infty</tex> <font color="darkgreen">//если лист свободен</font>
 +
    '''return''' Node(newVal)
 +
  '''Node''' temp = insert(currentNode.left, newVal)
 +
  '''if''' temp == ''null''
 +
    temp = insert(currentNode.right, newVal)
 +
    '''if''' temp == ''null''
 +
      '''return''' ''null''
 +
    '''else'''
 +
      '''return''' Node(currentNode.left, temp)
 +
  '''else'''
 +
    '''return''' Node(temp, currentNode.right)
 +
</code>
 +
 
 +
==== extractMin ====
 +
 
 +
Учитывая тот факт, что корень дерева содержит ключ минимального элемента, можно найти путь к листу, содержащему этот элемент, и удалить его. Аналогично вставке, не стоит забывать о сохранении предыдущих состояний очереди. Вызов функции должен производиться указанием в качестве аргументов корня дерева и значения в корне дерева. Запрос удаления минимального ключа создает <tex>O(\log n)</tex> новых вершин.
 +
<code>
 +
'''Node''' extractMin(currentNode : '''Node''', delVal : '''T'''):
 +
  '''if''' currentNode.left == ''null'' '''and''' currentNode.right == ''null'' '''and''' currentNode.val == delVal
 +
    '''return''' Node(<tex>\infty</tex>)
 +
  '''if''' currentNode.left.val == delVal:
 +
    '''return''' Node(extractMin(currentNode.left, delVal), currentNode.right)
 +
  '''else'''
 +
    '''return''' Node(currentNode.left, extractMin(currentNode.right, delVal))
 +
</code>
 +
 
 +
==== merge ====
 +
 
 +
Слияние двух деревьев будет производить с помощью конструктора структуры. Поэтому оно выполняется за <tex>O(1)</tex>.
 +
<code>
 +
'''Node''' merge(leftTree : '''Node''', rightTree : '''Node''')
 +
  '''return''' Node(leftTree, rightTree)
 +
</code>
 +
 
 +
=== Недостатки реализации ===
 +
У данной реализации есть несколько существенных минусов:
 +
#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
 +
#Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.
 +
Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации.
 +
 
 +
== Реализация с помощью левосторонней кучи ==
 +
 
 +
Реализуем приоритетную очередь на [[Левосторонняя куча|левосторонней куче]]. Т.к. в [[Левосторонняя куча|левосторонней куче]] нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.
 +
 
 +
Будем хранить структуру:
 +
<code>
 +
'''struct''' LeftistHeap:
 +
  '''LeftistHeap''' left
 +
  '''LeftistHeap''' right
 +
  '''T''' key
 +
  '''int''' dist
 +
  LeftistHeap(leftChild : '''LeftistHeap''', rightChild : '''LeftistHeap''', val : '''T''')
 +
</code>
 +
 
 +
Приведём реализацию конструктора:
 +
 
 +
<code>
 +
LeftistHeap(leftChild : '''LeftistHeap''', rightChild : '''LeftistHeap''', val : '''T'''):
 +
  key = val
 +
  '''if''' leftChild.dist > rightChild.dist
 +
    left = leftChild
 +
    right = rightChild
 +
  '''else'''
 +
    left = rightChild
 +
    right = leftChild
 +
  dist = min(left.dist, right.dist) + 1
 +
</code>
 +
 
 +
=== Поддерживаемые операции ===
 +
 
 +
Все операции практически (кроме <tex>\mathrm{merge}</tex>) аналогичны операциям с [[Левосторонняя куча|левосторонней кучей]], только каждая из них возвращает корень измененной кучи. В частности <tex>\mathrm{extractMin}</tex> возвращает пару из извлеченной вершины и измененной кучи.
 +
 
 +
<tex>\mathrm{merge}</tex> примет следующий вид:
 +
<code> 
 +
'''LeftistHeap''' merge(x : '''LeftistHeap''', y : '''LeftistHeap'''):
 +
  '''if''' x == <tex> \varnothing </tex>:
 +
      '''return''' y
 +
  '''if''' y == <tex> \varnothing </tex>:
 +
      '''return''' x
 +
  '''if''' y.key >= x.key:
 +
    z = LeftistHeap(x.left, merge(x.right, y), x.key)
 +
  '''else'''
 +
    z = LeftistHeap(y.left, merge(y.right, x), y.key)
 +
  '''return''' z
 +
</code>
 +
 
 +
== Реализация с помощью биномиальной кучи ==
 +
 
 
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
 
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
  
Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя.
+
Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Т.к. дочерний элемент не знает о своем родителе, то можно объединять деревья, сохраняя персистентность данной структуры.
== Операции ==
+
 
=== Merge ===
+
=== Структура кучи ===
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.
+
 
<pre>
+
Каждый узел в персистентной биномиальной куче представляется набором полей:
merge_tree(t1, t2)
+
* <tex>key</tex> {{---}} ключ (вес) элемента,
  if (t1.key < t2.key)
+
* <tex>next</tex> {{---}} указатель на следующий элемент,
    t2.next = t1.son;
+
* <tex>child</tex> {{---}} указатель на ребенка с большим рангом,
    t1.son = t2;
+
* <tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
  else
+
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
    t1.next = t2.son;
+
 
    t2.son = t1;
+
=== Операции ===
</pre>
+
 
Проход по корневым спискам выполнится за <tex>O(logN)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>merge</tex> работает за <tex>O(logN)</tex>.
+
==== getMinimum ====
 +
 
 +
Для нахождения минимального элемента необходимо пройти по списку корней дерева. Можно это сделать за <tex>O(\log n)</tex>, т.к. список корней содержит не более <tex>\log n</tex> элементов. На рисунке это корень второго дерева в куче.
 +
 
 +
[[File:PersistentBinomialHeapExample1_1.png]]
 +
 +
==== merge ====
 +
 
 +
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.  
 +
 
 +
Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{---}} новый корень, другой из них {{---}} видоизмененный корень одного из деревьев.
 +
<code>
 +
'''PersistentBinomialHeap''' mergeTree(t1 : '''PersistentBinomialHeap''', t2 : '''PersistentBinomialHeap'''):
 +
  newRoot = PersistentBinomialHeap()
 +
  tmp = PersistentBinomialHeap()
 +
  newRoot.child = tmp
 +
  newRoot.degree = t1.degree + t2.degree
 +
  '''if''' (t1.key < t2.key)
 +
    tmp = PersistentBinomialHeap(t2) <font color = "green">// создаем новый узел путем копирования старого с помощью конструктора</font>
 +
    tmp.next = t1.child
 +
    newRoot.key = t1.key
 +
  '''else'''
 +
    tmp = PersistentBinomialHeap(t1)
 +
    tmp.next = t2.child
 +
    newRoot.key = t2.key
 +
  '''return''' newRoot
 +
</code>
 +
 
 +
Процесс слияния двух деревьев показан на рисунке. Первоначально было два дерева <tex>t1</tex> и <tex>t2</tex> (на рисунке выделены черным). Затем их слили, появились два новых узла, которые обращаются по прежнему к старым поддеревьям (выделено красным).
 +
 
 +
[[File:PersistentBinomialHeapExample1_2.png]]
 +
 
 +
Проход по корневым спискам выполнится за <tex>O(\log n)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>\mathrm{merge}</tex> работает за <tex>O(\log n)</tex>.
 +
 
 +
==== insert ====
 +
 
 +
Общий принцип вставки нового элемента схож с принципом вставки в обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну. 
 +
 
 +
Есть два случая слияния:
 +
 
 +
#Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
 +
#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(1)</tex>.
 +
 
 +
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
 +
 
 +
<code>
 +
'''PersistentBinomialHeap''' insert(heap : '''PersistentBinomialHeap''', newVal : '''T'''):
 +
  newRoot = PersistentBinomialHeap(newVal)
 +
  '''if''' heap.degree == newRoot.degree:
 +
    return merge(newRoot, heap)
 +
  '''else'''
 +
    newRoot.next = heap
 +
    '''return''' newRoot
 +
</code>
  
=== Insert ===
+
===== Пример работы. =====
Разрешим при объединении двух деревьев присоединять еще одну вершину, дерево ранга 0. Тогда получится возможным существование еще двух типов деревьев:
 
[[Файл:Persistent priority queue insert.png|300px]]
 
  
Разберем случаи добавления.
+
{| class = "wikitable" width="100%"
 +
! Описание !! Изображение
 +
|-align="center"
 +
|Исходная куча.
 +
|[[File:PersistentBinomialHeapExample1_3.png]]
 +
|-align="center"
 +
|Вставим в кучу элемент, с ключом, равным <tex>3</tex>. В данном случае выполняется условие под пунктом <tex>2</tex>.
 +
|[[File:PersistentBinomialHeapExample1_4.png]]
 +
|-align="center"
 +
|Теперь вставим в эту же кучу элемент, с ключом, равным <tex>4</tex>. Эта ситуация соответствует пункту <tex>1</tex>.
 +
|[[File:PersistentBinomialHeapExample1_5.png]]
 +
|}
  
а) Минимальный ранг дерева <tex>k</tex> и такое дерево одно. Добавим новое дерево ранга 0 - нашу вершину.
+
==== extractMinimum ====
  
б) Минимальный ранг дерева <tex>k</tex> и таких деревьев два. Объединим эти деревья и нашу вершину в дерево ранга <tex>k+1</tex>, получим дерево типа 1 или 2 в зависимости от того у какой вершины ключ меньше.
+
Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
  
Тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
+
== Cм. также ==
  
=== extractMinimum ===
+
* [[Приоритетные очереди]]
Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом.
+
* [[Персистентные структуры данных]]
<pre>
 
extractMinimum(t)
 
  t1=t;
 
  while t1.next != null
 
    if min.val>t1.val
 
      min = t1;
 
    t1 = t1.next;
 
  par = t;
 
  t1 = t;
 
  while min != t1
 
    par = t1;
 
    t1 = t1.next;
 
  par.next = par.next.next;
 
  return (min, t)
 
</pre>
 
Возвращает дерево с минимальным элементом и остаток от очереди после извлечения минимума. Работает за <tex>O(logN)</tex>.
 
== Смотри также ==
 
 
* [[Биномиальная куча]]
 
* [[Биномиальная куча]]
== Ссылки ==
+
* [[Левосторонняя куча]]
[http://www.lektorium.tv/lecture/?id=14234 Лекция А.С. Станкевича по приоритетным очередям]
+
* [[Персистентная очередь]]
 +
 
 +
== Источники информации ==
 +
 
 +
*[http://compscicenter.ru/courses/advanced-algo/2013-spring/classes/723/ Лекция А.С. Станкевича по приоритетным очередям]
 +
*[http://logic.pdmi.ras.ru/csclub/node/2734 Лекция П.Ю. Мавривна по персистентным структурам данных]
 +
*[http://ru.wikipedia.org/wiki/Очередь_с_приоритетом_(программирование) Википедия {{---}} Очередь с приоритетом]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
 +
[[Категория: Структуры данных‏‎]]
 +
[[Категория: Персистентные структуры данных]]

Версия 16:46, 6 февраля 2017

Персистентная приоритетная очередь (англ. persistent priority queue) — приоритетная очередь, реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям.

Реализация с помощью дерева отрезков

Идея

Известно, что на основе дерева отрезков можно построить полностью персистентную структуру данных. Поэтому используем его, модифицируя операцию изменения на случай вставки и удаления элементов очереди.

Реализация

Будем хранить явные указатели на дочерние элементы. Тогда структура узла дерева примет следующий вид:

struct Node:
  Node left
  Node right
  T key
  Node(val : T)                              // конструктор для листов
  Node(leftChild : Node, rightChild : Node)  // конструктор для узлов (присваивает полю key минимальное среди leftChild и rightChild)

Реализуем следующие функции:

  • [math]\mathrm{build}[/math] — построение дерева,
  • [math]\mathrm{insert}[/math] — вставка нового элемента очереди,
  • [math]\mathrm{extractMin}[/math] — удаление минимального элемента очереди,
  • [math]\mathrm{merge}[/math] — слияние.

Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива.

build

Дерево будет построено фиксированного размера. Стоит отметить, что при создании нескольких деревьев необходимо придерживаться одного максимального размера. Асимптотика построения дерева отрезков составит [math]O(n)[/math].

Node build(left : uint, right : uint):
  if left == right 
    return Node([math]\infty[/math])
  uint mid = (left + right) / 2
  return Node(build(left, mid), build(mid + 1, right))

insert

Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно [math]\infty[/math]. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает [math]O(\log n)[/math] новых вершин и время его работы [math]O(n)[/math].

Node insert(currentNode : Node, newVal : T):
  if currentNode.left == null and currentNode.right == null and currentNode.val != [math]\infty[/math] //если лист занят
    return null
  if currentNode.left == null and currentNode.right == null and currentNode.val == [math]\infty[/math] //если лист свободен
    return Node(newVal)
  Node temp = insert(currentNode.left, newVal)
  if temp == null
    temp = insert(currentNode.right, newVal)
    if temp == null 
      return null
    else
      return Node(currentNode.left, temp)
  else
    return Node(temp, currentNode.right)

extractMin

Учитывая тот факт, что корень дерева содержит ключ минимального элемента, можно найти путь к листу, содержащему этот элемент, и удалить его. Аналогично вставке, не стоит забывать о сохранении предыдущих состояний очереди. Вызов функции должен производиться указанием в качестве аргументов корня дерева и значения в корне дерева. Запрос удаления минимального ключа создает [math]O(\log n)[/math] новых вершин.

Node extractMin(currentNode : Node, delVal : T):
  if currentNode.left == null and currentNode.right == null and currentNode.val == delVal
    return Node([math]\infty[/math])
  if currentNode.left.val == delVal:
    return Node(extractMin(currentNode.left, delVal), currentNode.right)
  else
    return Node(currentNode.left, extractMin(currentNode.right, delVal))

merge

Слияние двух деревьев будет производить с помощью конструктора структуры. Поэтому оно выполняется за [math]O(1)[/math].

Node merge(leftTree : Node, rightTree : Node)
  return Node(leftTree, rightTree)

Недостатки реализации

У данной реализации есть несколько существенных минусов:

  1. Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
  2. Вставка происходит за [math]O(n)[/math], что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении приоритетной очереди просто копировать её и изменять.

Более эффективной реализацией является персистентная приоритетная очередь построенная на двоичном дереве поиска. Все операции, кроме слияния, выполняются за [math]O(\log n)[/math]. К тому же двоичное дерево поиска — динамическая структура, что позволит не думать об ограничении данных из-за реализации.

Реализация с помощью левосторонней кучи

Реализуем приоритетную очередь на левосторонней куче. Т.к. в левосторонней куче нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.

Будем хранить структуру:

struct LeftistHeap:
  LeftistHeap left
  LeftistHeap right
  T key
  int dist
  LeftistHeap(leftChild : LeftistHeap, rightChild : LeftistHeap, val : T)

Приведём реализацию конструктора:

LeftistHeap(leftChild : LeftistHeap, rightChild : LeftistHeap, val : T):
  key = val
  if leftChild.dist > rightChild.dist
    left = leftChild
    right = rightChild
  else
    left = rightChild
    right = leftChild
  dist = min(left.dist, right.dist) + 1

Поддерживаемые операции

Все операции практически (кроме [math]\mathrm{merge}[/math]) аналогичны операциям с левосторонней кучей, только каждая из них возвращает корень измененной кучи. В частности [math]\mathrm{extractMin}[/math] возвращает пару из извлеченной вершины и измененной кучи.

[math]\mathrm{merge}[/math] примет следующий вид:

LeftistHeap merge(x : LeftistHeap, y : LeftistHeap):
  if x == [math] \varnothing [/math]: 
      return y
  if y == [math] \varnothing [/math]: 
      return x
  if y.key >= x.key:
    z = LeftistHeap(x.left, merge(x.right, y), x.key)
  else
    z = LeftistHeap(y.left, merge(y.right, x), y.key)
  return z

Реализация с помощью биномиальной кучи

Возьмем биномиальную кучу и реализуем ее на односвязных списках.

Для этого будем хранить список корней в порядке возрастания ранга, а детей будем хранить по убыванию ранга. Каждый родитель будет знать ребенка с большим рангом, который является головой списка детей, но ребенок не будет знать родителя. Т.к. дочерний элемент не знает о своем родителе, то можно объединять деревья, сохраняя персистентность данной структуры.

Структура кучи

Каждый узел в персистентной биномиальной куче представляется набором полей:

  • [math]key[/math] — ключ (вес) элемента,
  • [math]next[/math] — указатель на следующий элемент,
  • [math]child[/math] — указатель на ребенка с большим рангом,
  • [math]degree[/math] — степень узла (количество дочерних узлов данного узла).

Доступ к куче осуществляется ссылкой на первый корень в списке корней.

Операции

getMinimum

Для нахождения минимального элемента необходимо пройти по списку корней дерева. Можно это сделать за [math]O(\log n)[/math], т.к. список корней содержит не более [math]\log n[/math] элементов. На рисунке это корень второго дерева в куче.

PersistentBinomialHeapExample1 1.png

merge

Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.

Вспомогательная функция [math]\mathrm{mergeTree}[/math] объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых — новый корень, другой из них — видоизмененный корень одного из деревьев.

PersistentBinomialHeap mergeTree(t1 : PersistentBinomialHeap, t2 : PersistentBinomialHeap):
  newRoot = PersistentBinomialHeap()
  tmp = PersistentBinomialHeap()
  newRoot.child = tmp
  newRoot.degree = t1.degree + t2.degree 
  if (t1.key < t2.key)
    tmp = PersistentBinomialHeap(t2) // создаем новый узел путем копирования старого с помощью конструктора
    tmp.next = t1.child
    newRoot.key = t1.key
  else
    tmp = PersistentBinomialHeap(t1) 
    tmp.next = t2.child
    newRoot.key = t2.key
  return newRoot

Процесс слияния двух деревьев показан на рисунке. Первоначально было два дерева [math]t1[/math] и [math]t2[/math] (на рисунке выделены черным). Затем их слили, появились два новых узла, которые обращаются по прежнему к старым поддеревьям (выделено красным).

PersistentBinomialHeapExample1 2.png

Проход по корневым спискам выполнится за [math]O(\log n)[/math], объединение деревьев выполняется за [math]O(1)[/math]. Тогда [math]\mathrm{merge}[/math] работает за [math]O(\log n)[/math].

insert

Общий принцип вставки нового элемента схож с принципом вставки в обычную биномиальную кучу. Создаем кучу с деревом ранга [math]0[/math], в котором будет единственный элемент — тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.

Есть два случая слияния:

  1. Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью [math]\mathrm{merge}[/math]. Время работы [math]O(\log n)[/math].
  2. Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы [math]O(1)[/math].

Тогда амортизационная стоимость одной операции [math]\mathrm{insert}[/math] составляет [math]O(1)[/math].

PersistentBinomialHeap insert(heap : PersistentBinomialHeap, newVal : T):
  newRoot = PersistentBinomialHeap(newVal)
  if heap.degree == newRoot.degree:
    return merge(newRoot, heap)
  else
    newRoot.next = heap 
    return newRoot

Пример работы.
Описание Изображение
Исходная куча. PersistentBinomialHeapExample1 3.png
Вставим в кучу элемент, с ключом, равным [math]3[/math]. В данном случае выполняется условие под пунктом [math]2[/math]. PersistentBinomialHeapExample1 4.png
Теперь вставим в эту же кучу элемент, с ключом, равным [math]4[/math]. Эта ситуация соответствует пункту [math]1[/math]. PersistentBinomialHeapExample1 5.png

extractMinimum

Работает так же как и в обычной биномиальной куче. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции [math]O(\log n)[/math].

Cм. также

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