In computer science, an addressable heap is an abstract data type. Specifically, it is a mergeable heap supporting access to the elements of the heap via handles (also called references). It allows the key of the element referenced by a particular handle to be removed or decreased.
Definition
An addressable heap supports the following operations:
- <code>Make-Heap()</code>, creating an empty heap.
- <code>Insert(H,x)</code>, inserting an element <code>x</code> into the heap <code>H</code>, and returning a handle to it.
- <code>Min(H)</code>, returning a handle to the minimum element, or <code>Nil</code> if no such element exists.
- <code>Extract-Min(H)</code>, extracting and returning a handle to the minimum element, or <code>Nil</code> if no such element exists.
- <code>Remove(h)</code>, removing the element referenced by <code>h</code> (from its respective heap).
- <code>Decrease-Key(h,k)</code>, decreasing the key of the element referenced by <code>h</code> to <code>k</code>; illegal if <code>k</code> is larger than the key referenced by <code>h</code>.
- <code>Merge(H1,H2)</code>, combining the elements of <code>H1</code> and <code>H2</code>.
Examples
Examples of addressable heaps include:
A more complete list with performance comparisons can be found here.
References