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

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

Определение

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

  • Make-Heap (), создайте пустую кучу.
  • Вставить (H, x), вставить элемент Икс в кучу ЧАС.
  • Мин (H), вернуть минимальный элемент, или Ноль если такого элемента нет.
  • Экстракт мин (H), извлечь и вернуть минимальный элемент, или Ноль если такого элемента нет.

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

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

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

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

Слияние (H1, H2):

  1. x ← Экстракт мин. (H2)
  2. пока x ≠ ноль
    1. Вставить (H1, x)
    2. x ← Мин. извлечения (H2)

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

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

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

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

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

Смотрите также

Рекомендации

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