Page 244 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Unit 13: Sorting

13.6.3 Heap Sort Notes

Heap Sort is a comparison based algorithm. It bases on building a heap tree from the data set,
and then it removes the greatest element from the tree and adds it to the end of the sorted list.
There are two ways to do this, either to add the highest value to the root of the tree, or as one of
the left/right child with the greatest depth.

The heap tree is built according to the data set. Then the greatest value is move to the root of the
tree, and then it is removed. This represents the highest value from the data set, so it is added to
the end of the sorted list. Next, the heap is reconstructed, and the second highest value is added
to the top and then it is removed. This continues until the tree is empty and the list is full.

Example: Having the following list, let’s try to use heapsort to arrange the numbers
from lowest to greatest:

Unsorted list: 15, 19, 10, 7, 17, 16.
Building the heap tree:

Start with the rightmost node at height 1 – the node at position 3 = Size/2. It has one greater child
and has to be percolated down:

And it will look like this:

LOVELY PROFESSIONAL UNIVERSITY 237