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

Материал из Викиконспекты
Перейти к: навигация, поиск
(insert)
 
(не показано 16 промежуточных версий этого же участника)
Строка 1: Строка 1:
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') - это [[Приоритетные очереди|приоритетная очередь]], реализующая персистентность, то есть позволяющая получить доступ ко всем своим предыдущим версиям.
+
'''Персистентная приоритетная очередь''' (англ. ''persistent priority queue'') {{---}} [[Приоритетные очереди|приоритетная очередь]], реализующая [[Персистентные структуры данных|персистентность]], то есть позволяющая получить доступ ко всем своим предыдущим версиям.
  
== Наивная реализация с помощью дерева отрезов ==
+
== Реализация с помощью дерева отрезков ==
  
 
=== Идея ===
 
=== Идея ===
  
Известно, что на основе [[Дерево отрезков. Построение|дерева отрезков]] можно построить полностью [[Персистентные структуры данных|персистентную структуру данных]]. Поэтому используем его, только модифицируем операцию изменения на случай вставки и удаления элементов очереди для создания персистентной приоритетной очереди.
+
Известно, что на основе [[Дерево отрезков. Построение|дерева отрезков]] можно построить полностью [[Персистентные структуры данных|персистентную структуру данных]]. Поэтому используем его, модифицируя операцию изменения на случай вставки и удаления элементов очереди.
  
 
=== Реализация ===
 
=== Реализация ===
Строка 16: Строка 16:
 
   '''Node''' right
 
   '''Node''' right
 
   '''T''' key
 
   '''T''' key
   Node(val : '''T''')                              <font color="darkgreen">//конструктор для листов</font>
+
   Node(val : '''T''')                              <font color="darkgreen">// конструктор для листов</font>
   Node(leftChild : '''Node''', rightChild : '''Node''')  <font color="darkgreen">//конструктор для узлов(присваивает полю key минимальное среди leftChild и rightChild)</font>
+
   Node(leftChild : '''Node''', rightChild : '''Node''')  <font color="darkgreen">// конструктор для узлов (присваивает полю key минимальное среди leftChild и rightChild)</font>
 
</code>
 
</code>
  
 
Реализуем следующие функции:
 
Реализуем следующие функции:
* <tex>\mathrm{build}</tex> - построение дерева  
+
* <tex>\mathrm{build}</tex> {{---}} построение дерева,
* <tex>\mathrm{insert}</tex> - вставка нового элемента очереди
+
* <tex>\mathrm{insert}</tex> {{---}} вставка нового элемента очереди,
* <tex>\mathrm{extractMin}</tex> - удаление минимального элемента очереди
+
* <tex>\mathrm{extractMin}</tex> {{---}} удаление минимального элемента очереди,
* <tex>\mathrm{merge}</tex> - слияние  
+
* <tex>\mathrm{merge}</tex> {{---}} слияние.
  
 
Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива.
 
Каждая функция возвращает корень нового дерева, которое потом можно будет снова изменять. При реализации можно хранить отдельный массив корней деревьев и при каждом новом изменении какой-либо из версий добавлять измененную в конец массива.
Строка 42: Строка 42:
 
==== insert ====
 
==== insert ====
  
Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершин.  
+
Вставлять новое значение мы будем в любой пустой лист. Лист считается пустым, если его значение равно <tex>\infty</tex>. При этом не стоит забывать, что те узлы, которые подвергаются изменению, нужно сначала скопировать, а потом вставить новый на основе скопированного для сохранения предыдущих состояний очереди. Запрос вставки нового ключа создает <tex>O(\log n)</tex> новых вершин и время его работы <tex>O(n)</tex>.  
  
 
<code>
 
<code>
Строка 56: Строка 56:
 
       '''return''' ''null''
 
       '''return''' ''null''
 
     '''else'''
 
     '''else'''
       '''return''' Node(currentNode.left, y)
+
       '''return''' Node(currentNode.left, temp)
 
   '''else'''
 
   '''else'''
     '''return''' Node(y, currentNode.right)
+
     '''return''' Node(temp, currentNode.right)
</code>  
+
</code>
  
 
==== extractMin ====
 
==== extractMin ====
Строка 82: Строка 82:
 
</code>
 
</code>
  
== Наивная реализация с помощью левосторонней кучи ==
+
=== Недостатки реализации ===
 +
У данной реализации есть несколько существенных минусов:
 +
#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
 +
#Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.
 +
Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации.
 +
 
 +
== Реализация с помощью левосторонней кучи ==
  
 
Реализуем приоритетную очередь на [[Левосторонняя куча|левосторонней куче]]. Т.к. в [[Левосторонняя куча|левосторонней куче]] нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.  
 
Реализуем приоритетную очередь на [[Левосторонняя куча|левосторонней куче]]. Т.к. в [[Левосторонняя куча|левосторонней куче]] нигде не делается уничтожающих присваиваний, то можно её преобразовать в персистентную приоритетную очередь.  
Строка 96: Строка 102:
 
</code>
 
</code>
  
Приведём реализацию конструктора
+
Приведём реализацию конструктора:
  
 
<code>
 
<code>
Строка 109: Строка 115:
 
   dist = min(left.dist, right.dist) + 1
 
   dist = min(left.dist, right.dist) + 1
 
</code>
 
</code>
 
Все предыдущие и текущую версии очереди будем хранить в виде массива корней.
 
  
 
=== Поддерживаемые операции ===
 
=== Поддерживаемые операции ===
  
Все операции практически (кроме <tex>\mathrm{merge}</tex>) аналогичны операциям с эфемерной [[Левосторонняя куча|левосторонней кучей]], только каждая из них возвращает корень измененной кучи. В частности <tex>\mathrm{extractMin}</tex> возвращает пару из извлеченной вершины и измененной кучи.
+
Все операции практически (кроме <tex>\mathrm{merge}</tex>) аналогичны операциям с [[Левосторонняя куча|левосторонней кучей]], только каждая из них возвращает корень измененной кучи. В частности <tex>\mathrm{extractMin}</tex> возвращает пару из извлеченной вершины и измененной кучи.
  
 
<tex>\mathrm{merge}</tex> примет следующий вид:
 
<tex>\mathrm{merge}</tex> примет следующий вид:
 
<code>   
 
<code>   
  '''LeftistHeap''' merge(x, y):
+
  '''LeftistHeap''' merge(x : '''LeftistHeap''', y : '''LeftistHeap'''):
 
   '''if''' x == <tex> \varnothing </tex>:  
 
   '''if''' x == <tex> \varnothing </tex>:  
 
       '''return''' y
 
       '''return''' y
 
   '''if''' y == <tex> \varnothing </tex>:  
 
   '''if''' y == <tex> \varnothing </tex>:  
 
       '''return''' x
 
       '''return''' x
   '''if''' y.key < x.key:
+
   '''if''' y.key >= x.key:
      swap(x, y)
+
    z = LeftistHeap(x.left, merge(x.right, y), 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
 
   '''return''' z
 
</code>
 
</code>
  
== Основная идея ==
+
== Реализация с помощью биномиальной кучи ==
  
 
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
 
Возьмем [[Биномиальная куча|биномиальную кучу]] и реализуем ее на односвязных списках.
Строка 138: Строка 143:
  
 
Каждый узел в персистентной биномиальной куче представляется набором полей:
 
Каждый узел в персистентной биномиальной куче представляется набором полей:
* <tex>key</tex> ключ (вес) элемента;
+
* <tex>key</tex> {{---}} ключ (вес) элемента,
* <tex>next</tex> указатель на следующий элемент;
+
* <tex>next</tex> {{---}} указатель на следующий элемент,
* <tex>child</tex> указатель на ребенка с большим рангом;
+
* <tex>child</tex> {{---}} указатель на ребенка с большим рангом,
* <tex>degree</tex> степень узла (количество дочерних узлов данного узла).
+
* <tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
 
Доступ к куче осуществляется ссылкой на первый корень в списке корней.  
 
Доступ к куче осуществляется ссылкой на первый корень в списке корней.  
  
Строка 156: Строка 161:
 
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.  
 
Проходим по корневым спискам и создаем новый, объединяя деревья одинакового ранга.  
  
Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых - новый корень, другой из них - видоизмененный корень одного из деревьев.
+
Вспомогательная функция <tex>\mathrm{mergeTree}</tex> объединят в одно деревья одинакового ранга. Для этого мы создаём два новых узла, один из которых {{---}} новый корень, другой из них {{---}} видоизмененный корень одного из деревьев.
 
<code>
 
<code>
 
  '''PersistentBinomialHeap''' mergeTree(t1 : '''PersistentBinomialHeap''', t2 : '''PersistentBinomialHeap'''):
 
  '''PersistentBinomialHeap''' mergeTree(t1 : '''PersistentBinomialHeap''', t2 : '''PersistentBinomialHeap'''):
Строка 164: Строка 169:
 
   newRoot.degree = t1.degree + t2.degree  
 
   newRoot.degree = t1.degree + t2.degree  
 
   '''if''' (t1.key < t2.key)
 
   '''if''' (t1.key < t2.key)
     tmp = PersistentBinomialHeap(t2) <font color = "green">//создаем новый узел путем копирования старого с помощью конструктора</font>
+
     tmp = PersistentBinomialHeap(t2) <font color = "green">// создаем новый узел путем копирования старого с помощью конструктора</font>
 
     tmp.next = t1.child
 
     tmp.next = t1.child
 
     newRoot.key = t1.key
 
     newRoot.key = t1.key
Строка 182: Строка 187:
 
==== insert ====
 
==== insert ====
  
Общий принцип вставки нового элемента схож с принципом вставки в эфемерную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга 0, в котором будет единственный элемент - тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.   
+
Общий принцип вставки нового элемента схож с принципом вставки в обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.   
  
 
Есть два случая слияния:
 
Есть два случая слияния:
  
а) Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
+
#Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
 
+
#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(1)</tex>.
б) Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент.ex>. Время работы <tex>O(\log n)</tex>.
 
  
 
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
 
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
Строка 196: Строка 200:
 
   newRoot = PersistentBinomialHeap(newVal)
 
   newRoot = PersistentBinomialHeap(newVal)
 
   '''if''' heap.degree == newRoot.degree:
 
   '''if''' heap.degree == newRoot.degree:
     return mergeTree(newRoot, heap)
+
     return merge(newRoot, heap)
 
   '''else'''
 
   '''else'''
 
     newRoot.next = heap  
 
     newRoot.next = heap  
Строка 202: Строка 206:
 
</code>
 
</code>
  
Пример работы. Пусть дана куча:
+
===== Пример работы. =====
 
 
[[File:PersistentBinomialHeapExample1_3.png]]
 
 
 
Вставим в кучу элемент, с ключом, равным 3. В данном случае выполняется условие под пунктом б). Тогда получим:
 
 
 
[[File:PersistentBinomialHeapExample1_4.png]]
 
 
 
Теперь вставим в эту же кучу элемент, с ключом, равным 4. Эта ситуация соответствует пункту а). Получим:
 
  
[[File:PersistentBinomialHeapExample1_5.png]]
+
{| 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]]
 +
|}
  
 
==== extractMinimum ====
 
==== extractMinimum ====
  
Работает так же как и в эфемерной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи.
+
Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
 
 
<code>
 
'''function''' extractMinimum(t : '''PersistentBinomialHeap''')
 
  tmp = t
 
  minimum = t
 
  '''while''' tmp != ''null''
 
    '''if''' minimum.key > tmp.key
 
      min = tmp
 
    tmp = tmp.next;
 
  tmp = t
 
  H = PersistentBinomialHeap()
 
  tmpNewRoot = H
 
  '''while''' tmp != ''null''
 
    '''if''' tmp.next == min
 
        tmpNewRoot = PersistentBinomialHeap(tmp)
 
        tmpNewRoot.next = tmp.next.next
 
    '''else'''
 
        tmpNewRoot = PersistentBinomialHeap(tmp)
 
    tmpNewRoot = tmpNewRoot.next
 
  <font color = "green">//расставляем детей в удаленном дереве в возрастающем порядке с помощью вспомогательного массива nodes</font>
 
  H' = PersistentBinomialHeap()
 
  tmp = min.child
 
  x = 0
 
  '''while''' tmp != null
 
    nodes[x] = tmp
 
    tmp = tmp.next
 
    x = x + 1
 
  tmp = H'
 
  '''for''' i = x - 1 '''downto''' 0
 
    tmp.next = PersistentBinomialHeap(nodes[x])
 
    tmp = tmp.next
 
  '''return''' (merge(H.next, H'.next), min.key)
 
</code>
 
 
 
Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Работает за <tex>O(\log n)</tex>.
 
  
== Смотри также ==
+
== Cм. также ==
  
 
* [[Приоритетные очереди]]
 
* [[Приоритетные очереди]]
Строка 261: Строка 233:
 
* [[Персистентная очередь]]
 
* [[Персистентная очередь]]
  
== Ссылки ==
+
== Источники информации ==
  
 
*[http://compscicenter.ru/courses/advanced-algo/2013-spring/classes/723/ Лекция А.С. Станкевича по приоритетным очередям]
 
*[http://compscicenter.ru/courses/advanced-algo/2013-spring/classes/723/ Лекция А.С. Станкевича по приоритетным очередям]
 
*[http://logic.pdmi.ras.ru/csclub/node/2734 Лекция П.Ю. Мавривна по персистентным структурам данных]
 
*[http://logic.pdmi.ras.ru/csclub/node/2734 Лекция П.Ю. Мавривна по персистентным структурам данных]
*[http://ru.wikipedia.org/wiki/Очередь_с_приоритетом_(программирование) Википедия - Очередь с приоритетом]
+
*[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м. также[править]

Источники информации[править]