Персистентная приоритетная очередь

Персистентная приоритетная очередь (англ. 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] новых вершин.

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, y)
  else
    return Node(y, 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)

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

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

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

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, y):
  if x == [math] \varnothing [/math]: 
      return y
  if y == [math] \varnothing [/math]: 
      return x
  if y.key < x.key:
      swap(x, y)
  z = LeftistHeap(x.left, merge(x.right, y), x.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] элементов. На рисунке это корень второго дерева в куче.

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] (на рисунке выделены черным). Затем их слили, появились два новых узла, которые обращаются по прежнему к старым поддеревьям (выделено красным).

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

insert

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

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

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

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

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

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

Пример работы. Пусть дана куча:

Вставим в кучу элемент, с ключом, равным 3. В данном случае выполняется условие под пунктом б). Тогда получим:

Теперь вставим в эту же кучу элемент, с ключом, равным 4. Эта ситуация соответствует пункту а). Получим:

extractMinimum

Работает так же как и в эфемерной биномиальной куче. Проходим по списку корней и находим вершину с минимальным ключом. Затем извлекаем дерево, которое хранит минимальный ключ. Сортируем детей в дереве с минимальным ключом по возрастанию ранга. Сливаем две кучи.

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
  //расставляем детей в удаленном дереве в возрастающем порядке с помощью вспомогательного массива nodes
  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)

Функция возвращает минимальный ключ и новую кучу после извлечения минимума. Работает за [math]O(\log n)[/math].

Cм. также

• Приоритетные очереди
• Персистентные структуры данных
• Биномиальная куча
• Левосторонняя куча
• Персистентная очередь

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

• Лекция А.С. Станкевича по приоритетным очередям
• Лекция П.Ю. Мавривна по персистентным структурам данных
• Википедия - Очередь с приоритетом