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

Материал из Викиконспекты
Перейти к: навигация, поиск
(extractMinimum)
(insert)
 
(не показано 6 промежуточных версий этого же участника)
Строка 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>
  
Строка 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 ====
Строка 81: Строка 81:
 
   '''return''' Node(leftTree, rightTree)
 
   '''return''' Node(leftTree, rightTree)
 
</code>
 
</code>
 +
 +
=== Недостатки реализации ===
 +
У данной реализации есть несколько существенных минусов:
 +
#Реализация подразумевает конечный размер очереди, что весьма усложняет использование её в большом диапазоне данных.
 +
#Вставка происходит за <tex>O(n)</tex>, что делает данную реализацию бесполезной на большом количестве данных. Такое же время работы можно было получить, если при каждом изменении [[Приоритетные очереди|приоритетной очереди]] просто копировать её и изменять.
 +
Более эффективной реализацией является персистентная приоритетная очередь построенная на [[Дерево поиска, наивная реализация|двоичном дереве поиска]]. Все операции, кроме слияния, выполняются за <tex>O(\log n)</tex>. К тому же [[Дерево поиска, наивная реализация|двоичное дерево поиска]] {{---}} динамическая структура, что позволит не думать об ограничении данных из-за реализации.
  
 
== Реализация с помощью левосторонней кучи ==
 
== Реализация с помощью левосторонней кучи ==
Строка 122: Строка 128:
 
       '''return''' x
 
       '''return''' x
 
   '''if''' y.key >= x.key:
 
   '''if''' y.key >= x.key:
     z = LeftistHeap(x.left, '''merge'''(x.right, y), x.key)
+
     z = LeftistHeap(x.left, merge(x.right, y), x.key)
 
   '''else'''
 
   '''else'''
     z = LeftistHeap(y.left, '''merge'''(y.right, x), y.key)
+
     z = LeftistHeap(y.left, merge(y.right, x), y.key)
 
   '''return''' z
 
   '''return''' z
 
</code>
 
</code>
Строка 163: Строка 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
Строка 181: Строка 187:
 
==== insert ====
 
==== insert ====
  
Общий принцип вставки нового элемента схож с принципом вставки в эфемерную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.   
+
Общий принцип вставки нового элемента схож с принципом вставки в обычную [[Биномиальная куча|биномиальную кучу]]. Создаем кучу с деревом ранга <tex>0</tex>, в котором будет единственный элемент {{---}} тот самый, который нам нужно вставить. И затем сливаем две кучи в одну.   
  
 
Есть два случая слияния:
 
Есть два случая слияния:
  
 
#Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
 
#Минимальный ранг дерева в куче равен нулю. Тогда сливаем две кучи в одну с помощью <tex>\mathrm{merge}</tex>. Время работы <tex>O(\log n)</tex>.
#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(\log n)</tex>.
+
#Минимальный ранг дерева в куче отличен от нуля. Тогда присоединяем к созданной куче ту, в которую нужно добавить элемент. Время работы <tex>O(1)</tex>.
  
 
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
 
Тогда амортизационная стоимость одной операции <tex>\mathrm{insert}</tex> составляет <tex>O(1)</tex>.
Строка 194: Строка 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  
Строка 214: Строка 220:
 
|[[File:PersistentBinomialHeapExample1_5.png]]
 
|[[File:PersistentBinomialHeapExample1_5.png]]
 
|}
 
|}
 +
 
==== extractMinimum ====
 
==== extractMinimum ====
  
Работает так же как и в эфемерной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
+
Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
  
 
== Cм. также ==
 
== Cм. также ==
Строка 230: Строка 237:
 
*[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м. также[править]

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