heap sort

A simple heap sort implementation was addedd.

Actually two steps for heap sort:

1. Build a max heap
2. Heap sort

To build a max heap, use max_heapify procedure to make each parent node larger than its child node. From node n/2(the last parent node in the tree) down to node 0, check if current node is larger than its child node, if not, change value with largest node, then recursive the largest node.

To perform heap sort, exchange node 0 with last node, reduce the heap size, then use max_heapify to make node 0 is the largest node in the tree.

For Heap sort, T(n) = O(nlgn) Although it spends more time than merge sort and qsort, which are also O(nlgn), but from the increase trend, it still use O(nlgn). See below data:

Round1:
(venv) [jyang2@ctu-bits-calc0 sort]$ python sort.py 10000
Original Array
Sorted Array, usage=0.252530

Round2:
(venv) [jyang2@ctu-bits-calc0 sort]$ python sort.py 100000
Original Array
Sorted Array, usage=3.176408

Round3:
(venv) [jyang2@ctu-bits-calc0 sort]$ python sort.py 1000000
Original Array
Sorted Array, usage=39.565229

the scale for each round is 10 times than previous one.

times2 = n3*lgn3/n2*lgn2 = 10 * lg(1000000)/lg(100000) = 10 * 6 / 5 = 12
T3=39.565229 T2=3.176408 T3/T2 = 12.455

times1 = n2*lgn2/n1*lgn1 = 10 * lg(100000)/lg(10000) = 10 * 5 / 4 = 12.5
T2=3.176408 T1=0.252530 T3/T2 = 12.578

From the trend, we can see that when n increases 10 times, the time usage just increase about n*lgn times.

BTW: sort 1000000 elements by merge sort in same machine:

(venv) [jyang2@ctu-bits-calc0 sort]$ python merge_sort.py 1000000
Original Array
Sorted Array, usage=11.254584