Heap Tree Sort and its implementation in C

Heap is an almost complete Binary Tree implemented in a sequential format such that the value at any of the nodes (nd) is >= or <= value of the children.

If nd >= children –> Maxheap ; If nd <= children –> Minheap ;

Inserting an item to a Heap

1. Join the item at the end of Heap so that Heap is still an ACBT (Almost Complete Binary Tree) but not necessarily a Heap.
2. Now gradually raise the item to the proper position in the Heap.

Sorting using a Heap

Heap sorting is simply an implementation of the general selection sort using a single array X[i] as a heap representing a descending priority queue. Heap sorting involves two phases.

Phase 1: Construct the heap by pre-processing the priority queue by a  ‘sift up’ operation

Phase 2: Repeatedly delete the largest item at the root of the queue and place it at the end of the queue and follow the item at the end of the queue to sink to the proper position in the array. The process is repeated till all the largest items are deleted once. The resulting array will be a sorted array.

Below is an example how to sort below list using heap sort –

List of numbers to sort – 12 40 25 33 16 52 77 82 55

Building the Heap

1)   12                          2)   40                     3)  40               4)  40

/      \                           /        \                     /      \               /       \

40        25                    12          25              12        25          33         25

/                        /

33                      12

5)   40                          6)   52                     7)  52               8)    77

/      \                           /        \                     /      \                 /        \

33        25                    33          40              33        40          33           52

/   \     /                     /      \      /                /    \     /      \       /     \       /    \

12     16  32               12       16 25             12     16  25     77   12     16  25    40

9)    82                      10)         82

/       \                              /        \

33       77                         55        77

/   \    /    \                   /      \     /       \

12   16  52  40             33      16  52      40

/                                 /       \

25                             25       12

Sorting the Heap

1)      77                           2)    55                           3)              52                                 4)               40

/      \                           /         \                                     /         \                                            /         \

55        52                   33           52                              33           40                                     33              12

/      \                           /     \       /   \                         /        \      /      \                              /        \         /     \

33       16                      25       16 12    40                  25         16  12       55                       25         16   52      55

/     \                          /       \                                   /          \                                             /          \          x[7]     x[8]

25    82                    77        82                             77          82                                       77           82

x[9]      x[10]                 x[9]         x[10]

5)                    33                                         6)                      25

/        \                                                          /            \

25            12                                                  16

/       \       /       \                                        /          \        /            \

40       16   52      55                                  40           33    52          55

/       \                                                       /         \

77       82                                                77           82

Efficiency of Heap Sorting

Heap sorting requires O(n logn) operations. It is inferior to quick sort since it requires twice as time as quick sort to sort randomly sorted input. But it is superior to Quick sort in the worst case since the execution time remains O(n logn).