Heap Sort Introduction

Heap Sort follows the philosophy of Selection Sort because it finds the maximum and swaps it into place. However, Heap Sort partially orders the data to make it easy to find the maximum. The partial ordering is a "heap," and, once it is built, it guarantees that the maximum value will be in the first position of the array.

At the beginning of the sort, the procedure called "BuildHeap" constructs the heap within the array. Once the heap is constructed, the element in the first position of the array will be the maximum and can be swapped into its correct position. That swap disrupts the heap, but it can be rebuilt by looking at a small portion of the elements in the array by the procedure "Heapify."

HeapSort() 
{
	BuildHeap();
	for (i = heap_size-1;i>=1;i--)
	{
		swap(0,i);
		/* now the heap is one smaller because the sorted */
		/* portion of the array has grown by one */
		heap_size--;
		heapify(0);
	}	
}

Heapify(i) {
	/* l and r are the two places we have to look to see if the heap is broken */
	l = 2*i+1;
	r = 2*i+2;	
	/* if the entries at l or r are bigger than the entry at i, we have to */
	/* swap the biggest one into the i position */
	if ((l < heap_size) && (data[l] > data[i]))
		largest = l;
	else
		largest = i;
	if ((r < heap_size) && (data[r] > data[largest]))
		largest = r;
	if (largest != i)
	{
		swap(i,largest);
		/* the heap was broken and we fixed it here.  Now we have to check */
		/* to see if the swap broke it further down */
		Heapify(largest);
	}	
}

Interestingly, the procedure "BuildHeap" uses N calls to Heapify to build the heap from small heaps into increasingly larger ones.

BuildHeap() 
{
	heap_size = num_used;
	for (i=heap_size/2;i>=0;i--)
	{
		Heapify(i);
	}	

	return;
}