Редактирование: Персистентная приоритетная очередь

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 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>
* <tex>key</tex> {{---}} ключ (вес) элемента,
+
merge_tree(t1, t2)
* <tex>next</tex> {{---}} указатель на следующий элемент,
+
  if (t1.key < t2.key)
* <tex>child</tex> {{---}} указатель на ребенка с большим рангом,
+
    t2.next = t1.son;
* <tex>degree</tex> {{---}} степень узла (количество дочерних узлов данного узла).
+
    t1.son = t2;
Доступ к куче осуществляется ссылкой на первый корень в списке корней.
+
  else
 
+
    t1.next = t2.son;
=== Операции ===
+
    t2.son = t1;
 
+
</pre>
==== getMinimum ====
+
Проход по корневым спискам выполнится за <tex>O(logN)</tex>, объединение деревьев выполняется за <tex>O(1)</tex>. Тогда <tex>merge</tex> работает за <tex>O(logN)</tex>.
 
 
Для нахождения минимального элемента необходимо пройти по списку корней дерева. Можно это сделать за <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]]
 
|}
 
  
==== extractMinimum ====
+
а) Минимальный ранг дерева <tex>k</tex> и такое дерево одно. Добавим новое дерево ранга 0 - нашу вершину.
  
Работает так же как и в обычной [[Биномиальная куча|биномиальной куче]]. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи. Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Время работы операции <tex>O(\log n)</tex>.
+
б) Минимальный ранг дерева <tex>k</tex> и таких деревьев два. Объединим эти деревья и нашу вершину в дерево ранга <tex>k+1</tex>, получим дерево типа 1 или 2 в зависимости от того у какой вершины ключ меньше.
  
== Cм. также ==
+
Тогда <tex>insert</tex> работает за <tex>O(1)</tex>.
  
* [[Приоритетные очереди]]
+
=== 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/Очередь_с_приоритетом_(программирование) Википедия {{---}} Очередь с приоритетом]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Приоритетные очереди]]
 
[[Категория: Приоритетные очереди]]
[[Категория: Структуры данных‏‎]]
 
[[Категория: Персистентные структуры данных]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: