Addressable heap

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:[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:

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

References
  1. Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox (PDF). Springer. ISBN 978-3-540-77977-3.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.