Patarakin: 1 версия импортирована

2022-10-19T07:30:42Z

1 версия импортирована

← Предыдущая версия		Версия от 10:30, 19 октября 2022
(нет различий)

ru_wikipedia>НСНУ: Дoбaвлeнa Категория:Кучи (структуры данных) с помощью HotCat

2018-01-15T16:13:18Z

Дoбaвлeнa Категория:Кучи (структуры данных) с помощью HotCat

Новая страница

{{значения|Куча}}
'''Сливаемая куча''' ({{lang-en|Mergeable heap}}) — [[структура данных]], которая поддерживает следующие пять операций:
* Создание пустой кучи <math>H</math> ({{lang-en|Make heap}});
* Вставка узла <math>x</math> в кучу <math>H</math> ({{lang-en|Insert}});
* Поиск узла в куче <math>H</math>, который обладает минимальным ключом ({{lang-en|Minimum}});
* Удаление узла с минимальным ключом из кучи <math>H</math> ({{lang-en|Extract minimum}});
* Создание новой кучи <math>H</math>, которая содержит все узлы куч <math>H_1</math> и <math>H_2</math> ({{lang-en|Union}}).

== Реализации ==
Следующие две [[структура данных|структуры данных]] являются реализациями сливаемой кучи:
* [[Биномиальная куча]];
* [[Фибоначчиева куча]].

Эти [[структура данных|структуры данных]] так же поддерживают еще 2 операции:
* Присваивание узлу <math>x</math> в куче <math>H</math> нового значения ключа ({{lang-en|Decrease key}}) (предполагается, что новое значение ключа не превосходит текущего);
* Удаление узла <math>x</math> из кучи <math>H</math> ({{lang-en|Delete}}).

{| class="standard"
|+ Время выполнения операций у разных реализаций сливаемых пирамид
! Операция
! [[Биномиальная куча]]
! [[Фибоначчиева куча]]
|-
| Make heap
| align="center" | Θ(1)
| align="center" | Θ(1)
|-
| Insert
| align="center" | ''O''(lg''n'')
| align="center" | Θ(1)
|-
| Minimum
| align="center" | ''O''(lg''n'')
| align="center" | Θ(1)
|-
| Extract minimum
| align="center" | Θ(lg''n'')
| align="center" | ''O''(lg''n'')
|-
| Union
| align="center" | Ω(lg''n'')
| align="center" | Θ(1)
|-
| Decrease key
| align="center" | Θ(lg''n'')
| align="center" | Θ(1)
|-
| Delete
| align="center" | Θ(lg''n'')
| align="center" | ''O''(lg''n'')
|}

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

'''Замечание.''' По умолчанию сливаемые кучи являются неубывающими сливаемыми кучами ({{lang-en|Mergeable min-heap}}). Также существуют невозрастающие сливаемые кучи ({{lang-en|Mergeable max-heap}}), которые поддерживают следующие операции:
* Создание пустой кучи <math>H</math> ({{lang-en|Make heap}});
* Вставка узла <math>x</math> в кучу <math>H</math> ({{lang-en|Insert}});
* Поиск узла в куче <math>H</math>, который обладает максимальныи ключом ({{lang-en|Maximum}});
* Удаление узла с максимальныи ключом из кучи <math>H</math> ({{lang-en|Extract maximum}});
* Создание новой кучи <math>H</math>, которая содержит все узлы куч <math>H_1</math> и <math>H_2</math> ({{lang-en|Union}}).
* Присваивание узлу <math>x</math> в куче <math>H</math> нового значения ключа ({{lang-en|Increase key}});
* Удаление узла <math>x</math> из кучи <math>H</math> ({{lang-en|Delete}}).

== Литература ==
* {{книга
|автор = Томас Х. Кормен и др.
|заглавие = Алгоритмы: построение и анализ
|оригинал =
|ссылка =
|издание = 2-е изд
|место = М.
|издательство = [[Вильямс (издательство)|Издательский дом «Вильямс»]]
|год = 2007
|страницы = 1296
|isbn = 5-8459-0857-4
}}

[[Категория:Структуры данных]]
[[Категория:Кучи (структуры данных)]]

Сливаемая куча - История изменений

Patarakin: 1 версия импортирована

ru_wikipedia>НСНУ: Дoбaвлeнa Категория:Кучи (структуры данных) с помощью HotCat