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

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

Определение

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

Make-Heap(), создавая пустую кучу.
Insert(H,x), вставка элемента x в кучу Hи возвращаем к нему дескриптор.
Min(H), возвращая дескриптор минимального элемента, или Nil если такого элемента не существует.
Extract-Min(H), извлекая и возвращая дескриптор минимального элемента, или Nil если такого элемента не существует.
Remove(h), удаляя элемент, на который ссылается h (из соответствующей кучи).
Decrease-Key(h,k), уменьшая ключ элемента, на который ссылается h к k; незаконно, если k больше, чем ключ, на который ссылается h.
Merge(H1,H2), объединяя элементы H1 и H2.

Примеры

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

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

Ссылки

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

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

[ 1 ]