Skip to content

Instantly share code, notes, and snippets.

@fernandozamoraj
Created March 31, 2019 00:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save fernandozamoraj/1dc97b0d54f243e405c031b7a1910c6f to your computer and use it in GitHub Desktop.
Save fernandozamoraj/1dc97b0d54f243e405c031b7a1910c6f to your computer and use it in GitHub Desktop.
Priority queue using heao
#include<iostream>
#include<string>
using namespace std;
template <class T>
class PriorityQueue{
private:
T *_array;
int _capacity;
int _size;
T _defaultValue;
void BubbleUp(int idx){
if(idx != 0 && Parent(idx) < _array[idx]){
Swap(GetParent(idx), idx);
BubbleUp(GetParent(idx));
}
}
void BubbleDown(int idx){
int greatest = idx;
//Check if left child is greater than parent
if(LeftValue(idx) > _array[greatest]){
greatest = GetLeft(idx);
}
//Check if right child is greater than current greatest
if(RightValue(idx) > _array[greatest]){
greatest = GetRight(idx);
}
//Check if one of the childer were greater than the parent
//if one of them is then swap continue to bubble up
if(greatest != idx){
Swap(idx, greatest);
BubbleDown(greatest);
}
}
int GetLeft(int idx){
return idx * 2 + 1;
}
int GetRight(int idx){
return idx * 2 + 2;
}
T LeftValue(int idx){
int leftIdx = GetLeft(idx);
if(leftIdx < _capacity){
return _array[leftIdx];
}
return _defaultValue;
}
T RightValue(int idx){
int rightIdx = GetRight(idx);
if(rightIdx < _capacity){
return _array[rightIdx];
}
return _defaultValue;
}
T Parent(int idx){
if(idx == 0){
return _defaultValue;
}
return _array[idx / 2];
}
int GetParent(int idx){
return idx / 2;
}
void Swap(int idxa, int idxb){
T temp = _array[idxa];
_array[idxa] = _array[idxb];
_array[idxb] = temp;
}
public:
PriorityQueue(T defaultValue, int capacity){
_defaultValue = defaultValue;
_capacity = capacity;
_array = new T[capacity];
_size = 0;
}
void Enque(T val){
_array[_size++] = val;
BubbleUp(_size-1);
}
T DeQueue(){
if(IsEmpty()){
cout << "Dequeing Emtpy queue..." << endl;
return _defaultValue;
}
Swap(0, _size-1);
T temp = _array[_size-1];
_array[_size-1] = _defaultValue;
_size--;
BubbleDown(0);
return temp;
}
T PeekNext(){
if(_size > 0)
return _array[_size-1];
return _defaultValue;
}
bool IsEmpty(){
return _size == 0;
}
};
int main(int argc, char *argv[]){
PriorityQueue<int> test(0, 1024);
test.Enque( 10);
test.Enque( 30);
test.Enque( 40);
test.Enque( 10);
test.Enque( 130);
test.Enque( 150);
test.Enque( 10);
while(!test.IsEmpty()){
int item = test.DeQueue();
cout << item << endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment