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

In computer science, a heap is a specialized treebased 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 maxheap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a minheap.) 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:
 findmax or findmin: find the maximum item of a maxheap or a minimum item of a minheap, respectively
 deletemax or deletemin: removing the root node of a max or minheap, respectively
 increasekey or decreasekey: updating a key within a max or minheap, 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 minheap.
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 
SharpPcomplete 
Algebraic extension 
Concatenation 
Byteorder mark 
Residue (complex analysis) 
Abstract factory pattern 
Subtraction 
Unique factorization domain 
