Heap Sort fits for data insertion and data sorting at the same time. It tries to store data in a complete binary tree, ensuring the nonleaf node is larger or smaller than the left/right leaf node. The advantage of storing data into complete binary tree is that the largest or smallest value always pop out in to root node. So, after forming the complete binary tree, we fetch the root value and store it in the first or the last location in a[N]
, and replace the root value with the corresponding value in a[N]
.
There are some important issues during implementation:
1. for the nonleaf node a[i]
, its leftleaf node is a[2*i + 1]
, and the rightleaf node is a[2*i + 2]
.
2. if the length of data to sort is N
, the leaf node number is int(N/2.0 + 0.5)
.
First, we need to write the heap adjust code.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 

Second, we have to sort the data with Heap Sort in an iterative way.
1 2 3 4 5 6 7 8 9 10 11 12 13 
