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