2–3 кучи

Эта статья может быть слишком технической для понимания большинства читателей . Пожалуйста, помогите улучшить ее, чтобы сделать ее понятной для неспециалистов , не удаляя технические детали. ( Апрель 2024 ) ( Узнайте, как и когда удалить это сообщение )

Эта статья в значительной степени или полностью основана на одном источнике . Соответствующее обсуждение можно найти на странице обсуждения . Пожалуйста, помогите улучшить эту статью, добавив ссылки на дополнительные источники . Найти источники:  "2–3 heap" – новости  · газеты  · книги  · ученый  · JSTOR ( май 2024 г. )

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

Временные затраты на некоторые общие операции с кучей следующие:

• Удаление-мин занимает амортизированное время .${\displaystyle O(\log(n))}$
• Уменьшение клавиши занимает постоянное амортизированное время.
• Вставка занимает постоянное амортизированное время.

Источник: ^[1]

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

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

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

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

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

Источник: ^[1]

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

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

Delete-min : Сначала найдите минимум, просматривая корень деревьев. Пусть будет деревом, содержащим минимальный элемент, а пусть будет результатом удаления корня из . Затем выполните слияние и (Операция слияния похожа на слияние двух r-номиальных очередей ).${\displaystyle T(i)}$${\displaystyle Q}$${\displaystyle T(i)}$${\displaystyle P-T(i)}$${\displaystyle Q}$

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

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