Теневая куча

В информатике — теневая куча это кучи объединяемая структура данных , которая поддерживает эффективное слияние кучи в амортизированном смысле. Более конкретно, теневые кучи используют алгоритм теневого слияния для достижения вставки за амортизированное время O (f( n )) и удаления за амортизированное время O ((log n log log n )/f( n )) для любого выбора 1 ≤ f( n ) ≤ журнал журнал n .

В этой статье предполагается, что A и B — двоичные кучи с | А | ≤ | Б |.

Слияние теней

Теневое слияние — это алгоритм эффективного объединения двух двоичных куч, если эти кучи реализованы как массивы . В частности, время выполнения слияния теней в двух кучах. $A$ и $B$ является $O(|A|+\min\{\log |B|\log \log |B|,\log |A|\log |B|\})$.

Алгоритм

Мы хотим объединить две двоичные минимальные кучи. $A$ и $B$. Алгоритм следующий:

1. Объединить массив $A$ в конце массива $B$ чтобы получить массив $C$.
2. Определите тень ​ $A$ в $C$; то есть предки последних $|A|$ узлы в $C$ которые разрушают свойство кучи.
3. Определите следующие две части тени от $C$:
   • Путь ​ $P$: набор узлов в тени, для которых имеется не более 2 на любой глубине. $C$;
   • Поддерево ​ $T$: остаток тени.
4. Извлеките и отсортируйте самые маленькие $|P|$ узлы из тени в массив $S$.
5. Трансформировать $S$ следующее:
   • Если $|S|>|C|$, затем, начиная с наименьшего элемента отсортированного массива, последовательно вставьте каждый элемент $S$ в $C$, заменив их на $C$мельчайшие элементы.
   • Если $|S|\leq |C|$, затем извлеките и отсортируйте $|P|$ мельчайшие элементы из $C$и объединить этот отсортированный список с $S$.
6. Замените элементы $S$ на свои исходные позиции в $C$.
7. Сделать кучу из $T$.

Время работы

Опять же, пусть $P$ обозначают путь и $T$ обозначаем поддерево объединенной кучи $C$. Количество узлов в $P$ не более чем в два раза превышает глубину $C$, что $O(\log |B|)$. Кроме того, количество узлов в $T$ на глубине $d$ составляет не более 3/4 количества узлов на глубине $d+1$, поэтому поддерево имеет размер $O(|A|)$. Поскольку на каждом уровне имеется не более 2 узлов $P$, затем читаем самый маленький $|P|$ элементы тени в отсортированный массив $S$ берет $O(\log |B|)$ время.

Если $|S|>|C|$, затем объединив $P$ и $C$ как и в шаге 5 выше, требуется время $O(\log |A|\log |B|)$. В противном случае время, затраченное на этом этапе, равно $O(|A|+\log |B|\log \log |B|)$. Наконец, создание кучи поддерева $T$ берет $O(|A|)$ время. Это составляет общее время выполнения теневого слияния $O(|A|+\min\{\log |A|\log |B|,\log |B|\log \log |B|\})$.

Структура

Теневая куча $H$ состоит из пороговой функции $f(H)$и массив , для которого обычное свойство двоичной кучи , реализованное в массиве, поддерживается в его первых записях и для которого свойство кучи не обязательно поддерживается в других записях. Таким образом, теневая куча по сути представляет собой двоичную кучу. $B$ рядом с массивом $A$. Чтобы добавить элемент в теневую кучу, поместите его в массив $A$. Если массив становится слишком большим в соответствии с указанным порогом, мы сначала создаем кучу из $A$ используя алгоритм Флойда для построения кучи, а затем объединить эту кучу с $B$ использование слияния теней. Наконец, объединение теневых куч просто осуществляется путем последовательной вставки одной кучи в другую с использованием описанной выше процедуры вставки.

Анализ

Нам дана теневая куча $H=(B,A)$, с пороговой функцией $\log |H|\leq f(H)\leq \log |H|\log \log |H|$ как указано выше. Предположим, что пороговая функция такова, что любое изменение $|B|$ не вызывает больших изменений, чем в $f(H)$. Мы получаем желаемые границы времени выполнения операций объединяемой кучи , используя потенциальный метод амортизированного анализа . Потенциал $\Psi (H)$ кучи выбирается следующим образом:

$\Psi (H)=|A|(1+\min\{\log |B|\log \log |B|,\log |B|\log |A|\}/f(H))$

Используя этот потенциал, мы можем получить желаемое амортизированное время работы:

create( H ) : инициализирует новую пустую теневую кучу $H$

Здесь потенциал $\Psi$ остается неизменной, поэтому амортизированная стоимость создания равна $O(1)$, фактическая стоимость.

вставить( x , H ) : вставляет $x$ в теневую кучу $H$

Есть два случая:

• Если используется слияние, то падение потенциальной функции равно точно фактической стоимости слияния. $B$ и $A$, поэтому амортизированная стоимость равна $O(1)$.
• Если слияние не произведено, то амортизированная стоимость составит $O(1+\min\{\log |B|\log \log |B|,\log |B|\log |A|\}/f(H))$

Таким образом, выбрав пороговую функцию, мы получаем, что амортизированная стоимость внедрения равна:

$O(\log |H|\log \log |H|/f(H))$

delete_min( H ) : удаляет элемент с минимальным приоритетом из $H$

Поиск и удаление минимума занимает фактическое время $O(|A|+\log |B|)$. При этом потенциальная функция после такого исключения может увеличиться только в том случае, если значение $f(H)$ уменьшается. По выбору $f$, имеем, что амортизированная стоимость данной операции равна фактической стоимости.

Связанные алгоритмы и структуры данных

Наивный алгоритм слияния двоичной кучи объединит две кучи. $A$ и $B$ вовремя $O(|B|)$ путем простого объединения обеих куч и создания кучи из полученного массива с использованием алгоритма Флойда для построения кучи. Альтернативно, кучи можно просто объединить, последовательно вставляя каждый элемент. $A$ в $B$, требуется время $O(|A|\log |B|)$.

Сак и Стротхотт предложили алгоритм объединения двоичных куч в $O(|A|+\log |A|\log |B|)$ время. Их алгоритм, как известно, более эффективен, чем второе наивное решение, описанное выше, примерно, когда $|A|>\log |B|$. Слияние теней работает асимптотически лучше, чем их алгоритм, даже в худшем случае.

Есть несколько других куч, которые поддерживают более быстрое слияние. Например, кучи Фибоначчи можно объединить в $O(1)$ время. Поскольку двоичные кучи требуют $\Omega (|A|)$ время объединиться, слияние теней остается эффективным.