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.

Please note You will be presented with a research related survey when you submit the exercise.

Algorithm 1 Build-Min-Heap(A)


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


Algorithm 2 Min-Heapify(A, i)


lLeft-child-index(i)
rRight-child-index(i)
if lheap-size[A] and A[l] < A[i] then
smallestl
else
smallesti
end if
if rheap-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:42 EEST 2007 - Powered by SVG-hut