In this algorithms lesson, we explain how to create and maintain a heap. A heap is an arrangement of ordered elements that partially sorts those elements so that they may be quickly added and removed while maintaining the partial ordering.

Rather than explain what we already went over in the video, we will cover the C++ code (listed below) in greater depth here. We create a random array of 15 integers, which have values between 0 and 99, inclusive. Then we add each of these integers into our heap by calling AddElement(). We output the elements that we have added to the heap as an array (OutputArray()) and then as a binary tree (OutputHeap()) after each element is added. Then we remove the elements one by one by calling RemoveRoot(). Again, we output the heap as array and then as a binary tree. That is basically all there is to the main() function.

The function, AddElement(), takes three arguments. The first argument, iNewEntry, is the entry that is to be added to the heap as the next element. The second argument, ipHeap, is a pointer to the beginning of the array or heap. The third argument, iSize, is the current size of the heap. Inside the function, the last index of the array given by ipHeap, is assigned the value iNewEntry. Then the function SwapWithParent() is called repeatedly until it returns the index that is passed in to indicate that the entry is in its proper place, and we now have a heap with an additional element in it.

The function, SwapWithParent(), takes two arguments. The first argument, i, is the entry that may be out of place; specifically, this entry may need to move up the heap. The second argument, ipHeap, is a pointer to the beginning of the array or heap. This function then tests the entry at i to check whether it needs to move up the heap. If the entry moves up, the new index of the entry is returned. Otherwise, the entry remains where it is and the original index is returned.

The function, RemoveRoot(), takes two arguments. The first argument, ipHeap, is a pointer to the beginning of the array or heap. The second argument, iSize, is the current size of the heap. Inside the function, the first index, or root node, of the array given by ipHeap, is assigned the value of the entry at the end of the array. The the heap size is reduced to shrink the heap and effectively remove the last element. Then the function SwapWithChild() is called repeatedly until it returns the index that is passed in to indicate that the entry is in its proper place, and we now have a heap with one less element in it.

The function, SwapWithChild(), takes three arguments. The first argument, iIndex, is the entry that may be out of place; specifically, this entry may need to move down the heap. The second argument, ipHeap, is a pointer to the beginning of the array or heap. The third argument, iSize, is the current size of the heap. This function then tests the entry at iIndex to check whether it needs to move it down the heap. If the entry moves down, the new index of the entry is returned. Otherwise, the entry remains where it is and the original index, iIndex, is returned.

The remaining elements either simple or not essential to the algorithm. The functions OutputHeap() and OutputArray() are used to output the entries as a binary tree or in the order that they are stored in the array, respectively. Near the start of the code, there is a simple Swap() function that is used to swap intger values. At the beginning of the code, there are three functions that are use to calculate the indices of the left and right children and the parent, using the formulas 2x+1, 2x+2, and (x-1)/2, for a given index x.

#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) {
	 // Put the last element at the root
	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 OutputHeap(int* ipHeap, int iSize) {
	using namespace std;

	 // Find the largest power of two, That is the depth
	int iDepth = 0;
	int iCopy = iSize;
	while (iCopy > 0) {
		iCopy >>= 1;
		++iDepth;
	}

	int iMaxWidth = (1 << iDepth);
	int iCharWidth = 4*iMaxWidth;
	int iEntry = 0;

	for (int i = 0; i < iDepth; ++i) {
		int iPowerOf2 = (1 << i);
		for (int j = 0; j < iPowerOf2; ++j) {
			int iSpacesBefore = ((iCharWidth/(1 << (i + 1))) - 1);
			 // Spaces before number
			for (int k = 0; k < iSpacesBefore; ++k) {
				cout << " ";
			}
			 // Output an extra space if the number is less than 10
			if (ipHeap[iEntry] < 10) {
				cout << " ";
			}
			 // Output the entry and the spaces after it
			cout << ipHeap[iEntry];
			++iEntry;
			if (iEntry >= iSize) {
				cout << endl;
				return;
			}
			for (int k = 0; k < iSpacesBefore; ++k) {
				cout << " ";
			}
		}
		cout << endl << endl;
	}
}

void OutputArray(int* ipArray, int iSize) {
	using namespace std;
	for (int i = 0; i < iSize; ++i) {
		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);
		cout << endl;
		OutputHeap(iaArray, i + 1);
		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);
		cout << endl;
		OutputHeap(iaArray, 14 - i);
		cout << "---------------------------------------------" << endl;
	}

    return 0;
}

The output of the program does not fit into the console window. However, the end of the output is shown in the image below. If you compile and run the code, you can scroll up and look at the rest of the output.