Рандомизированная объединяемая куча - Randomized meldable heap - Wikipedia

В информатике случайная объединяемая куча (также Плавящийся Куча или же Рандомизированный смешиваемый Приоритетная очередь ) является приоритетной очередью на основе структура данных в котором основная структура также упорядочена в куче двоичное дерево. Однако нет никаких ограничений на форму базового двоичного дерева.

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

Операции

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

Meld

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

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

функция Meld (Узел Q1, Узел Q2)    если Q1 равно нулю => возвращаться Q2    если Q2 равно нулю => возвращаться Q1    если Q1 > Q2 => поменять местами Q1 и Q2    если coin_toss равно 0 => Q1.оставили = Meld (Q1.оставили, Q2)    еще Q1.верно = Meld (Q1.верно, Q2)    возвращаться Q1

Вставлять

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

функция Вставить (x) Узел u = новый узел    u.x = x root = Meld (u, root) root.parent = nil приращение количества узлов

Удалять

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

функция Remove () root = Meld (root.left, root.right) если root не равен nil => root.parent = nil количество узлов уменьшения

FindMin

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

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

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

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

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

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

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

Операция	Экономия времени в наихудшем случае
Meld (Q1, Q2)	О(бревноп)
Вставить (x)	О(бревноп)
Удалять()	О(бревноп)
FindMin ()	О(1)
Удалить (x)	О(бревноп)
Поглощение (клавиша Q)	О(бревноп)

История

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

Варианты

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