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

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

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

РеализацииПравить

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

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

Присваивание узлу $\text{[math]}$ $\text{[math]}$ $x$ в куче $\text{[math]}$ $\text{[math]}$ $H$ нового значения ключа (англ. Decrease key) (предполагается, что новое значение ключа не превосходит текущего);
Удаление узла $\text{[math]}$ $\text{[math]}$ $x$ из кучи $\text{[math]}$ $\text{[math]}$ $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), которые поддерживают следующие операции:

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

ЛитератураПравить

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