Sorting and Analysis

Recall that Heap Sort basically operates by building a heap with n values then destroying the heap.

A complete binary tree with n nodes means that at most there are log n nodes from the root (top) to a leaf (a node at the bottom of the tree)

Insertion may require the percolate up process. The number of times a node needs to percolate up can be no more than the number of nodes from the root to the leaf. Therefore, it is pretty easy to see that this percolate up process is O(log n) for a tree with n nodes. This means that to add a value to a Heap is a process that is O(n log n). In order for us to build a heap we need to insert into it n times. Therefore, the worst case runtime for this process is O(n log n)

The deletion process may require a percolate down process. Like the percolate up process this also is O(log n). Thus, to remove a value from the heap is O(log n). We need to remove n values so this process is O(n log n).

To heap sort we build heap O(n log n) then destroy the heap O(n log n). Therefore the whole sorting algorithm has a runtime of O(n log n)

Our heap can be represented with an array. The simplest implementation of heap sort would be to create a heap object and then doing the following with it:

void heapSort(int data[],int size){
    Heap theheap;
    for(int i=0;i<size;i++){
        theheap.insert(data[i]);
    }
    for(int i=0;i<size;i++){
        data[i]=theheap.front();
        theheap.delete();
    }
}

but this is not actually a good implementation. The above would create a heap as it goes meaning that we need to actually double the data storage as the heap itself would be an array that is as big as data. Thus, the function would have the same drawback as merge sort.

What we want to be able to do is to implement the heap sort in place.

We can do this by borrowing the idea from insertion sort... in that algorithm we start off by hiving off the first element and saying that it is a sorted array. We then "insert" successive elements into this sorted array so that it stays sorted.

For heap sort we start off by using the first element as the root of the heap. Successive elements are then placed into the heap in place. Because new nodes are always bottom level leftmost, the element added will always be "end" of the array. Thus, similar to doing an insertion sort...we insert subsequent values into our heap which is being formed at the front end.

One key thing we have to change though is the priority. We actually need to ensure that items with that should go towards the end of the array is considered highest priority for the heap. Thus if we were sorting an array in ascending order (small to big) we should use give larger numbers a higher priority.

The reason is this... when we start to remove from the heap, the node that is first removed is from the bottom level, right most. this is essentially last node in the heap part of the array. However, the value that is removed comes from the root. Since the position that is freed up is at the end of the array, we want to ensure that the value that is removed first is the lowest priority item instead of highest otherwise our list will be sorted backwards.

Thus, to sort an array in ascending order (small to big), our heap should be built so that larger values have higher priority.