Рандомизированная объединяемая куча

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

Этот подход имеет ряд преимуществ перед аналогичными структурами данных. Он обеспечивает большую простоту: все операции для рандомизированной объединяемой кучи легко реализовать, а постоянные коэффициенты в их границах сложности невелики. Также нет необходимости сохранять условия баланса и не требуется никакой спутниковой информации внутри узлов. Наконец, эта структура имеет хорошую эффективность использования времени в худшем случае. Время выполнения каждой отдельной операции не более чем логарифмическое с высокой вероятностью. ^[1]

Операции

Рандомизированная объединяемая куча поддерживает ряд распространенных операций. Это вставка, удаление и операция поиска findMin. Операции вставки и удаления реализованы с помощью дополнительной операции, специфичной для объединяемой кучи, Meld(Q1, Q2).

Слияние

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

Приятной особенностью этой операции объединения является то, что ее можно определить рекурсивно. Если какая-либо из куч равна нулю, то слияние происходит с пустым набором, и метод просто возвращает корневой узел непустой кучи. Если оба Q1 и Q2 не равны нулю, проверьте, Q1> Q2. Если да, поменяйте местами два. Таким образом, гарантируется, что Q1 < Q2 и что корневой узел объединенной кучи будет содержать Q1. Затем мы рекурсивно объединяем Q2 с Q1.left или Q1.right. На этом этапе происходит рандомизация, поскольку решение о том, с какой стороной сливаться, определяется подбрасыванием монеты.

function Meld(Node Q1, Node Q2)
    if Q1 is nil => return Q2
    if Q2 is nil => return Q1
    if Q1 > Q2 => swap Q1 and Q2
    if coin_toss is 0 => Q1.left = Meld(Q1.left, Q2)
    else Q1.right = Meld(Q1.right, Q2)
    return Q1

Вставлять

Когда операция объединения завершена, вставка в объединяемую кучу становится проще. Сначала создается новый узел u, содержащий значение x. Затем этот новый узел просто объединяется с корневым узлом кучи.

function Insert(x)
    Node u = new Node
    u.x = x
    root = Meld(u, root)
    root.parent = nil
    increment node count

Удалять

Функция Remove(), аналогичная операции вставки, использует операцию Meld для удаления корневого узла из кучи. Это делается путем простого объединения двух дочерних узлов корневого узла и превращения возвращенного узла в новый корень.

function Remove()
    root = Meld(root.left, root.right)
    if root is not nil => root.parent = nil
    decrement node count

НайтиМин

Возможно, самая простая операция для рандомизированной объединяемой кучи. FindMin() просто возвращает элемент, хранящийся в данный момент в корневом узле кучи.

Дополнительные операции

Некоторые дополнительные операции, которые можно реализовать для объединяемой кучи, которые также имеют эффективность O (log n ) в худшем случае:

Remove(u) — Удалить узел u и его ключ из кучи.
Absorb(Q) — добавить все элементы объединяемой кучи Q в эту кучу, опустошая при этом Q.
DecreaseKey(u, y) — Уменьшает ключ в узле u до y (предварительное условие: y <= ux).

Анализ эффективности

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

Результатом этого анализа является то, что ожидаемое время любой объединяемой операции очереди с приоритетами в рандомизированной куче из n узлов равно O (log n ). ^[1]^[2]

Операция	Наихудшая экономия времени
Объединение (Q1, Q2)	О (логарифм n )
Вставить(х)	О (логарифм n )
Удалять()	О (логарифм n )
НайтиМин()	О ( 1 )
Удалить(х)	О (логарифм n )
Поглощение(клавиша Q)	О (логарифм n )

История

Сплавляемая куча, по-видимому, впервые была предложена в 1998 году Гамбином и Малиновским. ^[1]

Варианты

Хотя рандомизированная объединяемая куча является простейшей формой реализации объединяемой кучи, существуют и другие. Это:

Ссылки

^ Перейти обратно: ^а ^б ^с А. Гамбин и А. Малиновский. 1998. Рандомизированные очереди с объединяемыми приоритетами. В материалах 25-й конференции «Современные тенденции в теории и практике информатики: теория и практика информатики» (SOFSEM '98), Бранислав Рован (ред.). Спрингер-Верлаг, Лондон, Великобритания, Великобритания, 344–349.
^ П. Морин , [1] Открытые структуры данных, с. 191-

[Gambin-1] Перейти обратно: ^а ^б ^с А. Гамбин и А. Малиновский. 1998. Рандомизированные очереди с объединяемыми приоритетами. В материалах 25-й конференции «Современные тенденции в теории и практике информатики: теория и практика информатики» (SOFSEM '98), Бранислав Рован (ред.). Спрингер-Верлаг, Лондон, Великобритания, Великобритания, 344–349.

[Morin-2] П. Морин , [1] Открытые структуры данных, с. 191-

[1]

[2]