在元素更改时更新优先队列顺序

Question

我发现了一些关于这个主题的类似问题，但我想再问一次以获得更明确的答案。我正在编写一个图形匹配算法，其中图形上的每个节点根据其邻居的匹配分配给一个优先级集。细节并不是很重要，但我正在使用 std::priority_queue 以便首先匹配最高优先级的节点。棘手的一点是：每次引入新匹配时，匹配节点的邻居的优先级都应更新。

该算法引用自一篇论文，虽然我实现了完全相同的算法，但我无法达到相同的匹配率。我自然怀疑 std::priority_queue 可能不会按照我想要的优先更新进行重新排序，所以我进行了运行一些测试，然后我发现了其他问题问同样的事情：

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

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

我的问题自然是，如何更新新配对的顺序？我可以强制执行吗？或者是否有任何其他数据结构（例如最大堆）可以用于此目的？请注意，将新元素推入队列对我来说不是有效的解决方案。这是我正在使用的代码片段（matchFace() 函数更新元素优先级）：

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

根据收到的关于问题的评论，我决定自己回答。我发现有三种可能的方法可以解决这个问题：

实施您自己的可更新优先级队列或使用外部库。为此，Boost 可能有一些额外的数据结构。我还在这里找到了 Updatable Priority Queue 源代码。
每次收到更新时，使用向量存储值并使用算法库中提供的std::make_heap函数。这是最简单的方法，但速度很慢。
删除并re-insert元素。如果这不是一种有效的方法，请使用地图来存储元素 ID，而不是删除元素，而是在地图上标记元素，这样如果您多次遇到它们，您可以忽略它们。另一种策略是通过添加标志并通过打开标志来标记元素来更改项目。

在元素更改时更新优先队列顺序

Updating Priority Queue Order On Element Changes

c++

priority-queue