Implement a binary heap by C++
5 min readAug 23, 2020
One nice implementation
The code below is taking this video’s implementation as a reference.
MaxHeap
// Implement a max heap
#include <iostream>
#include <vector>
using namespace std;class MaxHeap {
private:
int _size{};
vector<int> vect = {-1}; // 1 index based can make the child and parent index more simple
int p(int i) {return i>>1;}; // i/2
int l(int i) {return i<<1;}; // i*2;
int r(int i) {return (i<<1) + 1;}; // i*2 + 1;
void _shiftUp(int i);
void _shiftDown(int i);
public:
bool empty() const {return _size == 0;};
void push(int val);
int top();
void pop();
};void MaxHeap::push(int val) {
if (_size + 1 >= vect.size()) {
vect.push_back(0);
}
vect[++_size] = val;
_shiftUp(_size);
}void MaxHeap::_shiftUp(int i) {
if (i > _size) return;
if (i == 1) return;
if (vect[p(i)] < vect[i]) {
swap(vect[p(i)], vect[i]);
_shiftUp(p(i));
}
else return;
}int MaxHeap::top() {
if (empty()) return -1;
return vect[1];
}void MaxHeap::_shiftDown(int i) {
int largerChildId = i;
if (l(i)<=_size && vect[l(i)] > vect[i]) {
largerChildId = l(i);
}
if (r(i)<=_size && vect[r(i)] > vect[largerChildId]) {
largerChildId = r(i);
}
if (largerChildId != i) {
swap(vect[i], vect[largerChildId]);
_shiftDown(largerChildId);
}
}void MaxHeap::pop() {
if (empty()) return;
swap(vect[1], vect[_size--]);
_shiftDown(1);
// for (auto x : vect) cout<<x<<" ";
// cout<<endl;
}int main() {
MaxHeap maxHeap;
if (maxHeap.empty()) cout<<"good";
else cout<<"the initial maxHeap should be empty";
maxHeap.push(7);
maxHeap.push(8);
maxHeap.push(19);
maxHeap.push(8);
maxHeap.push(1);
cout << maxHeap.top() << endl;
maxHeap.pop();
cout << maxHeap.top() << endl;
maxHeap.pop();
cout << maxHeap.top() << endl;
maxHeap.pop();
cout << maxHeap.top() << endl;
return 0;
}// 7(1)
// 8(2) 9(3)
// 7 4 3
MinHeap
#include <iostream>
#include <vector>
// this is a min heap it has some bug and should be addressed soon
class MinHeap {
private:
std::vector<int> heap = {-1};
int size_ = 0;
int p(int i) {return i >>1;}
int l(int i) {return (i <<1);}
int r(int i) {return (i <<1) + 1;}
void shiftUp(int idx);
void shiftDown(int idx);
public:
bool empty() {return size_ == 0;}
void push(int v);
void pop();
int top();
};void MinHeap::shiftUp(int i){
if (i > size_ || i <= 0) return; //invalid i
if (i == 1) return; //bottom case
if (heap[p(i)] > heap[i]) {
std::swap(heap[p(i)], heap[i]);
shiftUp(p(i));
}
else return;
}void MinHeap::push(int v) {
if (size_ + 1 >= heap.size()) {
heap.push_back(v);
}
heap[++size_] = v;
shiftUp(size_);
return;
}void MinHeap::shiftDown(int i){
if (i >size_ || i <= 0) return; // invalid i
int smallerChildId = i;
if (l(i) <= size_ && heap[l(i)] < heap[i]) {
smallerChildId = l(i);
}
if (r(i) <= size_ && heap[r(i)] < heap[smallerChildId]) {
smallerChildId = r(i);
}
if (smallerChildId == i) return;
std::swap(heap[smallerChildId], heap[i]);
shiftDown(smallerChildId);
}void MinHeap::pop() {
if (size_ == 0) return;
std::swap(heap[size_--], heap[1]);
shiftDown(1);
}int MinHeap::top() {
if (size_ <= 0) return -1;
return heap[1];
}int main() {
MinHeap hq;
std::cout << hq.empty() << std::endl;
hq.push(1);
hq.push(4);
hq.push(0);
std::cout << hq.top() <<std::endl;
hq.pop();
std::cout << hq.top() <<std::endl;
hq.push(-1);
std::cout << hq.top() <<std::endl;}
MinHeap in python
def p(i):return i >> 1
def l(i):return i << 1
def r(i):return (i << 1) + 1
class MinHeap:
def __init__(self):
self.size = 0
self.heap = [-1]
def _shiftUp(self, i):
if i <= 0 or i > self.size:return
if i == 1:return # bottom case
if self.heap[p(i)] > self.heap[i]:
self.heap[p(i)], self.heap[i] = self.heap[i], self.heap[p(i)] # swap
self._shiftUp(p(i))
else:return
def _shiftDown(self, i):
if i <= 0 or i > self.size:return
smaller_child_id = i
left, right = l(i), r(i)
if left <= self.size and self.heap[left] < self.heap[i]:
smaller_child_id = left
if right <= self.size and self.heap[right] < self.heap[smaller_child_id]:
smaller_child_id = right
if smaller_child_id == i:
return
self.heap[smaller_child_id], self.heap[i] = self.heap[i], self.heap[smaller_child_id]
self._shiftDown(smaller_child_id)def __len__(self):
return len(self.heap) - 1
def push(self, x):
if self.size + 1 >= len(self.heap):
self.heap.append(x)
self.size += 1
self.heap[self.size] = x
self._shiftUp(self.size)
def empty(self):return self.size == 0
def pop(self):
if self.empty():return -1
top = self.heap[1]
self.heap[1], self.heap[self.size] = self.heap[self.size], self.heap[1]
self.size -= 1
self._shiftDown(1)
print(self.heap)
return top
if __name__ == "__main__":
hq = MinHeap()
print(hq.empty())
hq.push(1)
hq.push(4)
hq.push(0)
print(hq.pop())
Another nice implementation
A nice implementation of the binary heap from [1]. One problem for this implementation is the heapify function is missing.
#include <iostream>
#include <cstdlib>
#include <vector>
#include <iterator>
using namespace std;
class BHeap {
private:
vector <int> heap;
int l(int parent);
int r(int parent);
int par(int child);
void heapifyup(int index);
void heapifydown(int index);
public:
BHeap() {}
void Insert(int element);
void DeleteMin();
int ExtractMin();
void showHeap();
int Size();
};
int main() {
BHeap h;
while (1) {
cout<<"1.Insert Element"<<endl;
cout<<"2.Delete Minimum Element"<<endl;
cout<<"3.Extract Minimum Element"<<endl;
cout<<"4.Show Heap"<<endl;
cout<<"5.Exit"<<endl;
int c, e;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter the element to be inserted: ";
cin>>e;
h.Insert(e);
break;
case 2:
h.DeleteMin();
break;
case 3:
if (h.ExtractMin() == -1) {
cout<<"Heap is Empty"<<endl;
}
else
cout<<"Minimum Element: "<<h.ExtractMin()<<endl;
break;
case 4:
cout<<"Displaying elements of Hwap: ";
h.showHeap();
break;
case 5:
exit(1);
default:
cout<<"Enter Correct Choice"<<endl;
}
}
return 0;
}
int BHeap::Size() {
return heap.size();
}
void BHeap::Insert(int ele) {
heap.push_back(ele);
heapifyup(heap.size() -1);
}
void BHeap::DeleteMin() {
if (heap.size() == 0) {
cout<<"Heap is Empty"<<endl;
return;
}
heap[0] = heap.at(heap.size() - 1);
heap.pop_back();
heapifydown(0);
cout<<"Element Deleted"<<endl;
}
int BHeap::ExtractMin() {
if (heap.size() == 0) {
return -1;
}
else
return heap.front();
}
void BHeap::showHeap() {
vector <int>::iterator pos = heap.begin();
cout<<"Heap --> ";
while (pos != heap.end()) {
cout<<*pos<<" ";
pos++;
}
cout<<endl;
}
int BHeap::l(int parent) {
int l = 2 * parent + 1;
if (l < heap.size())
return l;
else
return -1;
}
int BHeap::r(int parent) {
int r = 2 * parent + 2;
if (r < heap.size())
return r;
else
return -1;
}
int BHeap::par(int child) {
int p = (child - 1)/2;
if (child == 0)
return -1;
else
return p;
}
void BHeap::heapifyup(int in) {
if (in >= 0 && par(in) >= 0 && heap[par(in)] > heap[in]) {
int temp = heap[in];
heap[in] = heap[par(in)];
heap[par(in)] = temp;
heapifyup(par(in));
}
}
void BHeap::heapifydown(int in) {
int child = l(in);
int child1 = r(in);
if (child >= 0 && child1 >= 0 && heap[child] > heap[child1]) {
child = child1;
}
if (child > 0 && heap[in] > heap[child]) {
int t = heap[in];
heap[in] = heap[child];
heap[child] = t;
heapifydown(child);
}
}Reference
[1] https://www.tutorialspoint.com/cplusplus-program-to-implement-binary-heap
