# Algorithms: Heaps

## Heaps

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.