Min and Max Heaps in C++
Min Heap
Min Heap Header (minHeap.h)
#include <vector>
#include <algorithm>
#include <iostream>
using std::endl;
using std::cout;
using std::swap;
using std::vector;
class minHeap{
private:
int size;
int capacity;
vector<int> heap;
int parent(int i){return (i - 1) / 2;}
int left(int i){return 2 * i + 1;}
int right(int i){return 2 * i + 2;}
public:
minHeap(int capacity);
void insert(int k);
int extractMin();
void heapify(int i);
void printHeap();
};
minHeap::minHeap(int capacity){
size = 0;
this->capacity = capacity;
heap.resize(capacity);
}
void minHeap::insert(int k){
if(size == capacity){
cout << "MIN HEAP FULL!" << endl;
return;
}
size++;
int i = size - 1;
heap[i] = k;
while(i != 0 && heap[parent(i)] > heap[i]){
swap(heap[i], heap[parent(i)]);
i = parent(i);
}
}
void minHeap::heapify(int i){
int l = left(i);
int r = right(i);
int smallest = i;
if((l < size) && (heap[l] < heap[smallest])){
smallest = l;
}if((r < size) && (heap[r] < heap[smallest])){
smallest = r;
}
if(smallest != i){
swap(heap[i], heap[smallest]);
heapify(smallest);
}
}
int minHeap::extractMin(){
if(size == 0){
cout << "EMPTY HEAP" << endl;
return -1;
}else if(size == 1){
size--;
return heap[0];
}else{
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
heap[size] = 0;
return root;
}
}
void minHeap::printHeap(){
for (int i = 0; i < heap.size(); i++ ){
cout << heap[i] << " ";
}
cout << endl;
}
Main File for Min Heap Output (main.cpp)
#include <iostream>
using std::endl;
using std::cout;
#include "minHeap.h"
int main(){
// Number of elements for our minHeap
int N = 10;
// Declare a heap with space for 10 elements
minHeap heap(N);
cout << "inserting 20 into minHeap " << endl;
heap.insert(20);
heap.printHeap();
cout << endl;
cout << "inserting 30 into minHeap " << endl;
heap.insert(30);
heap.printHeap();
cout << endl;
cout << "inserting 10 into minHeap " << endl;
heap.insert(10);
heap.printHeap();
cout << endl;
cout << "inserting 35 into minHeap " << endl;
heap.insert(35);
heap.printHeap();
cout << endl;
cout << "inserting 40 into minHeap " << endl;
heap.insert(40);
heap.printHeap();
cout << endl;
cout << "inserting 32 into minHeap " << endl;
heap.insert(32);
heap.printHeap();
cout << endl;
cout << "inserting 8 into minHeap " << endl;
heap.insert(8);
heap.printHeap();
cout << endl;
cout << "Extract min: " << heap.extractMin() << endl;
heap.printHeap();
cout << endl;
cout << "Extract Another min Value (10): " << heap.extractMin() << endl;
cout << endl;
heap.printHeap();
cout << "Extract Another min Value (20): " << heap.extractMin() << endl;
cout << endl;
heap.printHeap();
cout << "Extract Another min Value (30): " << heap.extractMin() << endl;
cout << endl;
heap.printHeap();
cout << "Extract Another min Value (32): " << heap.extractMin() << endl;
cout << endl;
heap.printHeap();
cout << "Extract Another min Value (35): " << heap.extractMin() << endl;
cout << endl;
heap.printHeap();
}
Output:
inserting 20 into minHeap
20 0 0 0 0 0 0 0 0 0
inserting 30 into minHeap
20 30 0 0 0 0 0 0 0 0
inserting 10 into minHeap
10 30 20 0 0 0 0 0 0 0
inserting 35 into minHeap
10 30 20 35 0 0 0 0 0 0
inserting 40 into minHeap
10 30 20 35 40 0 0 0 0 0
inserting 32 into minHeap
10 30 20 35 40 32 0 0 0 0
inserting 8 into minHeap
8 30 10 35 40 32 20 0 0 0
Extract min: 8
10 30 20 35 40 32 0 0 0 0
Extract Another min Value (10): 10
20 30 32 35 40 0 0 0 0 0
Extract Another min Value (20): 20
30 35 32 40 0 0 0 0 0 0
Extract Another min Value (30): 30
32 35 40 0 0 0 0 0 0 0
Extract Another min Value (32): 32
35 40 0 0 0 0 0 0 0 0
Extract Another min Value (35): 35
40 0 0 0 0 0 0 0 0 0
Max Heap
Max Heap Header (maxHeap.h)
#include <vector>
#include <algorithm>
#include <iostream>
using std::cout;
using std::endl;
using std::swap;
using std::vector;
class maxHeap{
private:
int size;
int capacity;
vector<int> heap;
int parent(int i){return (i - 1) / 2;}
int left(int i){return 2 * i + 1;}
int right(int i){return 2 * i + 2;}
public:
maxHeap(int capacity);
void insert(int k);
int extractMax();
void heapify(int i);
void printHeap();
};
maxHeap::maxHeap(int capacity){
size = 0;
this->capacity = capacity;
heap.resize(capacity);
}
void maxHeap::insert(int val){
if(size == capacity){
cout << "Sorry the Max Heap is Full!" << endl;
return;
}
size++;
int i = size - 1;
heap[i] = val;
while(i != 0 && heap[parent(i)] < heap[i])
{
swap(heap[i], heap[parent(i)]);
i = parent(i);
}
}
void maxHeap::heapify(int i){
int l = left(i);
int r = right(i);
int largest = i;
if((l < size) && (heap[l] > heap[largest])){
largest = l;
}if((r < size) && (heap[r] > heap[largest])){
largest = r;
}
if(largest != i){
swap(heap[i], heap[largest]);
heapify(largest);
}
}
int maxHeap::extractMax(){
if(size == 0){
cout << "Sorry the heap is Empty!" << endl;
return -1;
}else if(size == 1){
size--;
return heap[0];
}
else{
int root = heap[0];
heap[0] = heap[size - 1];
size--;
heapify(0);
heap[size] = 0;
return root;
}
}
void maxHeap::printHeap(){
for (int i = 0; i < heap.size(); i++ ){
cout << heap[i] << " ";
}
cout << endl;
}
Main File to Test (main.cpp)
#include "maxHeap.h"
#include <iostream>
using std::cout;
using std::endl;
int main(){
// Number of elements for our maxHeap
int N = 8;
// Declare a heap with space for 10 elements
maxHeap heap(N);
heap.insert(50);
heap.insert(30);
heap.insert(20);
heap.insert(15);
heap.insert(10);
heap.insert(8);
cout << "Current Heap: " << endl;
heap.printHeap();
cout << endl;
cout << "Lets insert 25 into our MaxHeap!! " <<endl;
heap.insert(25);
heap.printHeap();
cout << endl;
cout << "Extracting the Max from the Heap " << endl;
heap.extractMax();
cout << endl;
heap.printHeap();
}
Output:
Current Heap:
50 30 20 15 10 8 0 0
Lets insert 25 into our MaxHeap!!
50 30 25 15 10 8 20 0
Extracting the Max from the Heap
30 20 25 15 10 8 0 0