In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includin ...
, an addressable heap is an
abstract data type
In computer science, an abstract data type (ADT) is a mathematical model for data types. An abstract data type is defined by its behavior (semantics) from the point of view of a '' user'', of the data, specifically in terms of possible values, po ...
. Specifically, it is a
mergeable heap supporting access to the elements of the heap via handles (also called
references
Reference is a relationship between objects in which one object designates, or acts as a means by which to connect to or link to, another object. The first object in this relation is said to ''refer to'' the second object. It is called a '' name'' ...
). 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:
*
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 heap
In computer science, a Fibonacci heap is a data structure for priority queue operations, consisting of a collection of heap-ordered trees. It has a better amortized running time than many other priority queue data structures including the bina ...
s
*
Binomial heap
In computer science, a binomial heap is a data structure that acts as a priority queue but also allows pairs of heaps to be merged.
It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which ...
s
A more complete list with performance comparisons can be found
here
Here is an adverb that means "in, on, or at this place". It may also refer to:
Software
* Here Technologies, a mapping company
* Here WeGo (formerly Here Maps), a mobile app and map website by Here
Television
* Here TV (formerly "here!"), a ...
.
References
{{reflist
Heaps (data structures)