2–3 кучи

В информатике куча 2–3 — это структура данных , разновидность кучи , разработанная Тадао Такаокой в ​​1999 году. Структура аналогична куче Фибоначчи и заимствована из дерева 2–3 .

Затраты времени на некоторые распространенные операции с кучей составляют:

• Удалить – мин. дублей $O(\log(n))$ амортизированное время .
• Уменьшение клавиши занимает постоянное амортизируемое время.
• Вставка занимает постоянное амортизированное время.

Полином деревьев

Источник:

Линейное дерево размера $r$ представляет собой последовательный путь $r$ узлы, первый из которых является корнем дерева и выделен жирным шрифтом. $\mathbf {r}$ (например $\mathbf {1}$ представляет собой линейное дерево из одного узла). Продукт $P=ST$ из двух деревьев $S$ и $T$, представляет собой новое дерево с каждым узлом $S$ заменяется копией $T$ и для каждого ребра $S$ соединяем корни деревьев, соответствующие концам ребра. Обратите внимание, что это определение продукта является ассоциативным, но не коммутативным. Сумма $S+T$ из двух деревьев $S$ и $T$ это совокупность двух деревьев $S$ и $T$.

R-арный полином деревьев определяется как $P=\mathbf {a} _{k-1}\mathbf {r} ^{k-1}+\dots +\mathbf {a} _{1}\mathbf {r} +\mathbf {a} _{0}$ где $0\leq a_{i}\leq r-1$. Это полиномиальное обозначение для деревьев $n$ узлы уникальны. Дерево $\mathbf {a} _{i}\mathbf {r} ^{i}$ на самом деле $a_{i}$ копия $\mathbf {r} ^{i}$ что их корни связаны с $a_{i}-1$ ребра последовательно и путь этих $a_{i}-1$ край называется основным стволом дерева $\mathbf {a} _{i}\mathbf {r} ^{i}$. Кроме того, r-арный многочлен деревьев называется r-номиальной очередью, если узлы многочлена деревьев связаны с ключами в свойстве кучи.

Операции над r-номиальными очередями

Чтобы объединить два термина формы $\mathbf {a} _{i}\mathbf {r} ^{i}$ и $\mathbf {a} '_{i}\mathbf {r} ^{i}$мы просто переупорядочиваем деревья в основном стволе на основе ключей в корне деревьев. Если $a_{i}+a'_{i}\geq r$ у нас будет срок формы $(\mathbf {a} _{i}+\mathbf {a} '_{i}-\mathbf {r} )\mathbf {r} ^{i}$ и дерево для переноски $\mathbf {r} ^{i+1}$. Иначе у нас было бы только дерево $(\mathbf {a} _{i}+\mathbf {a} '_{i})\mathbf {r} ^{i}$. Таким образом, сумма двух r-номиальных очередей на самом деле аналогична сложению двух чисел в системе счисления. $r$.

Вставка ключа в полиномиальную очередь аналогична объединению одного узла с меткой ключа в существующую r-номиальную очередь, принимая $O(r\log _{r}{n})$ время.

Чтобы удалить минимум, сначала нам нужно найти минимум в корне дерева, скажем $T$, то удаляем минимум из $T$ и добавляем полученную полиномиальную очередь $Q$ к $P-T$ за общее время $O(r\log _{r}{n})$.

(2,3)-куча

Источник:

Ан $(l,r)-$ дерево $T(i)$ определяется рекурсивно $T(i)=T_{1}(i-1)\triangleleft \dots \triangleleft T_{s}(i-1)$ для $i\geq 1$ ( $s$ находится между $l$ и $r$ и $(s-1)$ $\triangleleft$ операции оцениваются справа налево), где для двух деревьев $A$ и $B$, результат операции $A\triangleleft B$ соединяет корень $B$ как самый правый ребенок в корне $A$ и $T(0)$ представляет собой дерево с одним узлом. Обратите внимание, что корень дерева $T(i)$ имеет степень $i$.

Расширенный полином деревьев, $P$, определяется $P=a_{k-1}T(k-1)+\dots +a_{1}T(1)+a_{0}$. Если мы назначаем ключи узлам расширенного многочлена деревьев в кучном порядке, это называется $(l,r)-heap$и частный случай $l=2$ и $r=3$ называется $(2,3)-heap$.

Операции над (2,3)-кучей

Удалить-мин : сначала найдите минимум, сканируя корень деревьев. Позволять $T(i)$ — дерево, содержащее минимальный элемент, и пусть $Q$ быть результатом удаления корня из $T(i)$. Затем объединить $P-T(i)$ и $Q$ (Операция слияния аналогична слиянию двух r-номиальных очередей ).

Вставка : чтобы вставить новый ключ, объедините существующую (2,3)-кучу с одним деревом узлов, $T(0)$ помечены этим ключом.

Клавиша уменьшения : Готово!