Heap can be utilized in sorting as well. A maximum heap is built using the linear time algorithm. After this, the largest item is deleted N times. The largest item can be added to the position that became empty as a result of the deletion. Since the items are removed from the largest to the smallest (maxheap) and the deleted item is placed at the empty position at the end of the array, the items will end up in order from smallest to largest.
Exercises: a) Heapsort
|
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 perform all the required operations necessary with the MaxHeapify algorithm in order to restore the heap property again. Algorithm 5 HeapSort(A)
|
b) Is Heapsort a stable sorting algorithm??
This document was last updated 13.8.2009. Please send your comments to Mikko Laakso, Ari Korhonen, and Ville Karavirta.