Skip to content

Instantly share code, notes, and snippets.

@truncs
Created February 12, 2012 20:54
Show Gist options
  • Save truncs/1810804 to your computer and use it in GitHub Desktop.
Save truncs/1810804 to your computer and use it in GitHub Desktop.
Heap in C++
#include <iostream>
#include <vector>
using namespace std;
template <class T>
class Heap {
vector<T> list;
void bubbleUp();
void bubbleDown();
void swap(int child, int parent);
int getLeftChild(int parent);
int getRightChild(int parent);
int getParent(int child);
public:
Heap();
void insert(T );
T remove();
int getSize();
};
template <class T>
Heap<T> :: Heap(){
}
template <class T>
int Heap<T> :: getSize(){
return list.size();
}
template <class T>
void Heap<T>::swap(int child, int parent) {
T temp;
temp = list[child];
list[child] = list[parent];
list[parent] = temp;
}
template <class T>
int Heap<T> :: getParent(int child) {
if (child % 2 == 0)
return (child /2 ) -1;
else
return child/2;
}
template <class T>
int Heap<T> :: getLeftChild(int parent){
return 2*parent +1;
}
template <class T>
int Heap<T> :: getRightChild(int parent){
return 2 * parent + 2;
}
template <class T>
void Heap<T> :: insert(T value) {
list.push_back(value);
bubbleUp();
}
template <class T>
void Heap <T>:: bubbleUp() {
int child = list.size() - 1;
int parent = getParent(child);
while (list[child] > list[parent] && child >=0 && parent >= 0) {
swap(child, parent);
child = parent;
parent = getParent(child);
}
}
template <class T>
T Heap<T> :: remove() {
int child = list.size() - 1;
swap(child, 0);
T value = list.back();
list.pop_back();
bubbleDown();
return value;
}
template <class T>
void Heap<T> :: bubbleDown() {
int parent = 0;
while (1) {
int left = getLeftChild(parent);
int right = getRightChild(parent);
int length = list.size();
int largest = parent;
if (left < length && list[left] > list[largest])
largest = left;
if (right < length && list[right] > list[largest])
largest = right;
if (largest != parent) {
swap(largest, parent);
parent = largest;
}
else
break;
}
}
int main(){
int a[] = {4, 5,2,3,6,7};
Heap<int> heap;
int len = sizeof(a) /sizeof(int);
int i =0;
for (i = 0; i < len; i++)
{
heap.insert(a[i]);
}
while(heap.getSize() > 0)
cout<<"Heap Max\t"<< heap.remove()<<endl;
return 0;
}
@108krohan
Copy link

Rock solid implementation!

@satejplatonist
Copy link

THANK YOU VERY MUCH !
You helped me for my practical exams , the cleanest code i have seen till now

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment