Строгая куча Фибоначчи

Строгая куча Фибоначчи
Тип	Куча
Изобретенный	2012
Изобретён	Герт С. Бродал, Джордж Лагояннис и Роберт Э. Тарьян
Сложности в обозначении большого О
Пространственная сложность Космос На ) Временная сложность Функция Амортизированный Худший случай Вставлять О (1) Найти-мин О (1) Удалить-мин. О (логарифм n ) Клавиша уменьшения О (1) Объединить О (1)

В информатике строгая куча Фибоначчи — это очереди с приоритетом структура данных и минимальными временными границами для наихудшего случая . он соответствует амортизированным временным границам кучи Фибоначчи В худшем случае . Чтобы достичь этих временных ограничений, строгие кучи Фибоначчи поддерживают несколько инвариантов , выполняя восстанавливающие преобразования после каждой операции. Эти преобразования могут выполняться за постоянное время с использованием вспомогательных структур данных для отслеживания нарушений инвариантов, а принцип «ячейки» гарантирует, что их можно исправить. Строгие кучи Фибоначчи были изобретены в 2012 году Гертом С. Бродалом , Джорджем Лагояннисом и Робертом Э. Тарджаном .

Наряду с очередями Бродала , строгие кучи Фибоначчи относятся к классу асимптотически оптимальных структур данных для приоритетных очередей. Все операции со строгими кучами Фибоначчи выполняются в худшем случае с постоянным временем, за исключением delete-min , которое обязательно является логарифмическим. Это оптимально, поскольку для сортировки списка можно использовать любую приоритетную очередь. $n$ элементы, выполняя $n$ вставки и $n$ операции удаления минимума . Однако строгие кучи Фибоначчи проще, чем очереди Бродала, в которых используются динамические массивы и избыточные счетчики. тогда как строгая куча Фибоначчи основана только на указателях .

Структура

Строгая куча Фибоначчи без потерь. Узлы 5 и 2 являются активными корнями. Их активные поддеревья являются биномиальными деревьями.

Строгая куча Фибоначчи — это одно дерево, удовлетворяющее свойству минимальной кучи . То есть ключ узла всегда меньше или равен его дочерним узлам. Как прямое следствие, узел с минимальным ключом всегда находится в корне.

Как обычные кучи Фибоначчи, Строгие кучи Фибоначчи обладают подструктурами, подобными биномиальным кучам . Чтобы идентифицировать эти структуры, мы маркируем каждый узел одним из двух типов. Таким образом, мы вводим следующие определения и правила:

• Все узлы либо активны (окрашены в белый цвет ), либо пассивны (окрашены в красный цвет ) .
• Активный корень — это активный узел с пассивным родителем.
• Пассивный связываемый узел — это пассивный узел, все его потомки являются пассивными (пассивный узел без дочерних элементов считается связываемым).
• Ранг . активного узла — это количество его активных дочерних элементов
• Потеря . активного узла — это количество потерянных активных дочерних узлов
• Для любого узла активные дочерние элементы лежат слева от пассивных дочерних узлов.
• Активный корень всегда имеет нулевые потери.
• Корень пассивный.
• Пассивные связываемые дочерние элементы корня лежат справа от пассивных несвязываемых дочерних элементов.

Инварианты

Инвариант 1: Структура

The $i$самый правый активный ребенок $c_{i}$ активного узла удовлетворяет $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1$.

Таким образом, потерю активного узла можно рассматривать как обобщение «меток» кучи Фибоначчи . Например, поддерево, состоящее только из активных узлов с нулевыми потерями, является биномиальным деревом .

Кроме того, несколько инвариантов, которые накладывают логарифмические ограничения на три основные величины: количество активных корней, общие потери и степени узлов. В этом отличие от обычной кучи Фибоначчи, которая более гибкая и позволяет структурным нарушениям расти порядка $O(n)$ его нужно очистить позже, так как это ленивая структура данных.

Чтобы поддерживать логарифмичность степеней узлов, каждый некорневой узел также участвует в очереди. $Q$. В следующем разделе и в оставшейся части этой статьи мы определяем действительное число. $R=2\lg n+6$, где $n$ количество узлов в куче, а $\lg$ обозначает двоичный логарифм .

Инвариант 2: Активные корни

Общее число активных корней не более $R+1$.

Инвариант 3: Полная потеря

Общие потери в куче не превышают $R+1$.

Инвариант 4: Корневая степень

Степень корня не более $R+3$.

Инвариант 5: Некорневые степени

Для активного узла с нулевыми потерями степень не более $2\lg(2n-p)+10$, где $p$ это его положение в $Q$ (с 1 в качестве первого элемента). Для всех остальных некорневых узлов степень не превышает $2\lg(2n-p)+9$.

Следствие 1: Максимальная степень

Степень любого некорневого узла не более $R+6$.

Доказательство :

Это непосредственно следует из инварианта 5. Полагая $p=0$, у нас есть

$2\lg(2n-0)+10=2\lg n+12=R+6$

Лемма 1: Максимальный ранг

Если соблюдается инвариант 1, максимальный ранг $r$ или любой активный узел не более $\lg n+{\sqrt {2L}}+2$, где $L$ это общая потеря.

Доказательство :

Мы действуем от противного. Позволять $x$ быть активным узлом максимального ранга $r$ в куче с $n$ узлы и полная потеря $L$и предположим, что $r\geq \lg n+k+1$, где $k$ — наименьшее целое число такое, что $k(k+1)/2\geq L$. Наша цель — показать, что поддерево $T_{x}$ укорененный в $x$ содержит $n+1$ узлов, что является противоречием, поскольку существуют только $n$ узлы в куче.

Отбросить все поддеревья, коренящиеся в пассивных узлах из $T_{x}$, оставив в нем только активные узлы. Отрезать всех внуков $x$ чьи поддеревья содержат любой узел положительных потерь, и увеличивают потери потомков $x$ соответственно, по одному разу за каждого потерянного внука. Количество $\mathrm {rank} +\mathrm {loss}$ для остальных узлов не изменяется, сохраняя инвариант 1. При этом общие потери по-прежнему не превосходят $L$.

Дети $x$ теперь состоит из поддеревьев без потерь и листовых узлов с положительными потерями. В настоящее время, $T_{x}$ удовлетворяет $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1$ для $i$самый правый ребенок $c_{i}$ из $x$. Мы добиваемся точного равенства, сначала уменьшая потери каждого $c_{i}$и при необходимости обрезать внуков. После, $c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} =i-1$ точно. Все остальные потомки $x$ также преобразуются в биномиальные поддеревья путем обрезки дочерних элементов по мере необходимости.

Теперь мы попытаемся восстановить минимальную версию $T_{x}$ начав с биномиального дерева степени $r$, содержащий $2^{r}$ активные узлы. Мы хотим увеличить потери до $L$, но сохраняем звание $x$ как $r$ и количество узлов как можно меньше. Для биномиального дерева степени $r$, имеется по одному ребенку каждой степени от $0$ к $r-1$. Следовательно, существуют $j$ внуки порядка $r-j-1$. Если мы отрежем всех внуков, чья степень $\leq r-k-1$, то мы разрезали ${\textstyle \sum _{j=1}^{k}j=k(k+1)/2}$ внуков, чего достаточно, чтобы довести потери до $L$. Все внуки с высшим образованием $\leq r-k-2$ выживать. Позволять $w$ быть ребенком $x$ со степенью $r-k-1$ и потери 0. По предположению $r-k-1\geq \lg n$, и $w$ является полным биномиальным деревом, поэтому оно имеет по крайней мере $2^{\lg n}=n$ узлы. Поскольку это будет означать $T_{x}$ имеет по крайней мере $n+1$ узлов, мы пришли к противоречию, и, следовательно, $r<\lg n+k+1$. отмечая, что $k<{\sqrt {k(k+1)}}={\sqrt {2L}}$, мы получаем $r<\lg n+{\sqrt {2L}}+2$.

Следствие 2: Максимальный ранг

Если оба инварианта 1 и 3 выполняются, то максимальный ранг равен $R$.

Доказательство :

Из инварианта 3 имеем $L\leq R+1$. Подставляя это в лемму 1, вычисляем следующим образом:

${\begin{aligned}r&\leq \lg n+{\sqrt {2L}}+2\\&\leq \lg n+{\sqrt {2(R+1)}}+2\\&=\lg n+{\sqrt {4\lg n+14}}+2\\&\leq \lg n+{\sqrt {(\lg n)^{2}+2\cdot 4\lg n+4^{2}}}+2\\&=\lg n+(\lg n+4)+2\\&=R\end{aligned}}$

Преобразования

Следующие преобразования восстанавливают вышеуказанные инварианты после выполнения операции приоритетной очереди. Есть три основные величины, которые мы хотим минимизировать: количество активных корней, общие потери в куче и степень корня. Все преобразования можно выполнить в $O(1)$ время, что возможно за счет поддержки вспомогательных структур данных для отслеживания узлов-кандидатов (описано в разделе о реализации).

Активное сокращение корней

Позволять $x$ и $y$ быть активными корнями одинакового ранга $r$и предположим $x.\mathrm {key} \leq y.\mathrm {key}$. Связь $y$ как самый левый ребенок $x$ и повысить ранг $x$ на 1. Если самый правый ребенок $z$ из $x$ пассивен, ссылка $z$ в корень.

Как результат, $y$ больше не является активным корнем, поэтому количество активных корней уменьшается на 1. Однако степень корневого узла может увеличиться на 1,

С $y$ становится $(r+1)$самый правый ребенок $x$, и $y$ имеет ранг $r$, инвариант 1 сохраняется.

Лемма 2: Наличие активной корневой редукции

Если инвариант 2 нарушен, но инварианты 1 и 3 выполняются, то возможна активная корневая редукция.

Доказательство :

Поскольку инвариант 2 нарушен, существует более $R+1$ Имеются активные корни. Из следствия 2 максимальный ранг узла равен $R$. По принципу «ячейки» существует пара активных корней одинакового ранга.

Сокращение потерь

Сокращение потерь на один узел

Позволять $x$ быть активным не-root с потерей не менее 2. Ссылка $x$ к корню, превращая его таким образом в активный корень и сбрасывая его потерю в 0. Пусть исходный родительский элемент $x$ быть $y$. $y$ должен быть активным, так как в противном случае $x$ ранее был активным корнем и, следовательно, не мог иметь положительных потерь. Ранг $y$ уменьшается на 1. Если $y$ не является активным корнем, увеличьте его потерю на 1.

В целом общие потери уменьшаются на 1 или 2. В качестве побочного эффекта степень корня и количество активных корней увеличиваются на 1, что делает его менее предпочтительным по сравнению с уменьшением потерь на два узла, но все же необходимой операцией.

Сокращение потерь на два узла

Позволять $x$ и $y$ быть активными узлами с одинаковым рангом $r$ и потери равны 1, и пусть $z$ быть родителем $y$. Не ограничивая общности, предположим, что $x.\mathrm {key} \leq y.\mathrm {key}$. Отсоединить $y$ от $z$и ссылка $y$ к $x$. Повышайте ранг $x$ на 1 и сбросить потерю $x$ и $y$ от 1 до 0.

$z$ должен быть активным, так как $y$ имел положительные потери и не мог быть активным корнем. Следовательно, ранг $z$ уменьшается на 1. Если $z$ не является активным корнем, увеличьте его потерю на 1.

В целом общие потери уменьшаются на 1 или 2 без побочных эффектов.

Лемма 3: Наличие снижения потерь

Если инвариант 3 нарушается инвариантом 1, но сохраняется инвариант 2, то уменьшение потерь возможно.

Доказательство . Мы снова применим принцип «ячейки». Если инвариант 3 нарушается инвариантом 1, общие потери равны $L=R+2$. Лемму 1 можно переформулировать, чтобы она работала и с $L=R+2$. Таким образом, справедливо следствие 2. Поскольку максимальный ранг $R$, либо существует пара активных узлов с одинаковым рангом и потерей 1, либо активный узел с $\mathrm {loss} \geq 2$. Оба случая предоставляют возможность сокращения потерь.

Уменьшение степени корня

Уменьшение степени корня

Позволять $x$, $y$, и $z$ быть тремя крайними правыми пассивными связываемыми дочерними элементами корня. Отделите их все от корня и отсортируйте так, чтобы $x.\mathrm {key} \leq y.\mathrm {key} \leq z.\mathrm {key}$. Изменять $x$ и $y$ быть активным. Связь $z$ к $y$, связь $y$ к $x$и ссылка $x$ как самый левый дочерний элемент корня. Как результат, $x$ становится активным корнем с рангом 1 и потерей 0. Ранг и потеря $y$ установлено на 0.

Конечным изменением этого преобразования является то, что степень корневого узла уменьшается на 2. В качестве побочного эффекта количество активных корней увеличивается на 1.

Лемма 4. Наличие приведения степени корня.

Если инвариант 4 нарушен, но инвариант 2 выполнен, то возможно понижение степени корня.

Доказательство :

Если инвариант 4 нарушен, то степень корня не меньше $R+4$. Дочерние элементы корня делятся на три категории: активные корни, пассивные несвязываемые узлы и пассивные связываемые узлы. Каждый пассивный несвязываемый узел включает в себя активный корень, поскольку его поддерево содержит по крайней мере один активный узел. Так как число активных корней не более $R+1$Поэтому три крайних правых дочерних элемента корня должны быть пассивно связываемыми.

Краткое содержание

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

Эффект преобразований

	Активные корни	Общая потеря	Корневая степень
Активное сокращение корней	$-1$	$0$	$0{\text{ or }}{+}1$
Уменьшение степени корня	$+1$	$0$	$-2$
Сокращение потерь на один узел	$+1$	${\text{at least }}{-}1$	$+1$
Сокращение потерь на два узла	$0$	$-1{\text{ or }}{-}2$	$0$

Принимая решение о том, какие преобразования выполнять, мы для простоты учитываем только наихудший эффект этих операций. Два типа сокращения потерь также считаются одной и той же операцией. Таким образом, мы определяем «осуществление сокращения потерь» как означающее поочередную попытку каждого типа снижения потерь.

Наихудший эффект преобразований

	Активные корни	Общая потеря	Корневая степень
Активное сокращение корней	$-1$	$0$	$+1$
Уменьшение степени корня	$+1$	$0$	$-2$
Сокращение потерь	$+1$	$-1$	$+1$

Выполнение

Связывание узлов

Чтобы гарантировать, что активные узлы лежат слева от пассивных узлов и сохранить инвариант 1, операция связывания должна размещать активные узлы слева, а пассивные узлы справа. Необходимо, чтобы активные и пассивные узлы сосуществовали в одном списке, поскольку операция слияния превращает все узлы в меньшей куче в пассивные. Если бы они существовали в двух отдельных списках, списки пришлось бы объединить, что невозможно сделать за постоянное время для всех узлов.

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

Поиск узлов-кандидатов

Инвариантные восстанавливающие преобразования полагаются на возможность найти узлы-кандидаты в $O(1)$ время. Это означает, что мы должны отслеживать активные корни с одинаковым рангом, узлы с потерей 1 того же ранга и узлы с потерей не менее 2.

Оригинальная статья Brodal et al. описал список исправлений и список рангов как способ отслеживания узлов-кандидатов.

Список исправлений

Рейтинг-лист и список исправлений

Список исправлений разделен на четыре части:

1. Активные корни, готовые к активной редукции корней – активные корни с партнером того же ранга. Узлы одного ранга остаются смежными.
2. Активные корни еще не готовы к активному сокращению – единственные активные корни для этого ранга.
3. Активные узлы с потерей 1, которые еще не готовы к снижению потерь — единственные активные узлы с потерей 1 для данного ранга.
4. Активные узлы, готовые к сокращению потерь. Сюда входят активные узлы с потерей 1, имеющие партнера того же ранга, и активные узлы с потерей не менее 2, которым не требуется сокращение партнеров. Узлы одного ранга остаются смежными.

Чтобы проверить, возможно ли активное сокращение корня, мы просто проверяем, не пуста ли часть 1. Если он непустой, первые два узла можно удалить и преобразовать. Аналогично, чтобы проверить, возможно ли уменьшение потерь, мы проверяем конец части 4. Если она содержит узел с потерями не менее 2, выполняется уменьшение потерь на один узел. В противном случае, если оба последних узла имеют потерю 1 и имеют один и тот же ранг, выполняется уменьшение потерь на два узла.

Ранг-лист

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

Для каждого узла, представляющего ранг $r$ в рейтинге мы поддерживаем:

• Указатель на первый активный корень в списке исправлений с рангом $r$. Если такого узла не существует, это NULL.
• Указатель на первый активный узел в списке исправлений с рангом $r$ и потеря 1. Если такого узла не существует, это NULL.
• Указатель на узел, представляющий ранг $r+1$ и $r-1$, для облегчения увеличения и уменьшения рангов.

Список исправлений и список рангов требуют обширного учета, который необходимо выполнять всякий раз, когда возникает новый активный узел или когда изменяется ранг или потеря узла.

Общий флаг

Использование общего флага для изменения делает все узлы пассивными в $O(1)$ время

Операция слияния превращает все активные узлы меньшей кучи в пассивные узлы. Это можно сделать в $O(1)$ время, вводя уровень косвенности. Вместо логического флага каждый активный узел имеет указатель на объект активного флага, содержащий логическое значение. Для пассивных узлов не имеет значения, на какой активный объект-флаг они указывают, пока объект-флаг установлен на пассивный, поскольку не требуется одновременное изменение многих пассивных узлов на активные.

Пересвязывание указателей между узлами и упакованными ключами

Хранение ключей

Операция уменьшения ключа требует ссылки на узел, ключ которого мы хотим уменьшить. Однако сама операция уменьшения ключа иногда меняет местами ключ узла и корень ключа.

Предположим, что операция вставки возвращает некую непрозрачную ссылку, которую мы можем вызвать уменьшением ключа как часть общедоступного API. Если эти ссылки являются внутренними узлами кучи, то, поменяв местами ключи, мы изменили эти ссылки, в результате чего другие ссылки стали неопределенными. Чтобы гарантировать, что ключ всегда будет иметь одну и ту же ссылку, необходимо «упаковать» ключ. Каждый узел кучи теперь содержит указатель на блок, содержащий ключ, а блок также имеет указатель на узел кучи. При вставке элемента мы создаем ящик для хранения ключа, связываем узел кучи с ящиком обоими способами и возвращаем объект ящика. Чтобы поменять ключи между двумя узлами, вместо этого мы повторно связываем указатели между ящиками и узлами.

Операции

Объединить

Позволять $h_{1}$ и $h_{2}$ будьте строгими кучами Фибоначчи. Если один из них пуст, верните другой. В противном случае, пусть $n_{1}$ и $n_{2}$ быть их соответствующими размерами. Не ограничивая общности, предположим, что $n_{1}\leq n_{2}$. Поскольку размеры списка исправлений и списка рангов каждой кучи логарифмические по отношению к размеру кучи, невозможно объединить эти вспомогательные структуры за постоянное время. Вместо этого мы выбрасываем структуру меньшей кучи $h_{1}$ путем отказа от его списка исправлений и списка рангов и преобразования всех его узлов в пассивные узлы. Это можно сделать за постоянное время, используя общий флаг, как показано выше. Связь $h_{1}$ и $h_{2}$, позволяя корню с меньшим ключом стать родителем другого. Позволять $Q_{1}$ и $Q_{2}$ быть очереди $h_{1}$ и $h_{2}$ соответственно. Очередь результирующей кучи установлена ​​на $Q_{\mathrm {merged} }=Q_{1}+\{r_{\mathrm {larger} }\}+Q_{2}$, где $r_{\mathrm {larger} }$ это корень с большим ключом.

Единственным возможным структурным нарушением является степень корня. Это решается путем выполнения 1 активного сокращения корня и 1 уменьшения степени корня, если каждое преобразование возможно.

	Активные корни	Общая потеря	Корневая степень
Состояние после слияния	$0$	$0$	$+1$
$1\times$Активное сокращение корней	$-1$	$0$	$+1$
$1\times$Уменьшение степени корня	$+1$	$0$	$-2$
Общий	$0$	$0$	$0$

Доказательство правильности

Инварианты 1, 2 и 3 выполняются автоматически, поскольку структура кучи отбрасывается. Как вычислено выше, любые нарушения инварианта 4 устраняются преобразованием уменьшения степени корня.

Для проверки инварианта 5 рассмотрим конечные положения узлов в $Q$. Каждый узел имеет свою степень, ограниченную $2\lg(2n-p)+10$ или $2\lg(2n-p)+9$.

Для меньшей кучи $h_{1}$ позиции в $Q_{1}$ неизменны. Однако все узлы в $h_{1}$ теперь пассивны, что означает, что их ограничение может измениться с $+10$ дело в $+9$ случай. Но отметив, что $n_{1}\leq n_{2}$, результирующий размер $n=n_{1}+n_{2}$ как минимум в два раза $n_{1}$. Это приводит к увеличению по крайней мере на 1 для каждого ограничения, что устраняет предыдущую проблему.

Корень с большим ключом между $h_{1}$ и $h_{2}$ становится некорневым и помещается между $Q_{1}$ и $Q_{2}$ на позиции $n_{1}$. По инварианту 4 его степень ограничивалась либо $R_{1}+3=2\lg n_{1}+9$ или $R_{2}+3=2\lg n_{2}+9$, в зависимости от того, из какой кучи он взят. Легко видеть, что это меньше, чем $2\lg {(2n_{1}+2n_{2}-n_{1})}+9$ в любом случае.

Для большей кучи позиции увеличиваются на $n_{1}$. Но поскольку полученный размер $n=n_{1}+n_{2}$, значение $2n-p$ на самом деле увеличивается, ослабляя ограничение.

Вставлять

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

Найти-мин

Благодаря свойству минимальной кучи узел с минимальным ключом всегда находится в корне, если он существует.

Удалить-мин.

Удаление минимальной операции

Если корень — единственный узел в куче, мы закончим, просто удалив его. В противном случае выполните поиск дочерних элементов корня, чтобы найти узел. $x$ с минимальным ключом и установите новый корень на $x$. Если $x$ активен, сделайте его пассивным, в результате чего все активные дочерние элементы $x$ неявно стать активными корнями. Свяжите потомков старого корня с $x$. С $x$ теперь является корнем, переместите всех его пассивных связанных дочерних элементов вправо и удалите $x$ от $Q$.

Степень корня увеличивается примерно вдвое, поскольку мы связали всех детей старого корня с $x$. Мы выполняем следующие восстановительные преобразования:

1. Повторите дважды: поверните $Q$ двигая головой $y$ из $Q$ сзади и соедините двух крайних правых пассивных дочерних элементов $y$ в корень.
2. Если сокращение потерь возможно, выполните его.
3. Выполняйте активное уменьшение корня и уменьшение степени корня до тех пор, пока ни то, ни другое станет невозможным.

Чтобы увидеть, как ограничен шаг 3, рассмотрим состояние после шага 3:

	Активные корни	Общая потеря	Корневая степень
Состояние после удаления-мин	$+R$	$0$	$+R+6$
$2\times$Ротация очереди	$0$	$0$	$+4$
$1\times$Сокращение потерь	$+1$	$-1$	$+1$
Общий	$+R+1$	$-1$	$+R+11$

Обратите внимание, что 3 редукции активного корня и 2 редукции корня уменьшают степень корня и активных корней на 1:

	Активные корни	Общая потеря	Корневая степень
$3\times$Активное сокращение корней	$-3$	$0$	$+3$
$2\times$Уменьшение степени корня	$+2$	$0$	$-4$
Общий	$-1$	$0$	$-1$

С $R=2\lg n+6$, шаг 3 никогда не выполняет более $O(\log n)$ раз.

Доказательство правильности

Инвариант 1 выполняется тривиально, поскольку активные корни не создаются.

Размер кучи $n$ уменьшается на единицу, что приводит к $R=2\lg n+6$ уменьшается не более чем на единицу. Таким образом, инвариант 3 нарушается не более чем 1. По лемме 3 возможно уменьшение потерь, что и было сделано на шаге 2.

Инварианты 1 и 3 теперь справедливы. Если бы инварианты 2 и 4 все еще нарушались после шага 3, можно было бы применить активную редукцию корня и редукцию степени корня по леммам 2 и 4. Однако активная редукция корня и редукция степени корня уже полностью применены. Следовательно, инварианты 2 и 4 также имеют место.

Чтобы показать, что инвариант 5 выполняется, сначала заметим, что размер кучи $n$ уменьшилось на 1. Поскольку первые 2 узла в $Q$ выталкиваются на шаге 1, позиции других элементов в $Q$ уменьшится на 2. Следовательно, ограничения на степень $2\lg(2n-p)+10$ и $2\lg(2n-p)+9$ остаются постоянными для этих узлов. Два узла, которые были извлечены ранее, имели позиции 1 и 2 в $Q$, и теперь у нас есть позиции $n-2$ и $n-1$ соответственно. В результате их ограничения степени усилились на 2, однако мы отсекаем двух пассивных потомков для каждого из этих узлов, что достаточно для повторного удовлетворения ограничения.

Клавиша уменьшения

Клавиша уменьшения

Позволять $x$ быть узлом, ключ которого был уменьшен. Если $x$ это корень, мы закончили. В противном случае отсоедините поддерево с корнем в $x$и свяжите его с корнем. Если ключ $x$ меньше ключа корня, поменяйте их ключами.

Могло произойти до трех структурных нарушений. Пока не $x$ уже был дочерним элементом корня, степень корня увеличивается на 1. Когда $x$ был отделен от своего первоначального родителя $y$, мы имеем следующие случаи:

• Если $x$ пассивен, то лишних нарушений нет.
• Если $x$ ранее был активным корнем с $y$ пассивный, затем движущийся $x$ от того, что я ребенок $y$ дочернему элементу корня не создает никаких дополнительных активных корней и не увеличивает потерю какого-либо узла.
• Если оба $x$ и $y$ активны, то потеря $y$ увеличивается на 1, и создается дополнительный активный корень (путем связывания $x$ до корня).

В худшем случае все три величины (степень корня, общие потери, активные корни) увеличиваются на 1.

После выполнения 1 уменьшения потерь наихудший результат по-прежнему заключается в том, что степень корня и количество активных корней увеличились на 2. Чтобы исправить эти нарушения, мы используем тот факт, что 3 сокращения активных корней и 2 сокращения корней уменьшают обе эти величины. на 1. Следовательно, применения этих преобразований 6 и 4 раза соответственно достаточно, чтобы устранить все нарушения.

	Активные корни	Общая потеря	Корневая степень
Состояние после клавиши уменьшения	$+1$	$+1$	$+1$
$1\times$Сокращение потерь	$+1$	$-1$	$+1$
$6\times$Активное сокращение корней	$-6$	$0$	$+6$
$4\times$Уменьшение степени корня	$+4$	$0$	$-8$
Общий	$0$	$0$	$0$

Доказательство правильности

Узлы, которые ранее были левыми братьями и сестрами $x$ двигаться, чтобы заполнить пробел, оставленный $x$, уменьшая их индекс. Поскольку их ограничение ослабло, инвариант 1 не затрагивается. Инвариант 5 тривиально выполняется как $Q$ неизменен.

Леммы 2, 3 и 4 гарантируют наличие активной корневой редукции, редукции потерь и редукции степени корня. Следовательно, справедливы инварианты 2, 3 и 4.

Производительность

Хотя строгие кучи Фибоначчи теоретически оптимальны, они бесполезны в практических приложениях. Их чрезвычайно сложно реализовать, требуя управления более чем 10 указателями на узел. Хотя большинство операций выполняются в $O(1)$ время постоянные факторы могут быть очень высокими, что делает их до 20 раз медленнее, чем их более распространенные аналоги, такие как двоичные кучи или парные кучи . Несмотря на то, что строгая куча Фибоначчи относительно проще, эксперименты показывают, что на практике она работает медленнее, чем очередь Бродала.

Сводка времени работы

Вот временные сложности различных структур данных кучи. Аббревиатура ам. указывает, что данная сложность амортизируется, в противном случае это сложность наихудшего случая. Значение « O ( f )» и « Θ ( f )» см в обозначении Big O. . Имена операций предполагают минимальную кучу.

Операция	найти-мин	удаление-мин	клавиша уменьшения	вставлять	сливаться	помойка
Двоичный	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )	Θ ( н )
Перекос	я (1)	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	О (log n ) утра.	Θ ( н ) утра.
Левый	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ (логарифм n )	Θ ( н )
Биномиальный	я (1)	Θ (логарифм n )	Θ (логарифм n )	Θ (1) утра.	Θ (логарифм n )	Θ ( н )
Наклонный бином	я (1)	Θ (логарифм n )	Θ (логарифм n )	я (1)	Θ (логарифм n )	Θ ( н )
2–3 кучи	я (1)	О (log n ) утра.	я (1)	Θ (1) утра.	О (логарифм n )	Θ ( н )
Перекос снизу вверх	я (1)	О (log n ) утра.	О (log n ) утра.	Θ (1) утра.	Θ (1) утра.	Θ ( н ) утра.
Сопряжение	я (1)	О (log n ) утра.	о (log n ) утра.	я (1)	я (1)	Θ ( н )
Сопряжение по рангам	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Фибоначчи	я (1)	О (log n ) утра.	Θ (1) утра.	я (1)	я (1)	Θ ( н )
Строгий Фибоначчи	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н )
Мостовая долина	я (1)	Θ (логарифм n )	я (1)	я (1)	я (1)	Θ ( н )

Внешние ссылки

• JavaScript-моделирование строгой кучи Фибоначчи