Build heap

Hide text Hide pseudo-code

A heap can be built from a table of random keys by using a linear time bottom-up algorithm (a.k.a., Build-Heap, Fixheap, and Bottom-Up Heap Construction). This algorithm ensures that the heap-order property (the key at each node is lower than or equal to the keys at its children) is not violated in any node.

Some additional problems.

Algorithm 1 Build-Min-Heap(A)


for iheap-size[A]/2 - 1 downto 0 do
Min-Heapify (A, i)
end for


Algorithm 2 Min-Heapify(A, i)


lLeft-child-index(i)
rRight-child-index(i)
if l < heap-size[A] and A[l] < A[i] then
smallestl
else
smallesti
end if
if r < heap-size[A] and A[r] < A[smallest] then
smallestr
end if
if smallest ≠ i then
Swap(A[i],A[smallest])
Min-Heapify(A, smallest)
end if


  Created Wed Jun 20 16:00:44 EEST 2007 - Powered by SVG-hut