Сливаемая куча

У этого термина существуют и другие значения, см. Куча.

Сливаемая куча (англ. Mergeable heap) — структура данных, которая поддерживает следующие пять операций:

• Создание пустой кучи ${\displaystyle H}$ (англ. Make heap);
• Вставка узла ${\displaystyle x}$ в кучу ${\displaystyle H}$ (англ. Insert);
• Поиск узла в куче ${\displaystyle H}$, который обладает минимальным ключом (англ. Minimum);
• Удаление узла с минимальным ключом из кучи ${\displaystyle H}$ (англ. Extract minimum);
• Создание новой кучи ${\displaystyle H}$, которая содержит все узлы куч ${\displaystyle H_{1}}$ и ${\displaystyle H_{2}}$ (англ. Union).

Реализации

Следующие две структуры данных являются реализациями сливаемой кучи:

• Биномиальная куча;
• Фибоначчиева куча.

Эти структуры данных так же поддерживают еще 2 операции:

• Присваивание узлу ${\displaystyle x}$ в куче ${\displaystyle H}$ нового значения ключа (англ. Decrease key) (предполагается, что новое значение ключа не превосходит текущего);
• Удаление узла ${\displaystyle x}$ из кучи ${\displaystyle H}$ (англ. Delete).

Время выполнения операций у разных реализаций сливаемых пирамид

Операция	Биномиальная куча	Фибоначчиева куча
Make heap	Θ(1)	Θ(1)
Insert	O(lgn)	Θ(1)
Minimum	O(lgn)	Θ(1)
Extract minimum	Θ(lgn)	O(lgn)
Union	Ω(lgn)	Θ(1)
Decrease key	Θ(lgn)	Θ(1)
Delete	Θ(lgn)	O(lgn)

Примечание: для Биномиальной кучи время в наихудшем случае, для Фибоначчиевой кучи амортизированное время.

Замечание. По умолчанию сливаемые кучи являются неубывающими сливаемыми кучами (англ. Mergeable min-heap). Также существуют невозрастающие сливаемые кучи (англ. Mergeable max-heap), которые поддерживают следующие операции:

• Создание пустой кучи ${\displaystyle H}$ (англ. Make heap);
• Вставка узла ${\displaystyle x}$ в кучу ${\displaystyle H}$ (англ. Insert);
• Поиск узла в куче ${\displaystyle H}$, который обладает максимальныи ключом (англ. Maximum);
• Удаление узла с максимальныи ключом из кучи ${\displaystyle H}$ (англ. Extract maximum);
• Создание новой кучи ${\displaystyle H}$, которая содержит все узлы куч ${\displaystyle H_{1}}$ и ${\displaystyle H_{2}}$ (англ. Union).
• Присваивание узлу ${\displaystyle x}$ в куче ${\displaystyle H}$ нового значения ключа (англ. Increase key);
• Удаление узла ${\displaystyle x}$ из кучи ${\displaystyle H}$ (англ. Delete).

Литература

• Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.