HeapSort The algorithm runs in two steps. Given an array of data, first, we build a heap and then turn it into a sorted list by calling deleteMin. The running time of the algorithm is O(n log n). Example. Given an array {3, 1, 6, 5, 2, 4}.

HeapSort.txt

1. build a heap     1, 2, 4, 5, 3, 6
2. turn this heap into a sorted list

     deleteMin
     1, 2, 4, 5, 3, 6           swap 1 and 6
     6, 2, 4, 5, 3,        1    restore heap
     2, 6, 4, 5, 3,        1
     2, 3, 4, 5, 6,        1

     deleteMin
     2, 3, 4, 5, 6,        1    swap 2 and 6
     6, 3, 4, 5,        2, 1    restore heap
     3, 6, 4, 5,        2, 1
     3, 5, 4, 6,        2, 1

     deleteMin
     3, 5, 4, 6,       2, 1     swap 3 and 6
     6, 5, 4,       3, 2, 1     restore heap
     4, 5, 6,       3, 2, 1     restore heap

     deleteMin
     4, 5, 6,       3, 2, 1     swap 4 and 6
     6, 5,       4, 3, 2, 1     restore heap
     5, 6,       4, 3, 2, 1

     deleteMin

     6,       5, 4, 3, 2, 1