Русская Википедия:Сливаемая куча
Материал из Онлайн справочника
Шаблон:Значения Сливаемая куча (Шаблон:Lang-en) — структура данных, которая поддерживает следующие пять операций:
- Создание пустой кучи <math>H</math> (Шаблон:Lang-en);
- Вставка узла <math>x</math> в кучу <math>H</math> (Шаблон:Lang-en);
- Поиск узла в куче <math>H</math>, который обладает минимальным ключом (Шаблон:Lang-en);
- Удаление узла с минимальным ключом из кучи <math>H</math> (Шаблон:Lang-en);
- Создание новой кучи <math>H</math>, которая содержит все узлы куч <math>H_1</math> и <math>H_2</math> (Шаблон:Lang-en).
Реализации
Следующие две структуры данных являются реализациями сливаемой кучи:
Эти структуры данных так же поддерживают еще 2 операции:
- Присваивание узлу <math>x</math> в куче <math>H</math> нового значения ключа (Шаблон:Lang-en) (предполагается, что новое значение ключа не превосходит текущего);
- Удаление узла <math>x</math> из кучи <math>H</math> (Шаблон: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), которые поддерживают следующие операции:
- Создание пустой кучи <math>H</math> (Шаблон:Lang-en);
- Вставка узла <math>x</math> в кучу <math>H</math> (Шаблон:Lang-en);
- Поиск узла в куче <math>H</math>, который обладает максимальныи ключом (Шаблон:Lang-en);
- Удаление узла с максимальныи ключом из кучи <math>H</math> (Шаблон:Lang-en);
- Создание новой кучи <math>H</math>, которая содержит все узлы куч <math>H_1</math> и <math>H_2</math> (Шаблон:Lang-en).
- Присваивание узлу <math>x</math> в куче <math>H</math> нового значения ключа (Шаблон:Lang-en);
- Удаление узла <math>x</math> из кучи <math>H</math> (Шаблон:Lang-en).
Литература