I'm learning Graph Theory and trying to solve the Dijkstra Problem. One of the best ways to solve the problem is to use Indexed Priority Queue and so, I implemented it. The code is below. Pls review and tell me how I can write it better. I'm still very much of an amateur so it would be my pleasure to be helped! Tks! https://github.com/DanhCaBa/dsa-cpp/blob/main/indexed_priority_queue.exe
class minIndexedPriorityQueue {
public:
// q: Indexed-Priority Queue | a: Original array
vector<int> q, a;
// positionInHeap: index->nodePos | indexOfNode: nodePos->index
vector<int> positionInHeap, indexOfNode;
int treeSize = 0, actualSize = 0;
/// @brief Switch two nodes in the heap (PIT & ION as well)
/// @param pos1 First node
/// @param pos2 Second node
void switchNodes(int pos1, int pos2){
int z = q[pos1];
q[pos1] = q[pos2];
q[pos2] = z;
z = indexOfNode[pos1];
indexOfNode[pos1] = indexOfNode[pos2];
indexOfNode[pos2] = z;
z = positionInHeap[indexOfNode[pos1]];
positionInHeap[indexOfNode[pos1]] = positionInHeap[indexOfNode[pos2]];
positionInHeap[indexOfNode[pos2]] = z;
}
/// @brief bubble up the node in the heap
/// @param pos
void bubbleUp(int pos){
while (pos > 1 && q[pos/2] > q[pos]){
switchNodes(pos,pos/2);
pos /= 2;
}
return;
}
/// @brief bubble down the node in the heap
/// @param pos
void bubbleDown(int pos){
if (pos*2 > treeSize) return;
if (pos*2+1 <= treeSize) {
if (q[pos] <= q[pos*2+1] && q[pos] < q[pos*2]) return;
if (q[pos*2] < q[pos*2+1]){
switchNodes(pos,pos*2);
bubbleDown(pos*2);
return;
}
switchNodes(pos,pos*2+1);
bubbleDown(pos*2+1);
} else {
if (q[pos] <= q[pos*2]) return;
else {
switchNodes(pos,pos*2);
bubbleDown(pos*2);
}
}
return;
}
/// @brief Create IPQ from given array
/// @param array Vector array which consists of integers
void makeQueue(vector<int> array){
treeSize = array.size();
actualSize = treeSize;
a.resize(treeSize+1, -1);
q.resize(treeSize+1, -1);
positionInHeap.resize(treeSize+1, -1);
indexOfNode.resize(treeSize+1, -1);
for (int i = 1; i <= treeSize; i++){
a[i] = array[i-1];
q[i] = array[i-1];
positionInHeap[i] = i;
indexOfNode[i] = i;
if (i == 1) continue;
bubbleUp(i);
}
}
/// @brief Push a new element into queue with the index of size
/// @param value The value of the element
void push(int value){
treeSize++;
actualSize++;
a.push_back(value);
positionInHeap.push_back(treeSize);
if (treeSize < actualSize) indexOfNode[treeSize] = actualSize;
else indexOfNode.push_back(actualSize);
bubbleUp(treeSize);
}
/// @brief Pop the node with given position
/// @param pos The index of the node
void popAt(int pos){
switchNodes(pos,treeSize);
a[indexOfNode[treeSize]] = -1;
positionInHeap[indexOfNode[treeSize]] = -1;
indexOfNode[treeSize] = -1;
treeSize--;
bubbleDown(pos);
bubbleUp(pos);
}
/// @brief Pop the top node
void popTop(){
switchNodes(1,treeSize);
a[indexOfNode[treeSize]] = -1;
positionInHeap[indexOfNode[treeSize]] = -1;
indexOfNode[treeSize] = -1;
treeSize--;
bubbleDown(1);
}
/// @brief Update the node with given position with new value
/// @param pos The position of the node
/// @param value The new value
void update(int pos, int value){
a[indexOfNode[pos]] = value;
q[pos] = value;
bubbleDown(pos);
bubbleUp(pos);
}
/// @brief Return the top node
/// @return The pair {index,value} of the top node
pair<int,int> top(){
return {indexOfNode[1],q[1]};
}
/// @brief Return the queue size
/// @return The integer that indicates queue size
int size(){
return treeSize;
}
/// @brief Return if the queue is empty or not
/// @return true: the queue is empty | false: the queue is not empty
bool empty(){
return (treeSize>0?false:true);
}
/// @brief Print out arrays in order a -> q -> positionInHeap -> indexOfNode
void print(){
for (int i = 1; i <= actualSize; i++) cout << a[i] << " ";
cout << "\n";
for (int i = 1; i <= treeSize; i++) cout << q[i] << " ";
cout << "\n";
for (int i = 1; i <= actualSize; i++) cout << positionInHeap[i] << " ";
cout << "\n";
for (int i = 1; i <= treeSize; i++) cout << indexOfNode[i] << " ";
}
};