Косая биномиальная куча

Не путать со Skew heap .

Косая биномиальная куча
Тип	куча
Изобретенный	1996
Изобретён	Герт Столтинг Бродал и Крис Окасаки
Временная сложность в обозначении большого О Операция Средний Худший случай Вставлять я (1) я (1) Найти-мин я (1) Удалить-мин. О( вход ) Клавиша уменьшения О( вход ) Объединить О( вход ) Пространственная сложность

В информатике ( косая биномиальная куча или косая биномиальная очередь ) — это структура данных для операций приоритетной очереди . Это вариант биномиальной кучи , который в худшем случае поддерживает операции вставки с постоянным временем, а не с амортизированным временем .

Мотивация

Так же, как биномиальные кучи основаны на двоичной системе счисления , косые двоичные кучи основаны на косой двоичной системе счисления . Обычные биномиальные кучи страдают от логарифмической сложности вставки в наихудшем случае, поскольку операция переноса может быть каскадной, аналогично двоичному сложению. Косые биномиальные кучи основаны на косой двоичной системе счисления, где $k$-я цифра (с нулевым индексом) представляет $2^{k+1}-1$, вместо $2^{k}$. Цифры могут быть либо 0, либо 1, за исключением самой младшей ненулевой цифры, которая может быть 2. Преимущество этой системы состоит в том, что требуется не более одной операции переноса. Например, 60 представлено как 11 200 в асимметричном двоичном формате (31 + 15 + 7 + 7), а добавление 1 дает 12 000 (31 + 15 + 15). Поскольку следующая старшая цифра гарантированно не равна 2, перенос выполняется не более одного раза. Эта аналогия применяется к операции вставки путем введения троичных (косых) связей, которые связывают три дерева вместе. Это позволяет операции вставки выполняться за постоянное время.

Структура

Косая биномиальная куча, содержащая числа от 1 до 19, показывающая деревья рангов 0, 1, 2 и 3, построенные из различных типов ссылок.

Просто: введите « перекос» и типа b. «перекос»

Косая биномиальная куча — это лес косых биномиальных деревьев , которые определяются индуктивно:

• Косое биномиальное дерево ранга 0 является одноэлементным узлом.
• Косое биномиальное дерево рангов $r+1$ можно построить тремя способами:
  • простая ссылка связывает два ранга $r$ деревья, что делает одно крайним левым дочерним элементом другого;
  • соединяет Косая связь типа А три дерева. Два ранга $r$ деревья становятся потомками дерева ранга 0;
  • связывает Косая связь типа B три дерева. Дерево ранга 0 и ранг $r$ дерево станет самым левым потомком другого ранга $r$ дерево.

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

Следующий код OCaml демонстрирует операции связывания:

type 'a heap = 'a tree list
 and 'a tree = Tree of 'a * int * 'a tree list
 
let rank (Tree (_, r, _)) = r

let simple_link (Tree (k1, r, c1) as t1) (Tree (k2, r, c2) as t2) =
  if k1 <= k2 then
    Tree (k1, r + 1, t2 :: c1)
  else
    Tree (k2, r + 1, t1 :: c2)
    
let skew_link k1 (Tree (k2, r, c2) as t2) (Tree (k3, r, c3) as t3) =
  if k1 <= k2 && k1 <= k3 then (* type A *)
    Tree (k1, r + 1, [t2; t3])
  else                         (* type B *)
    let t1 = Tree (k1, 0, []) in
    if k2 <= k3 then
      Tree (k2, r + 1, t1 :: t3 :: c2)
    else
      Tree (k3, r + 1, t1 :: t2 :: c3)

Из этих свойств можно вывести, что корень ранга $r$ скошенное биномиальное дерево имеет до $2r$ дети. Количество узлов в косом биномиальном дереве $t$ ранга $r$ также ограничено $2^{r}\leq |t|\leq 2^{r+1}-1$. Поскольку деревья одного и того же ранга могут иметь разное количество узлов, может существовать более одного способа распределения рангов в куче.

Эти конструкции можно рассматривать как обобщение бинарных и биномиальных деревьев. Косое биномиальное дерево, построенное с использованием только простых связей, является обычным биномиальным деревом, а использование только косых связей типа А приводит к идеально сбалансированному двоичному дереву.

Операции

Найти-мин

Найдите в списке корней узел, содержащий минимальный ключ. Это занимает $O(\log n)$ время.

В императивной настройке можно сохранить указатель на корень, содержащий минимальный ключ, разрешая доступ в $O(1)$ время. Этот указатель должен обновляться после каждой операции, добавляя лишь постоянные накладные расходы по временной сложности.

В функциональной настройке без произвольного доступа к узлам вместо этого можно представить кучу как одно дерево с косыми биномиальными деревьями в качестве его дочерних элементов. Корень этого дерева — минимум кучи, что позволяет $O(1)$ доступ. Обратите внимание, что это дерево не обязательно само по себе будет косым биномиальным деревом. Остальные операции необходимо изменить для работы с этим единственным деревом. Эта концепция глобального корня используется в описанных ниже оптимизациях , хотя и немного по-другому.

Объединить

Чтобы объединить две косые биномиальные кучи, сначала удалите все повторяющиеся деревья ранга в каждой куче, выполнив простые связи . Затем объедините кучи так же, как обычные биномиальные кучи, что похоже на двоичное сложение. Деревья с одинаковыми рангами связываются простой ссылкой , и при необходимости дерево переноса передается вверх. Поскольку ранг деревьев в каждой куче теперь уникален, рассматриваются не более трех деревьев одного ранга, что достаточно для установления $O(\log n)$ граница.

let rec unique = function
  | t1 :: t2 :: ts when rank t1 = rank t2 ->
    unique (simple_link t1 t2 :: ts)
  | ts -> ts

let rec merge_uniq h1 h2 = match h1, h2 with
  | h1, [] -> h1
  | [], h2 -> h2
  | t1 :: ts1, t2 :: ts2 ->
    if rank t1 < rank t2 then
      t1 :: merge_uniq ts1 h2
    else if rank t1 > rank t2 then
      t2 :: merge_uniq h1 ts2
    else
      unique (simple_link t1 t2 :: merge_uniq ts1 ts2)
  
let merge h1 h2 = merge_uniq (unique h1) (unique h2)

Вставить

Создайте косое биномиальное дерево ранга 0 (одноэлементный узел), содержащее вставляемый ключ. Затем рассматриваются два самых маленьких дерева в куче:

• Если они оба имеют ранг $r$, затем выполните косую связь с этими двумя деревьями и одноэлементным узлом. Полученное дерево имеет ранг $r+1$. Поскольку мог быть только один ранг $r+1$ дерево в исходной куче, инвариант сохраняется.
• Если они имеют разные ранги, просто добавьте дерево ранга 0 в начало списка корней. Поскольку ранее список корней не имел повторяющихся деревьев ранга, инвариант не нарушается, так как после него будет не более двух деревьев ранга 0.

Поскольку выполняется до одной ссылки, эта операция выполняется в худшем случае. $O(1)$ время, улучшая биномиальную кучу, которая опирается на амортизированный анализ для своего $O(1)$ связанный, с наихудшим случаем $O(\log n)$.

let insert k = function
  | t2 :: t3 :: ts when rank t2 = rank t3 -> skew_link k t2 t3 :: ts
  | ts -> Tree (k, 0, []) :: ts

Удалить-моё

Найдите и отбросьте узел, содержащий минимальный ключ. Этот узел должен быть корнем дерева. может быть более двух дочерних элементов с рангом 0 Разделите его дочерние элементы на две группы: группы с рангом 0 и группы с рангом > 0. Обратите внимание, что из-за перекоса связей . Дочерние элементы, ранг которых > 0, образуют действительную косую биномиальную кучу, поскольку они уже упорядочены и не имеют дубликатов. Объединение этих детей в кучу занимает $O(\log n)$ время. После этого повторно вставьте в кучу каждого дочернего элемента ранга 0 по цене $O(1)$ каждый. Общее время, необходимое для $O(\log n)$.

Клавиша уменьшения

Эта операция не отличается от биномиальных куч. Уменьшение ключа узла может привести к тому, что он станет меньше своего родителя. Неоднократно обменивайте его с родительским элементом до тех пор, пока не будет удовлетворено свойство минимальной кучи , затрачивая $O(\log n)$ временная сложность. Для этой операции требуется указатель на узел, содержащий рассматриваемый ключ, и ее проще всего выполнить в императивной настройке.

Оптимизации

Бродал и Окасаки показали, как можно сократить временную сложность операции слияния до $O(1)$, применив технику «бутстреппинга» Буксбаума и Тарьяна .

Пусть тип примитивной косой биномиальной кучи, содержащей элементы типа $\alpha$ быть $H_{\alpha }$. Вместо представления леса деревьев, описанного выше, мы поддерживаем одно дерево с глобальным корнем как минимум.

Пусть тип корневой косой биномиальной кучи будет

$R_{\alpha }=\alpha \times H_{R_{\alpha }}$,

то есть пара, содержащая элемент типа $\alpha$ и примитивная куча корневых куч.

Наконец, мы определяем тип самозагруженной кучи , заключая корневые кучи в параметр type :

$B_{\alpha }=\{\mathrm {Empty} \}+R_{\alpha }$

что допускает пустую кучу.

Операции над этой самозагруженной кучей переопределяются соответствующим образом. В следующем коде OCaml простой символ ' обозначает операции для самозагруженных куч.

type 'a bootstrapped =
  | Empty
  | Root of 'a rooted

let find_min' (Root (k, h)) = k

let merge' bh1 bh2 = match bh1, bh2 with
  | _, Empty -> bh1
  | Empty, _ -> bh2
  | Root (k1, h1), Root (k2, h2) ->
    if k1 <= k2 then
      Root (k1, insert bh2 h1)
    else
      Root (k2, insert bh1 h2)

let insert' k h = merge' (Root(k, [])) h

let delete_min' (Root (x, h)) =
  let Root (y, h1) = find_min h in
  let h2 = delete_min h in
  Root (y, merge h1 h2)

Новая операция слияния использует только операции вставки в примитивные кучи. Таким образом, он выполняется в $O(1)$ время. Этот метод можно применить к любой приоритетной очереди с вставкой постоянного времени и логарифмическим слиянием.

Сводка времени работы

Вот временные сложности различных структур данных кучи. Имена функций предполагают минимальную кучу. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. .

Операция	найти-мин	удаление-мин	вставлять	клавиша уменьшения	сливаться
Двоичный	я (1)	Θ (логарифм n )	О ( войти )	О ( войти )	Θ ( н )
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	О ( войти )	Θ (логарифм n )
Биномиальный	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О ( войти )
Наклонный бином	я (1)	Θ (логарифм n )	я (1)	Θ (логарифм n )	О ( войти )
Сопряжение	я (1)	О ( войти )	я (1)	о ( войти )	я (1)
Сопряжение по рангам	я (1)	О ( войти )	я (1)	я (1)	я (1)
Фибоначчи	я (1)	О ( войти )	я (1)	я (1)	я (1)
Строгий Фибоначчи	я (1)	О ( войти )	я (1)	я (1)	я (1)
Мостовая долина	я (1)	О ( войти )	я (1)	я (1)	я (1)
2–3 кучи	я (1)	О ( войти )	я (1)	я (1)	О ( войти )