Объединяемая куча

В информатике ( объединяемая куча также называемая объединяемой кучей ) — это абстрактный тип данных , который представляет собой кучу, поддерживающую операцию слияния.

Определение

Объединяемая куча поддерживает обычные операции с кучей: ^[1]

Make-Heap(), создайте пустую кучу.
Insert(H,x), вставьте элемент x в кучу H.
Min(H), верните минимальный элемент или Nil если такого элемента не существует.
Extract-Min(H), извлеките и верните минимальный элемент или Nil если такого элемента не существует.

И еще одно, что его отличает: ^[1]

Merge(H1,H2), объединить элементы H1 и H2 в одну кучу.

Тривиальная реализация

Реализовать объединяемую кучу при наличии простой кучи несложно:

Merge(H1,H2):

x ← Extract-Min(H2)
while x ≠ Nil
1. Insert(H1, x)
2. x ← Extract-Min(H2)

Однако это может быть расточительно, поскольку каждый Extract-Min(H) и Insert(H,x) обычно приходится поддерживать свойство кучи .

Более эффективные реализации

Примеры объединяемых структур данных кучи включают в себя:

Более полный список со сравнением производительности можно найти в Heap (структура данных) § Сравнение теоретических границ вариантов .

В большинстве объединяемых структур кучи слияние является фундаментальной операцией, на которой основаны другие. Вставка реализуется путем объединения новой одноэлементной кучи с существующей кучей. Удаление реализуется путем слияния дочерних элементов удаляемого узла.

См. также

Адресуемая куча

Ссылки

^ Jump up to: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 505–506. ISBN 0-262-03384-4 .

[CLR-1] Jump up to: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2009) [1990]. Введение в алгоритмы (3-е изд.). MIT Press и McGraw-Hill. стр. 505–506. ISBN 0-262-03384-4 .

[1]