Updating Priority Queue Order On Element Changes

Question

I have found some similar questions on this subject, but I wanted to ask again in order to get a more clear answer. I am writing a graph matching algorithm, where each node on the graph assigned to a priority set depending on the matching of its neighbours. Details are not really important, but I am using an std::priority_queue in order to match the highest priority nodes first. Here is the tricky point: Each time a new match is introduced, the priority of the neighbours of the matching nodes shall be updated.

This algorithm is referenced from a paper and although I have implemented the exact same algorithm, I couldn't reach the same matching percentage. I naturally suspected that std::priority_queue may not be reordered as I wanted on priority updates, so I have run some tests and then I found out other questions asking the same thing:

How to tell a std::priority_queue to refresh its ordering?

Does changing a priority queue element result in resorting the queue?

My question naturally is, how can I update the order on new matchings? Can I enforce it? Or is there any other data structure (max heap for example) that can serve to this purpose? Note that, pushing new elements into the queue is not a valid solution for me. Here is the code piece I am using (matchFace() function updates the element priorities):

while (priorityQueue.size() != 0) {

    // Take the face at the top of the queue and check if it is already matched
    FaceData* currentFace = priorityQueue.top();

    // Pop the face at the top in any case
    priorityQueue.pop();

    // If the face is not already matched, try to find a matching
    if (!currentFace->matched) {

        // Try to match the face with one of its neighbors, add it to the unmatched faces list if it fails
        int neighborId = matchFace(currentFace);
        if (neighborId == -1) {
            unmatchedFaces.push_back(currentFace);
        } else {
            matchingMap[currentFace->id] = neighborId;
        }
    }
}

Answer 1

Using the comments that I received on the problem, I decided to answer it myself. I found out there are three possible ways to overcome this problem:

• Implement your own updatable priority queue or use external libraries. Boost might have some additional data structures for this purpose. I also found an Updatable Priority Queue source code here.
• Use a vector to store the values and use std::make_heap function provided in the algorithm library each time an update is received. This is the easiest way but it works very slow.
• Remove and re-insert the elements. If this is not a valid approach, use a map to store the element ids and instead of removing the elements, mark the elements on the map so if you encounter them multiple times you can just ignore them. An alternative strategy is to alter the items by adding a flag and marking the elements by turning the flag on.