TOPICS
Search

Heap


A sequence {a_n}_(n=1)^N forms a (binary) heap if it satisfies a_(|_j/2_|)<=a_j for 2<=j<=N, where |_x_| is the floor function, which is equivalent to a_i<a_(2i) and a_i<a_(2i+1) for 1<=i<=(N-1)/2. The first member must therefore be the smallest. A heap can be viewed as a labeled binary tree in which the label of the ith node is smaller than the labels of any of its descendents (Skiena 1990, p. 35). Heaps support arbitrary insertion and seeking/deletion of the minimum value in O(lnn) times per update (Skiena 1990, p. 38).

Heaps

A list can be converted to a heap in O(n) times using an algorithm due to Floyd (1964). For example, given the random permutation {6,2,7,9,5,3,4,8,10,1}, Floyd's algorithm gives the heap {1,2,3,8,5,7,4,9,10,6} (left figure). The right figure shows a heap containing 30 elements.

nheaps
1{1}
2{1, 2}
3{1, 2, 3}, {1, 3, 2}
4{1, 2, 3, 4}, {1, 2, 4, 3}, {1, 3, 2, 4}

The numbers of heaps a(n) on n=1, 2, ... elements are 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, ... (OEIS A056971), the first few of which are summarized in the above table. A formula for a(n) is given by

 a(n)=(n-1; b+r_1)a(b+r_1)a(b+r_2)
(1)

with a(0)=0, a(1)=1, and

h=|_log_2(n+1)_|-1
(2)
b=2^h-1
(3)
r=n-1-2b
(4)
r_1=r-|_r/(2^h)_|(r-2^h)
(5)
r_2=r-r_1.
(6)

The number of heaps of l levels (or equivalently, the number of heaps of 2^l-1 elements) is given by the recurrence relation

 S_l=(2^l-2; 2^(l-1)-1)S_(l-1)^2
(7)

with S_1=1 (Skiena 1990, p. 36). This can be written as a product as

 S_l=((2^l-1)!)/(product_(k=1)^(n)(2^k-1)^(2^(n-k))),
(8)

the values of which for l=1, 2, ... are 1, 2, 80, 21964800, 74836825861835980800000, ... (OEIS A056972).


See also

Binary Tree, Complete Binary Tree, Heapsort, Priority Queue

Explore with Wolfram|Alpha

References

Floyd, R. W. "Algorithm 245: Treesort 3." Comm. ACM 7, 701, 1964.Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed. Reading, MA: Addison-Wesley, 1998.Skiena, S. "Heaps." §1.4.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 35-39, 1990.Skiena, S. S. "Heaps." §1.4.4 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 35-39, 1997.Sloane, N. J. A. Sequences A056971 and A056972 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Heap

Cite this as:

Weisstein, Eric W. "Heap." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Heap.html

Subject classifications