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. Please note You will be presented with a research related survey when you submit the exercise. 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. Some additional problems.
Build-Heap Algorithm 1 Build-Min-Heap(A) for i ← heap-size[A]/2 downto 1 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