TRAKLA2 - Build heap

Build heap

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions 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. In this exercise, the heap is visualized both as a binary tree and vector. Both visualizations illustrate the same data structure and the exercise can be completed by swapping keys in either visualization. The swapping is done by drag & dropping a key into another node.
Build-Heap Algorithm 1 Build-Min-Heap(A) for i ← heap-size[A]/2 - 1 downto 0 do Min-Heapify (A, i) end for Algorithm 2 Min-Heapify(A, i) l ← Left-child-index(i) r ← Right-child-index(i) if l < heap-size[A] and A[l] < A[i] then smallest ← l else smallest ← i end if if r < heap-size[A] and A[r] < A[smallest] then smallest ← r end if if smallest ≠ i then Swap(A[i],A[smallest]) Min-Heapify(A, smallest) end if