Language: EN FI

Exercises > Build heap

These exercises demonstrate the content of the ByTheMark service. These are meant for private individuals for learning data structures and algorithms. If you want to try out more content, you can register to the ByTheMark Personal free of charge.

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.

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

  Last modified Tue Mar 01 20:54:04 EET 2011