In this algorithms lesson, we explain the heapsort algorithm for sorting an array of ordered elements. The heapsort algorithm consists of two primary steps. First, we construct a heap from the elements. Second, we repeatedly take the largest element of the heap and swap it with the end until we fully sort the array.

In the first step of the algorithm, we put the elements of the array in heap order, starting from the first index to the last. The image below shows what this looks like after the first nine elements have been put in heap order. The four shades of gray indicate the four levels of the heap, while red is used to show the elements that still need to be put into the heap.

The procedure for putting an element into the heap runs as follows. First, expand the size of the heap so that it contains the next element of the array. This new element is likely to be out of place, so that we no longer have a heap. Put the new element in its place by exchanging it with its parent while it is larger than its parent.

In the second step of the algorithm, we sort the elements of the heap, starting from the last index to the first. In the image below shows what this looks like after nine elements have been sorted. The last nine sorted elements are green, while the first six gray elements are still in heap order.

The procedure for removing a single element from the heap runs as follows. First, swap the first, or root, element to the end of the heap and shrink the size of hte heap to remove it from the heap. At this point, the root element has been put into its proper sorted position and the new root may violate the heap property. To fix the new root, swap it with its larger child node as long as one of the child nodes is larger.

Finally, we include the C++ code for the heapsort algorithm below. The code is similar to the code that we had in our heaps algorithm lesson. In fact, we only changed one line to turn the previous algorithm into a heapsort and that is the first line of the function RemoveRoot().

Changing that one line will make the program sort the array of elements; however, we made a few other simple modifications so that we could observe the stages of the sort. First, we removed the function OutputHeap() and the calls to it from main(). Second, we altered the OutputArray() function by adding a third parameter to specify the position where we should output a vertical bar to divide the elements into the two parts that we specified in our algorithm. Finally, we changed the calls to OutputArray() from main() so that they would output all of the elements of the array.

#include <iostream>

int Left(int iIndex) {
	return ((iIndex << 1) + 1);
}

int Right(int iIndex) {
	return ((iIndex << 1) + 2);
}

int Parent(int iIndex) {
	return ((iIndex - 1) >> 1);
}

void Swap(int& irX, int& irY) {
	int iTemp = irX;
	irX = irY;
	irY = iTemp;
}

int SwapWithChild(int iIndex, int* ipHeap, int iSize) {
	int iLeft		= Left(iIndex);
	int iRight		= Right(iIndex);
	int iLargest	= iIndex;
	if (iRight < iSize) {
		if (ipHeap[iLeft] < ipHeap[iRight]) {
			iLargest = iRight;
		} else {
			iLargest = iLeft;
		}
		if (ipHeap[iIndex] > ipHeap[iLargest]) {
			iLargest = iIndex;
		}
	} else if (iLeft < iSize) {
		if (ipHeap[iIndex] < ipHeap[iLeft]) {
			iLargest = iLeft;
		}
	}
	if (ipHeap[iIndex] < ipHeap[iLargest]) {
		Swap(ipHeap[iIndex], ipHeap[iLargest]);
	}
	return iLargest;
}

void RemoveRoot(int* ipHeap, int iSize) {
	// Swap the last element with the root
	Swap(ipHeap[0], ipHeap[iSize - 1]);
	--iSize;
	int iLasti = 0;
	int i = SwapWithChild(0, ipHeap, iSize);
	while (i != iLasti) {
		iLasti = i;
		i = SwapWithChild(i, ipHeap, iSize);
	}
}

int SwapWithParent(int i, int* ipHeap) {
	if (i < 1) {
		return i;
	}
	int iParent = Parent(i);
	if (ipHeap[i] > ipHeap[iParent]) {
		Swap(ipHeap[i], ipHeap[iParent]);
		return iParent;
	} else {
		return i;
	}
}

void AddElement(int iNewEntry, int* ipHeap, int iSize) {
	ipHeap[iSize] = iNewEntry;
	int iLasti = iSize;
	int i = SwapWithParent(iLasti, ipHeap);
	while (iLasti != i) {
		iLasti = i;
		i = SwapWithParent(i, ipHeap);
	}
}

void OutputArray(int* ipArray, int iBar, int iSize) {
	using namespace std;
	for (int i = 0; i < iSize; ++i) {
		if (i == iBar) {
			cout << "|  ";
		}
		cout << ipArray[i] << "  ";
	}
	cout << endl;
}

int main() {
	using namespace std;

	srand(1);

	int iaArray[15];
	for (int i = 0; i < 15; ++i) {
		iaArray[i] = (rand() % 100);
	}

	 // Output the heap after each element that we add
	for (int i = 0; i < 15; ++i) {
		AddElement(iaArray[i], iaArray, i);
		OutputArray(iaArray, i + 1, 15);
		cout << endl;
		cout << "---------------------------------------------" << endl;
	}

	 // Output the heap after each element that we remove
	for (int i = 0; i < 14; ++i) {
		RemoveRoot(iaArray, 15 - i);
		OutputArray(iaArray, 14 - i, 15);
		cout << endl;
		cout << "---------------------------------------------" << endl;
	}

    return 0;
}

Pressing (Ctrl + F5) compiles and executes the code as shown below. The output of the program does not fit into the console window. However, you can scroll up and look at the rest of the output.