2
\$\begingroup\$

I'm writing a priority queue that stores a bunch of data with a value attached to the data, with \$O(1)\$ access to the data with the smallest value attached to it. I also need to be able to update said value any time I want (the setValue operation), which is a bit awkward to do with a standard binary heap.

So I made two classes, pQueue and pQueueNode. pQueue holds a vector of pointers to pQueueNode that works like a binary heap. All operations related to the values of each pQueueNode go through the pQueue, including construction and destruction.

Adding a new pQueueNode to the pQueue returns a pQueueNode* which you can then use to call the setValue method.

This is the first time ever that I'm writing C++ code that other people might actually read/use, so I'm trying to make sure the interface is airtight and best practices are being followed. I would love to get some feedback on that. Also, if you guys know of better implementation strategies for what I'm trying to do, I would greatly appreciate it.

#include <iostream>
#include <vector>

template <typename D, typename V> // D is the data, V is the priority value
class pQueue;

template<typename D, typename V>
class pQueueNode;

template <typename D, typename V>
class pQueueNode {
public:
    D data;
    V getValue() {return value; };
    void setValue(V newValue) { pQueuePointer->changeValue(rank, newValue); }

    pQueueNode(const pQueueNode&) = delete;
    pQueueNode& operator=(const pQueueNode&) = delete;
private:
    pQueueNode(D data_, V value_, pQueue<V,D>* pQueuePointer_): //private constructor prevents clients from creating pQueueNode objects
        value(value_),
        data(data_),
        pQueuePointer(pQueuePointer_)
    {}
    void operator delete (void *p) { //only pQueue can use delete on pQueueNode pointers
        free(p);
    }
    ~pQueueNode() {};

    pQueue<V, D>* pQueuePointer;
    V value;
    int rank;
    friend class pQueue<D,V>;
};

template <typename D, typename V>
class pQueue {
public:
    pQueueNode<D,V>* add(const D& data, V value);
    pQueueNode<D,V>* lowest();
    void removeLowest();

    int size() { return binaryHeap.size(); };

    ~pQueue();
private:
    std::vector<pQueueNode<D, V>*> binaryHeap;

    void changeValue(int rank, V newValue);

    void goDown(int rank);
    void goUp(int rank);
    void swap(int rank1, int rank2);

    int parent(int i) { return (i + 1) / 2 - 1; };
    int child1(int i) { return 2 * (i + 1) - 1; }
    int child2(int i) { return 2 * (i + 1); }

    friend class pQueueNode<D, V>;
};

template <typename D, typename V>
void pQueue<D,V>::swap(int rank1, int rank2) {
    pQueueNode<D,V>* pqn = binaryHeap[rank1];
    binaryHeap[rank1] = binaryHeap[rank2];
    binaryHeap[rank2] = pqn;
    binaryHeap[rank1]->rank = rank2;
    binaryHeap[rank2]->rank = rank1;
}

template <typename D, typename V>
pQueueNode<D,V>* pQueue<D,V>::add(const D& data, V value) {
    pQueueNode<D,V>* pqn = new pQueueNode<D,V>(data, value, this);
    int currentRank = binaryHeap.size();
    pqn->rank = currentRank;
    binaryHeap.push_back(pqn);
    goUp(currentRank);

    return pqn;
}

template <typename D, typename V>
pQueueNode<D,V>* pQueue<D,V>::lowest() {
    return binaryHeap[0];
}

template <typename D, typename V>
void pQueue<D,V>::removeLowest() {
    //assert(binaryHeap.size() > 0 && "Priority queue is already empty" );

    delete binaryHeap[0];
    swap(0, binaryHeap.size()-1);
    binaryHeap.pop_back(); //biggest value is now at the top
    if (binaryHeap.size() > 0) {
        goDown(0);
    }


}

template <typename D, typename V>
void pQueue<D,V>::changeValue(int rank, V newValue) {
    V previousValue = binaryHeap[rank]->value;
    binaryHeap[rank]->value = newValue;
    if (newValue > previousValue) {
        goDown(rank);
    }
    else {
        goUp(rank);
    }

}

template <typename D, typename V>
void pQueue<D,V>::goDown(int rank) {
    bool rightPlace = 0;
    int currentRank = rank;
    while (!rightPlace) {
        //std::cout << "currentRank: " << currentRank << std::endl;

        V lowestValue = binaryHeap[currentRank]->value;
        int rankLowestValue = currentRank;

        int rankChild1 = child1(currentRank);
        if (rankChild1 < binaryHeap.size()) {
            rightPlace = 1;
            if (binaryHeap[rankChild1]->value < lowestValue) {
                rightPlace = 0;
                lowestValue = binaryHeap[rankChild1]->value;
                rankLowestValue = rankChild1;
            }

            int rankChild2 = child2(currentRank);
            if (rankChild2 < binaryHeap.size()) {
                if (binaryHeap[rankChild2]->value < lowestValue) {
                    rightPlace = 0;
                    rankLowestValue = rankChild2;
                }
            }
            swap(rankLowestValue, currentRank);
            currentRank = rankLowestValue;

        }
        else {
            rightPlace = 1;

        }
    }

}

template <typename D, typename V>
void pQueue<D,V>::goUp(int rank) {
    int currentRank = rank;
    bool rightPlace = 0;
    while (currentRank != 0 && !rightPlace) {
        int parentRank = parent(currentRank);
        if (binaryHeap[currentRank]->value < binaryHeap[parentRank]->value) {
            swap(parentRank, currentRank);
            currentRank = parentRank;
        }
        else {
            rightPlace = 1;
        }
    }
}

template <typename D, typename V>
pQueue<D, V>::~pQueue(){
    for (int i = 0; i < binaryHeap.size(); i++) {
        delete binaryHeap[i];
    }
}

Usage example:

int main() {

    pQueue<int, int> pQ;

    pQueueNode<int, int>* pqn = pQ.add(0,1);
    pQ.add(0, 5);
    pQ.add(0, 3);
    pQ.add(0, 6);
    pQ.add(0, 8);
    pQ.add(0, 13);
    pQ.add(0, 15);
    pQ.add(0, 1);
    pQ.add(0, 14);
    pQ.add(0, 4);
    pQ.add(0, 7);
    pQ.add(0, 10);

    pqn->setValue(12);


    for (int remove = 0; remove < 12; remove++) {
        pQ.removeLowest();
    }
return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Try to implement what the standard priority_queue interface provides? \$\endgroup\$ – GadaaDhaariAvi Feb 10 '17 at 5:22
  • \$\begingroup\$ Correct me if I'm wrong but I don't think std::priority_queue allows users to change the priority values of elements inside the queue once you add them (the setValue operation in my class), which is a requirement for what I'm trying to do and makes everything a bit more complicated. \$\endgroup\$ – Rch Feb 10 '17 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.