Week 9 - Complexity of HeapSort Algorithm (episode 1)

As we talks about time complexity in lecture, we have mentioned Merge and binary search. In order to follow up "Complexity", I would like to do more on the other kinds of sort. Heap sort is the first sorting algorithm I have learned in csc108 from last year which may be more impressive to most of you and me.

So, basically, there are two step algorithm in Heap sort. The first step is to build up a heap out of an array. Then the second step is to begin with removing the smallest element from the heap then put it into an array.

Here is the function I write for the Heap sort. I'd like to solve this complexity precisely in next episode.


def Heapify(A, i, n):
    l = Left( i )
    r = Right( i )
    if l A[ i ]:
        largest = l
    else:
        largest = i
    if r A[ largest ]:
        largest = r
    if largest != i:
        A[ i ], A[ largest ] = A[ largest ], A[ i ]
        Heapify(A, largest, n)


def BuildHeap(A):
    n = len(A) - 1
    for i in range( n/2 ,0 ,-1 ):
        Heapify(A, i, n)


def HeapSort(A):
    BuildHeap(A)
    HeapSize = len(A) - 1
    for i in range( HeapSize, 1 , -1 ):
        A[ 1 ],A[ i ] = A[ i ],A[ 1 ]
        HeapSize = HeapSize-1
        Heapify( A,1,HeapSize )