Сливаемая куча
Сливаемая куча (англ. Mergeable heap) — структура данных, которая поддерживает следующие пять операций:
Реализации
Следующие две структуры данных являются реализациями сливаемой кучи:
Эти структуры данных так же поддерживают еще 2 операции:
- Присваивание узлу в куче нового значения ключа (англ. Decrease key) (предполагается, что новое значение ключа не превосходит текущего);
- Удаление узла из кучи (англ. 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), которые поддерживают следующие операции:
- Создание пустой кучи (англ. Make heap);
- Вставка узла в кучу (англ. Insert);
- Поиск узла в куче , который обладает максимальныи ключом (англ. Maximum);
- Удаление узла с максимальныи ключом из кучи (англ. Extract maximum);
- Создание новой кучи , которая содержит все узлы куч и (англ. Union).
- Присваивание узлу в куче нового значения ключа (англ. Increase key);
- Удаление узла из кучи (англ. Delete).
Литература
- Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.