Heap (data structure)

related topics
{math, number, function}
{woman, child, man}
{style, bgcolor, rowspan}

In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) The several variants of heaps are the prototypical most efficient implementations of the abstract data type priority queues. Priority queues are useful in many applications. In particular, heaps are crucial in several efficient graph algorithms.

Heaps are usually implemented in an array, and do not require pointers between elements.

The operations commonly performed with a heap are:

  • find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively
  • delete-max or delete-min: removing the root node of a max- or min-heap, respectively
  • increase-key or decrease-key: updating a key within a max- or min-heap, respectively
  • insert: adding a new key to the heap
  • merge: joining two heaps to form a valid new heap containing all the elements of both.

Heaps are used in the sorting algorithm heapsort.

Contents

Variants

Comparison of theoretic bounds for variants

The following time complexities[1] are amortized time complexity for entries marked by an asterisk, and worst case time complexities for all other entries. O(f) gives asymptotic upper bound and Θ(f) is asymptotically tight bound (see Big O notation). Function names assume a min-heap.

Full article ▸

related documents
Bijection
Alexandroff extension
Fibonacci coding
Pseudometric space
Waring's problem
Degenerate distribution
Domain (mathematics)
Zeta distribution
Bernoulli process
Geometric mean
Iteration
Closed set
Binary operation
Currying
Static code analysis
General number field sieve
Alternating group
Quadratic programming
Graph of a function
Hamming distance
Differential cryptanalysis
Extractor
Sharp-P-complete
Algebraic extension
Concatenation
Byte-order mark
Residue (complex analysis)
Abstract factory pattern
Subtraction
Unique factorization domain