我正在做一个路径规划程序，其中我有一个优先级队列**'U'**：

using HeapKey = pair<float, float>;
vector<pair<HeapKey, unsigned int>> U;

我将优先级队列作为二进制最小堆进行排序和维护（也就是队列中最便宜的第一个节点）使用greater作为比较函数来获得最小堆（可能不重要）。当程序执行并规划路径时，它使用push_back向'U'添加节点（），然后是push_heap（），以使该节点进入正确的顺序，并且那里的一切工作正常...
然而，我使用的算法有时会调用新值更新**'U'中已经存在的节点，方法是将其从'U'中删除（我用find_if（）找到它，用erase删除它（），如果这很重要的话），然后调用函数重新插入（再次执行push_back（），然后执行push_heap（）），这样节点就有了更新后的值。
这对我来说是一个意想不到的问题。我不是这方面的Maven，但就我所能想到的，因为节点被移到了'U'内部的某个地方，所以它会打乱堆的顺序。我可以通过使用make_heap来让程序工作然而，这个解决方案带来了另一个问题，因为程序现在需要更多的时间来完成，时间越长，堆中的my map/节点越大，大概是因为每次更新节点时，**make_heap（）**都要重新组织/迭代整个堆，从而减慢了整体规划。
我的截止日期已经很近了，我不希望改变我的程序并得到新的结果，除非有人有一个简单的，我可以快速实现的简单解决方案。我在这里主要是为了学习，也许看看是否有一些建议可以传递，关于如何解决这个问题，有效地维护一个堆/优先级队列时，你不只是删除第一个或最后一个元素，但元素可能在中间。减少计划所需的时间是我唯一缺少的。
谢谢你。

• • 尝试最小可重复示例，而不进入实际算法，例如：**

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using Cost = float;
using HeapKey = pair<Cost, Cost>;
pair<Cost, Cost> PAIR1;
vector<pair<HeapKey, unsigned int>> U;
using KeyCompare = std::greater<std::pair<HeapKey, unsigned int>>;
int in_U[20];

ostream& operator<<(ostream& os, pair<Cost, Cost> const& p) {
  return os << "<" << p.first << ", " << p.second << ">";
}

bool has_neightbor(unsigned int id) {
    if ( (in_U[id+1]) && (in_U[id-1])) {
        return true;
    }
    return false;
}

void insert(unsigned int id, HeapKey k) {
    U.push_back({ k, id });
    push_heap(U.begin(), U.end(), KeyCompare());
    in_U[id]++;
}

void update(unsigned int id) {
    Cost x;
    Cost y;
    if (id != 21) { //lets say 21 is the goal
        x = U[id].first.first;
        y = U[id].first.second;
    }
    if (in_U[id]) {
        auto it = find_if(U.begin(), U.end(), [=](auto p) { return p.second == id; });
        U.erase(it);
        make_heap(U.begin(), U.end(), KeyCompare());
        in_U[id]--;
    }
    int r1 = rand() % 10 + 1;
    int r2 = rand() % 10 + 1;
    if (x != y) {
      insert(id, {x + r1, y + r2});
    }
}
 
int main() {

    U.push_back({ {8, 2}, 1 });
    in_U[1]++;
    U.push_back({ {5, 1}, 2 });
    in_U[2]++;
    U.push_back({ {6, 1}, 3 });
    in_U[3]++;
    U.push_back({ {6, 5}, 4 });
    in_U[4]++;
    U.push_back({ {2, 3}, 5 });
    in_U[5]++;
    U.push_back({ {2, 9}, 6 });
    in_U[6]++;
    U.push_back({ {9, 2}, 7 });
    in_U[7]++;
    U.push_back({ {4, 7}, 8 });
    in_U[8]++;
    U.push_back({ {11, 4}, 9 });
    in_U[9]++;
    U.push_back({ {2, 2}, 10 });
    in_U[10]++;
    U.push_back({ {1, 2}, 11 });
    in_U[11]++;
    U.push_back({ {7, 2}, 12 });
    in_U[12]++;
    make_heap(U.begin(), U.end(), KeyCompare());
    PAIR1.first = 14;
    PAIR1.second = 6;

    while (U.front().first < PAIR1) {

        cout << "Is_heap?: " << is_heap(U.begin(), U.end(), KeyCompare()) << endl;

        cout << "U: ";
        for (auto p : U) {
            cout << p.second << p.first << " - ";
        }
        cout << endl;

        auto uid = U.front().second;
        pop_heap(U.begin(), U.end(), KeyCompare());
        U.pop_back();

        if (has_neightbor(uid)) {
            update(uid - 1);
            update(uid + 1);
        }
    }
    //getchar();
}