Адресуемая куча - Addressable heap

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

Определение

Адресуемая куча поддерживает следующие операции:^[1]

• Make-Heap (), создав пустую кучу.
• Вставить (H, x), вставка элемента Икс в кучу ЧАС, и вернув ему дескриптор.
• Мин (H), возвращая дескриптор минимального элемента, или Ноль если такого элемента нет.
• Экстракт мин (H), извлекая и возвращая дескриптор минимального элемента, или Ноль если такого элемента нет.
• Удалить (h), удаляя элемент, на который ссылается час (из соответствующей кучи).
• Клавиша уменьшения (h, k), уменьшая ключ элемента, на который ссылается час к k; незаконно, если k больше ключа, на который ссылается час.
• Слияние (H1, H2), объединяя элементы H1 и H2.

Примеры

Примеры адресуемых куч:

• Куча Фибоначчи
• Биномиальные кучи

Более полный список со сравнениями производительности можно найти здесь.

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

1. Мельхорн, Курт; Сандерс, Питер (2008). Алгоритмы и структуры данных: базовый набор инструментов (PDF). Springer. ISBN  978-3-540-77977-3.