A heap is a tree data structure where child nodes are always bigger than their parent (min heap) or larger than their parent (max heap). In a min heap, the smallest-valued node is at the root and each of the child nodes are bigger than the parent. This holds true for all subtrees. In a max heap, the largest-valued node is at the root and each of the child nodes are smaller than the parent. This also holds true for all subtrees.
A valid min heap:
In every section so far, we have made our own classes to support our data structure and then used that structure in the main() method. In the case of heaps, we are going to use the built in C++ heap data structure. The make_heap() command needs begin() and end() to be called on a vector of values. You can then call the front() (largest), back() (smallest), or size() methods on the vector because it was rearranged into the heap order. In the code below, the vector is ordered into a max heap.
As a practice exercise, you can build classes to support your own heap.
using namespace std;
#include <iostream>
#include <algorithm>
#include <vector>
int main() {
vector<int> vectorOne = { 2,4,6 };
make_heap(vectorOne.begin(), vectorOne.end());
cout << "Original contents of heap: ";
for (int i : vectorOne) {
cout << i << ", ";
}
cout << "\nBack of heap: " << vectorOne.back();
cout << "\nFront of heap: " << vectorOne.front();
/*
pushing new values onto the vector and then reorganizing the vector into an updated max heap
*/
vectorOne.push_back(1);
vectorOne.push_back(7);
push_heap(vectorOne.begin(), vectorOne.end());
cout << "\nHeap contents after pushing 1 and 7 to the heap: ";
for (int i : vectorOne) {
cout << i << ", ";
}
cout << "\nNew back of heap: " << vectorOne.back();
cout << "\nNew front of heap: " << vectorOne.front();
}
Output:
Original contents of heap: 6, 4, 2,
Back of heap: 2
Front of heap: 6
Heap contents after pushing 1 and 7 to the heap: 7, 6, 2, 1, 4,
New back of heap: 4
New front of heap: 7