3
\$\begingroup\$

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] << " ";
    }
};
\$\endgroup\$
1
  • \$\begingroup\$ Is this really an indexed priority queue? There is no priority associated with elements, and when you push something it always goes to the back. It looks more like an "indexed queue" to me. \$\endgroup\$ Commented Nov 17, 2024 at 19:18

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.