Heap

Algorithms for Sorting - Heapsort

1. Heapsort
Based on Priority Queues
Sorts in O(NlogN) time by performing N times deleteMin operations.
Why O(NlogN)?

• Each deleteMin operation takes logN running time.
• N times performing deleteMin → NlogN running time
Basic algorithm (not very efficient - extra memory required):

1. Store N elements in a binary heap tree.
2. Perform deleteMin operation N times, storing each element deleted from
   the heap into another array.
3. Copy back the array.
Improvements: Use the same array to store the deleted elements
instead of using another array
How can we do this?
After each deletion we percolate down the hole that is formed after the deletion,
and as a result we get a vacant position in the array - the last cell.
There we store the deleted element.
When all the elements are deleted and stored in the same array following the above method,
the elements will be there in reversed order.
What is the remedy for this?

Store the elements in the binary heap tree in reverse order of priority -
then at the end the elements in the array will be in correct order. Complexity of heap sort: O(NlogN) is the rough estimate.
Here is an example of heapsort.

---

Learning Goals

• Be able to explain how heapsort works and its complexity.

---

Exam-like questions

1. Explain the complexity of heapsort
2. Given an array e.g. 17, 23, 10, 1, 7, 16, 9, 20, sort it on paper using heapsort
   Write down explicitly each step.