Addressable heap

In computer science, an Addressable heap is an abstract data type, which is a mergeable heap supporting access to the elements of the heap via handles (also called references), and allows to remove, or decrease the key of the element referenced by the handle.

Definition

An addressable heap supports the following operations^[1]:

Make-Heap(), creating an empty heap.
Insert(H,x), inserting an element x into the heap H, and returning a handle to it.
Min(H), returning a handle to the minimum element, or Nil if no such element exists.
Extract-Min(H), extracting and returning a handle to the minimum element, or Nil if no such element exists.
Remove(h), removing the element referenced by h (from its respective heap).
Decrease-Key(h,k), decreasing the key of the element referenced by h to k; illegal if k is larger than the key referenced by h.


Merge(H1,H2), combining the elements of H1 and H2.

Examples

Examples of addressable heaps include:

Fibonacci heaps
Binomial heaps

A more complete list with performance comparisons can be found here.

References



^ Kurt Mehlborn and Peter Sanders. Algorithms and Data Structures -- The Basic Toolbox.  2008. Springer-Verlag. Berlin, Heidelberg, Germany. ISBN: 978-3-540-77977-3.

[1] Kurt Mehlborn and Peter Sanders. Algorithms and Data Structures -- The Basic Toolbox. 2008. Springer-Verlag. Berlin, Heidelberg, Germany. ISBN: 978-3-540-77977-3.

[1]