Heap Sort

November 6, 2009

A priority queue is a data structure that permits insertion of a new element and retrieval of its smallest member; we have seen priority queues in two previous exercises. Priority queues permit sorting by inserting elements in random order and retrieving them in sorted order. Heapsort uses the heap data structure to maintain a priority queue. The heap is a tree embedded in an array, with the property that the item at each index i of the array is less than the children at indices 2i and 2i+1.

The key to understanding heapsort is a function we call heapify that gives the sub-array A[i .. n] the heap property if the sub-array A[i+1 .. n] already has the property. Heapify starts at the ith element of the array and swaps each element with its smallest child, repeating the operation at that child, stopping at the end of the array or when the current element is smaller than either of its children. Then heapsort works in two phases; the first phase forms an initial heap by calling heapify on each element of the array from n/2 down to 1, then a second phase extracts the elements in order by repeatedly swapping the first element with the last, re-heaping the sub-array that excludes the last element, and recurring with the smaller sub-array that excludes the last element.

Your task is to write a function that sorts an array using the heapsort algorithm, using the conventions of the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

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 629 other followers

%d bloggers like this: