如何高效维护支持中间元素删除的堆？路径规划场景优化

问题描述 #

开发路径规划程序时，使用vector模拟最小堆作为优先级队列U：

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

通过greater比较函数维护为最小堆，插入节点用push_back()+push_heap()，这部分运行正常。

但算法需要更新堆中已存在节点的数值：目前通过find_if()查找节点，erase()移除后调用make_heap()重建堆结构。该方式导致**O(n)**时间复杂度，地图规模越大耗时越久，且无法进行大规模代码修改，需要快速高效的改进方案。

快速解决方案：延迟删除（Lazy Deletion） #

这是改动最小、效率提升最明显的方案，核心思路是不立即删除旧的无效节点，仅标记最新节点值，在弹出堆顶时过滤无效节点，避免每次更新都重构整个堆。

实现步骤 #

1. 新增节点最新值映射表：用数组或哈希表存储每个节点ID对应的最新HeapKey，用于判断堆中节点是否有效。
2. 修改插入逻辑：插入节点时同步更新映射表的最新值。
3. 简化更新逻辑：更新节点时直接写入新值到映射表，然后将新节点插入堆，无需删除旧节点。
4. 堆顶过滤无效节点：每次取堆顶前，检查堆顶节点的HeapKey是否与映射表中的最新值一致，不一致则弹出该无效节点，直到堆顶为有效节点。

修改后的代码示例 #

新增映射表

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>>;
HeapKey current_keys[20]; // 存储每个节点的最新Key，根据实际节点ID范围调整

修改插入函数

void insert(unsigned int id, HeapKey k) {
    U.push_back({ k, id });
    push_heap(U.begin(), U.end(), KeyCompare());
    current_keys[id] = k; // 同步更新最新Key
}

修改更新函数

void update(unsigned int id) {
    Cost x, y;
    if (id != 21) { // 21为目标节点
        x = current_keys[id].first;
        y = current_keys[id].second;
    }
    int r1 = rand() % 10 + 1;
    int r2 = rand() % 10 + 1;
    HeapKey new_k = {x + r1, y + r2};
    current_keys[id] = new_k; // 更新最新Key
    insert(id, new_k); // 直接插入新节点，无需删除旧节点
}

修改主循环的堆顶处理逻辑

int main() {
    // 初始化节点时同步更新current_keys
    U.push_back({ {8, 2}, 1 });
    current_keys[1] = {8, 2};
    U.push_back({ {5, 1}, 2 });
    current_keys[2] = {5, 1};
    U.push_back({ {6, 1}, 3 });
    current_keys[3] = {6, 1};
    U.push_back({ {6, 5}, 4 });
    current_keys[4] = {6, 5};
    U.push_back({ {2, 3}, 5 });
    current_keys[5] = {2, 3};
    U.push_back({ {2, 9}, 6 });
    current_keys[6] = {2, 9};
    U.push_back({ {9, 2}, 7 });
    current_keys[7] = {9, 2};
    U.push_back({ {4, 7}, 8 });
    current_keys[8] = {4, 7};
    U.push_back({ {11, 4}, 9 });
    current_keys[9] = {11, 4};
    U.push_back({ {2, 2}, 10 });
    current_keys[10] = {2, 2};
    U.push_back({ {1, 2}, 11 });
    current_keys[11] = {1, 2};
    U.push_back({ {7, 2}, 12 });
    current_keys[12] = {7, 2};
    
    make_heap(U.begin(), U.end(), KeyCompare());
    PAIR1.first = 14;
    PAIR1.second = 6;

    while (!U.empty() && U.front().first < PAIR1) {
        // 过滤无效节点：堆顶节点Key与最新值不一致则弹出
        while (!U.empty() && U.front().first != current_keys[U.front().second]) {
            pop_heap(U.begin(), U.end(), KeyCompare());
            U.pop_back();
        }
        if (U.empty()) break;

        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 ( (uid+1 <=12 && current_keys[uid+1].first != 0) && (uid-1 >=1 && current_keys[uid-1].first !=0)) {
            update(uid - 1);
            update(uid + 1);
        }
    }
}

方案优势 #

• 代码改动极小：仅需新增映射表，修改插入、更新和堆顶过滤逻辑，无需重构原有堆操作。
• 时间复杂度优化：每次更新和插入均为O(logn)，堆顶过滤的无效节点弹出操作也为O(logn)，整体效率大幅提升。
• 无额外复杂维护：无需跟踪节点在堆中的位置，避免了索引维护的繁琐逻辑。

备选优化：删除后局部调整堆结构 #

若不想积累无效节点，可优化删除后的堆重建步骤，用局部调整替代make_heap()的全堆重构：

// 替换原erase和make_heap逻辑
auto it = find_if(U.begin(), U.end(), [=](auto p) { return p.second == id; });
if (it != U.end()) {
    size_t pos = it - U.begin();
    // 将最后一个元素移到删除位置
    U[pos] = U.back();
    U.pop_back();
    // 根据替换元素的大小调整堆结构
    if (pos < U.size()) {
        // 先尝试向上调整
        push_heap(U.begin(), U.begin() + pos + 1, KeyCompare());
        // 再尝试向下调整
        adjust_heap(U.begin(), U.end(), U.begin() + pos, KeyCompare());
    }
    // 原in_U逻辑可保留
}

该方案将删除后的堆重建从O(n)降至O(logn)，但仍需find_if()的**O(n)**查找时间，适合对内存占用敏感的场景。

内容的提问来源于stack exchange，提问作者OverDemon