Ronzii's Blog

Just your average geek's blog

Heap Sort

Heap Sort is a comparison based sorting algorithm. The logical structure of a heap is such that a parent(i) should be larger than its children at 2*i and 2*i+1.  The following example illustrates the structure of a heap. Eg. 100 is parent, 19 and 36 are its children. This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap Here are some auxiliary functions that would be required to implement heap sort

int leftChild(int n)
{
    return 2*n;
}
int rightChild(int n)
{
    return (2*n+1);
}

Heap-sort begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the partially sorted array. Each and every node in the array must follow the above structure.

void heapify(int a[],int length,int i)
{
    int left = leftChild(i);
    int right = rightChild(i);
    int largest = i;
    if(left<length && a[left] > a[i])
    {
        largest = left;
    }
    if(right<length && a[right]>a[largest])
    {
        largest  = right;
    }
    if(largest!=i)
    {
        swap(a[i],a[largest]);
        heapify(a,length,largest);
    }
}

This function is used to compare a root node with its 2 children and replace the root node with the largest of all three. As we can see this function is recursive, if the position of the element has been changed then heapify must be called again to ensure the rest of structure obeys the properties of a heap. The complexity of this function is O(log(n))
Now, to build a max heap we just need a for loop 🙂

void buildMaxHeap(int a[], int length)
{
    for(int i = (length-1)/2; i>=0; i--)
    {
        heapify(a,length,i);
    }
}

This function has a average running time of O(n* log(n)) as is apparent from the complexity of the for loop and heapify function.
Now, our array has been transformed into a heap. We can perform heap sort.
The main concept heap-sort follows is that the largest element is always at the top of the list. We swap this element to the end of the list, decreased the length of the list and then heapify the first node of the list.

void heapSort(int a[],int length)
{
    buildMaxHeap(a,length);
    for(int i= length-1 ; i>0; i--)
    {
        swap(a[0],a[i]);
        length--;
        heapify(a,length,0);
    }
}

The complexity of this function is O(n* log(n)) and requires pre-computation of O(n* log(n))

Advertisements

July 7, 2011 Posted by | C++, Sorting | , , , | Leave a comment