TRAKLA2 - Heapsort

Heapsort

Hide text Show text Hide pseudo-code Show pseudo-code
Task Instructions The HeapSort algorithm has been executed until line 2. In the figure, you can see the input array (both as an array and a binary tree representations). Continue the execution from line 2. You can swap keys by drag and dropping them on each other in either of the representations (array or binary tree). Begin by swapping the last key with the largest key, and reducing the size of the heap by one (by clicking the "Reduce heap size" button). After that, perform all the required operations necessary with the MaxHeapify algorithm in order to restore the heap property again.
HeapSort MaxHeapify HeapSort(array heap) 1. BuildHeap(heap) 2. while heap.getSize() > 1 do 3. heap.swap(0, heap.getSize()-1); 4. heap.setSize(heap.getSize()-1); 5. MaxHeapify(heap, 0) MaxHeapify(array heap, int i) 1. l = getLeftChildIndex(i) 2. r = getRightChildIndex(i) 3. largest = i 4. if l < heap.getSize() and heap[l] > heap[largest] then 5. largest = l 6. if r < heap.getSize() and heap[r] > heap[largest] then 7. largest = r 8. if largest != i then 9. heap.swap(i, largest); 10. MaxHeapify(heap, largest)