Heap Sort

November 6, 2009

We begin with a simple version that implements the heapsort algorithm directly:

function swap(A,i,j,    t) {
    t = A[i]; A[i] = A[j]; A[j] = t }

function heapify(A,left,right,    p,c) {
    for (p=left; (c=2*p) <= right; p=c) {
        if (c<right && A[c] < A[c+1]) c++
        if (A[p] < A[c]) swap(A, c, p) } }

function sort(A,n,    i) {
    for (i=int(n/2); i>=1; i--)
        heapify(A, i, n)
    for (i=n; i>1; i--) {
        swap(A, 1, i)
        heapify(A, 1, i-1) } }

By moving the swap inline, we can move the invariant part of the swap out of the inner loop:

function heapify(A,left,right,    p,c,t) {
    t = A[left]
    for (p=left; (c=2*p) <= right; p=c) {
        if (c<right && A[c] < A[c+1]) c++
        if (t < A[c]) A[p] = A[c]; else break }
    A[p] = t }

function sort(A,n,    i,t) {
    for (i=int(n/2); i>=1; i--)
        heapify(A, i, n)
    for (i=n; i>1; i--) {
        t = A[1]; A[1] = A[i]; A[i] = t
        heapify(A, 1, i-1) } }

It has been shown empirically that instead of heapifying from the top it is better to sift the item at the top of the heap all the way to the bottom, then sift it back up to its proper position, eliminating the comparison between a parent and its smallest child on the trip down:

function heapify(A,left,right,    p,c,t) {
    t = A[left]
    for (p=left; (c=2*p) <= right; p=c) {
        if (c<right && A[c] < A[c+1]) c++
        A[p] = A[c] }
    for (c=p; (p=int(c/2)) >= left; c=p) {
        if (t > A[p]) A[c] = A[p]; else break }
    A[c] = t }

function sort(A,n,    i,t) {
    for (i=int(n/2); i>=1; i--)
        heapify(A, i, n)
    for (i=n; i>1; i--) {
        t = A[1]; A[1] = A[i]; A[i] = t
        heapify(A, 1, i-1) } }

Our final version moves the heapify function inline:

function sort(A,n,    l,r,p,c,t) {
    if (n > 1) {
        l = int(n/2) + 1; r = n
        while(1) {
            if (l > 1) t = A[--l]
            else { t = A[r]; A[r--] = A[1]
                   if (r == 1) { A[1] = t; return } }
            for (p=l; (c=2*p) <= r; p=c) {
                if (c < r && A[c] < A[c+1]) c++
                A[p] = A[c] }
            for (c=p; (p=int(c/2)) >= l; c=p) {
                if (A[p] < t) A[c] = A[p]; else break }
            A[c] = t } } }

Like quicksort, heapsort runs in time O(n log n). The final heapsort is quite fast, nearly as fast as a well-tuned quicksort and without the annoying possibility of a quadratic worst-case. The code, including the test suite from the prior exercise, is collected at http://programmingpraxis.codepad.org/6HryLp9f, but you can’t run it, because codepad doesn’t provide an Awk interpreter.

About these ads

Pages: 1 2

One Response to “Heap Sort”

  1. Vikas Tandi said

    here is my implementation in c

    
    static void heapify(int arr[], int left, int right);
    static void sort(int arr[], int left, int right);
    static void siftup(int arr[], int left, int right, int key);
    
    void heapsort(int arr[], int left, int right)
    {
    	/* transform input file into a heap */
    	heapify(arr, (right+1)/2, right+1);
    
    	/* sort the heap */
    	sort(arr, left+1, right+1);
    }
    
    static void heapify(int arr[], int left, int right)
    {
    	int i;
    
    	/* convert to heap */
    	for(i = left; i > 0; i--)
    		siftup(arr, i, right, arr[i-1]);
    }
    
    static void sort(int arr[], int left, int right)
    {
    	int i, key;
    
    	for(i = right; i > 1; i--)
    	{
    		key = arr[i-1];
    		arr[i-1] = arr[left-1];		/* move the biggest element to the rightmost position in array */
    
    		/* move up the next biggest element to root */
    		siftup(arr, left, i-1, key);
    	}
    }
    
    static void siftup(int arr[], int left, int right, int key)
    {
    	int i, j;
    
    	/* move down the tree */
    	for(i = left, j = 2*i;  j <= right; i = j, j = 2*i)
    	{
    		/* j should point to the largest child */
    		if(j < right && arr[j-1] < arr[j])
    			j++;
    
    		/* if child is smaller or equal to parent, than break out of loop */
    		if(key >= arr[j-1])
    			break;
    		
    		/* move up the child element */
    		arr[i-1] = arr[j-1];
    	}
    	arr[i-1] = key;
    }
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 621 other followers

%d bloggers like this: