Сливаемая куча
Шаблон:Значения Сливаемая куча (Шаблон:Lang-en) — структура данных, которая поддерживает следующие пять операций:
- Создание пустой кучи [math]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Вставка узла [math]\displaystyle{ x }[/math] в кучу [math]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Поиск узла в куче [math]\displaystyle{ H }[/math], который обладает минимальным ключом (Шаблон:Lang-en);
- Удаление узла с минимальным ключом из кучи [math]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Создание новой кучи [math]\displaystyle{ H }[/math], которая содержит все узлы куч [math]\displaystyle{ H_1 }[/math] и [math]\displaystyle{ H_2 }[/math] (Шаблон:Lang-en).
Реализации
Следующие две структуры данных являются реализациями сливаемой кучи:
Эти структуры данных так же поддерживают еще 2 операции:
- Присваивание узлу [math]\displaystyle{ x }[/math] в куче [math]\displaystyle{ H }[/math] нового значения ключа (Шаблон:Lang-en) (предполагается, что новое значение ключа не превосходит текущего);
- Удаление узла [math]\displaystyle{ x }[/math] из кучи [math]\displaystyle{ 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]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Вставка узла [math]\displaystyle{ x }[/math] в кучу [math]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Поиск узла в куче [math]\displaystyle{ H }[/math], который обладает максимальныи ключом (Шаблон:Lang-en);
- Удаление узла с максимальныи ключом из кучи [math]\displaystyle{ H }[/math] (Шаблон:Lang-en);
- Создание новой кучи [math]\displaystyle{ H }[/math], которая содержит все узлы куч [math]\displaystyle{ H_1 }[/math] и [math]\displaystyle{ H_2 }[/math] (Шаблон:Lang-en).
- Присваивание узлу [math]\displaystyle{ x }[/math] в куче [math]\displaystyle{ H }[/math] нового значения ключа (Шаблон:Lang-en);
- Удаление узла [math]\displaystyle{ x }[/math] из кучи [math]\displaystyle{ H }[/math] (Шаблон:Lang-en).
Литература
- {{#if:Томас Х. Кормен и др.|Томас Х. Кормен и др. }}{{#if: |{{#if: |[{{{ссылка часть}}} {{{часть}}}]| {{{часть}}}}} // }}{{#if:|[[:s:{{{викитека}}}|Алгоритмы: построение и анализ]]|{{#if:|[ Алгоритмы: построение и анализ]|Алгоритмы: построение и анализ}}}}{{#if:| = }}{{#if:| / {{{ответственный}}}.|{{#if:||.}}}}{{#if:Алгоритмы: построение и анализ|{{#if:| {{#if:| = {{{оригинал2}}} }}{{#if:| / {{{ответственный2}}}.|{{#if:||.}}}}}}}}{{#if:2-е изд| — 2-е изд.}}{{#switch:{{#if:М.|м}}{{#if:Издательский дом «Вильямс»|и}}{{#if:2007|г}}
|миг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Издательский дом «Вильямс», 2007.
|ми= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}: Издательский дом «Вильямс».
|мг= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М.}} }}, 2007.
|иг= — Издательский дом «Вильямс», 2007.
|м= — {{#if:М.|{{#switch:М.|L.|N. Y.|P.|Б.|Б. м.|Ер.|Иер.|К.|Каз.|Л.|М.|Мн.|Н. Н.|Н. Новгород|Пг.|Ростов н/Д|СПб.|Тб.|Тф.|Яр.=Шаблон:М.|М..}} }}
|и= — Издательский дом «Вильямс».
|г= — 2007.
}}{{#if:| — {{{том как есть}}}.}}{{#if:| — Т. {{{том}}}.}}{{#if:| — Vol. {{{volume}}}.}}{{#if:| — B. {{{band}}}.}}{{#if:| — {{{страницы как есть}}}.}}{{#if:1296| — С. 1296.}}{{#if:| — {{{страниц как есть}}}.}}{{#if:| — {{{страниц}}} с.}}{{#if:| — P. {{{pages}}}.}}{{#if:| — S. {{{seite}}}.}}{{#if:| — p.}}{{#if:| — s.}}{{#if:| — ({{{серия}}}).}}{{#if:| — Шаблон:Nobr}}{{#if:5-8459-0857-4| — ISBN 5-8459-0857-4}}
