Created
March 31, 2019 00:58
-
-
Save fernandozamoraj/1dc97b0d54f243e405c031b7a1910c6f to your computer and use it in GitHub Desktop.
Priority queue using heao
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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