std::priority_queue非队首元素删改最优方案及近年更新问询

标准库更新情况 #

截至C23，std::priority_queue仍未提供原生的非队首元素删除、修改接口，近5年的C标准更新没有针对该场景新增专用接口，你提到的「删除+插入实现修改」的思路仍然是当前的主流实现逻辑。

主流最优实现方案 #

方案1：惰性删除（绝大多数场景首选） #

这是目前工业界使用最广泛的实现方式，不需要改动优先队列本身的结构，额外开销极低：

• 实现逻辑：不直接删除优先队列中的存量元素，额外维护一个哈希计数表，记录所有待删除的元素及对应删除次数。每次调用top()、pop()操作前，先检查队首元素是否属于待删除范围：如果是则弹出队首，同时扣减待删除计数，直到队首为有效元素为止。
• 时间复杂度：删除操作平均O(1)，插入、查询队首、弹出队首仍然保持O(log n)的复杂度。
• 适用场景：元素可哈希、允许少量冗余元素占用内存的场景，覆盖90%以上的业务使用需求。

示例代码：

#include <queue>
#include <unordered_map>

template <typename T, typename Comp = std::less<T>>
class ModifiablePriorityQueue {
private:
    std::priority_queue<T, std::vector<T>, Comp> base_pq;
    std::unordered_map<T, int> pending_delete;

    // 清理队首的待删除元素
    void flush() {
        while (!base_pq.empty() && pending_delete.contains(base_pq.top())) {
            auto curr = base_pq.top();
            pending_delete[curr]--;
            if (pending_delete[curr] == 0) {
                pending_delete.erase(curr);
            }
            base_pq.pop();
        }
    }

public:
    // 插入元素
    void push(const T& val) {
        base_pq.push(val);
    }

    // 标记待删除元素
    void remove(const T& val) {
        pending_delete[val]++;
    }

    // 获取有效队首
    T top() {
        flush();
        return base_pq.top();
    }

    // 弹出有效队首
    void pop() {
        flush();
        base_pq.pop();
    }

    // 判断队列是否为空
    bool empty() {
        flush();
        return base_pq.empty();
    }
};

如果元素不可哈希，也可以把std::unordered_map替换成std::map，仅会把删除操作的复杂度提升到O(log k)，k为待删除元素的种类数，开销仍然很低。

方案2：直接重建队列（仅适合小队列场景） #

如果你的优先队列规模很小（通常元素数小于1000），可以用最简单的遍历删除方式，不需要维护额外结构：

1. 将原优先队列的所有元素弹出存入std::vector
2. 从vector中删除目标元素
3. 用处理后的vector重新构建优先队列

该方案时间复杂度为O(n)，仅适合小队列场景，队列越大性能下降越明显。

替代方案：使用原生堆算法 #

如果你需要对堆结构做更多自定义操作，也可以放弃std::priority_queue封装，直接用std::vector搭配标准库的堆操作算法：std::make_heap、std::push_heap、std::pop_heap。你可以自由遍历vector定位目标元素，删除后调用std::make_heap重排即可，灵活性更高。

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