WikiSort.ru - Программирование

Сливаемая куча (англ. 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).

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

Замечание. По умолчанию сливаемые кучи являются неубывающими сливаемыми кучами (англ. 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.