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

Шаблон:Значения Сливаемая куча (Шаблон:Lang-en) — структура данных, которая поддерживает следующие пять операций:

• Создание пустой кучи $H$ (Шаблон:Lang-en);
• Вставка узла $x$ в кучу $H$ (Шаблон:Lang-en);
• Поиск узла в куче $H$, который обладает минимальным ключом (Шаблон:Lang-en);
• Удаление узла с минимальным ключом из кучи $H$ (Шаблон:Lang-en);
• Создание новой кучи $H$, которая содержит все узлы куч $H_1$ и $H_2$ (Шаблон:Lang-en).

Реализации

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

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

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

• Присваивание узлу $x$ в куче $H$ нового значения ключа (Шаблон:Lang-en) (предполагается, что новое значение ключа не превосходит текущего);
• Удаление узла $x$ из кучи $H$ (Шаблон:Lang-en).

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

Операция	Биномиальная куча	Фибоначчиева куча
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)

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

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

• Создание пустой кучи $H$ (Шаблон:Lang-en);
• Вставка узла $x$ в кучу $H$ (Шаблон:Lang-en);
• Поиск узла в куче $H$, который обладает максимальныи ключом (Шаблон:Lang-en);
• Удаление узла с максимальныи ключом из кучи $H$ (Шаблон:Lang-en);
• Создание новой кучи $H$, которая содержит все узлы куч $H_1$ и $H_2$ (Шаблон:Lang-en).
• Присваивание узлу $x$ в куче $H$ нового значения ключа (Шаблон:Lang-en);
• Удаление узла $x$ из кучи $H$ (Шаблон:Lang-en).

Литература

• Шаблон:Книга