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

Question

我在这个问题上发现了一些类似的问题，但我想再问一遍，以便得到一个更明确的答案。我正在编写一个图匹配算法，其中图上的每个节点分配给一个优先级集，取决于其邻居的匹配。细节其实并不重要，但我使用了std::priority_queue以便首先匹配最高优先级的节点。这里有一个棘手的问题：每次引入一个新的匹配，匹配节点的邻居的优先级将被更新。

我的问题自然是，如何更新新匹配的顺序？我能强制执行吗？或者是否有任何其他数据结构（例如max heap）可以用于此目的？请注意，将新元素推入队列对我来说不是一个有效的解决方案。下面是我正在使用的代码片段（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

利用我收到的关于这个问题的评论，我决定自己来回答这个问题。我发现有三种可能的方法可以克服这个问题：

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