c++ - STL的优先队列中为何没有删除某个任意元素的方法呢？

Question

STL中的优先队列，只有删除队首元素的方法，并没有删除队中某个元素的方法。
我知道，队列的定义就是只允许操作队首队尾。
但是，优先队列不就是一个堆的实现吗？
常见的堆的实现（比如算法第四版）中同样也是只有删除最值元素的方法。没有删除任意元素的方法。
请问，实现删除任意元素的方法有什么弊端吗？

目前我有一个需求：我需要快速的得到一个数组的最值，但是需要动态的维护这个数组（可能会插入一个元素，或者删除某个元素），思来想去觉得堆再合适不过了。然而发现我能找到的堆实现都没有删除任意元素的方法，这让我有些困惑。

Answer 1

堆只能保證堆頂的根節點元素是最值，根節點的左右子樹之間是不能保證有序的。如果要實現刪除任意元素的方法，首先要查找到該元素，而查找的時間複雜度是O(N)的，效率太低，因此沒有實現。

你的需求用一個平衡樹可以滿足，例如C++ STL裡面的set.

Answer 2

既然是優先隊列那麼就是有序的，而且用來實現它的堆是一個特殊的資料結構，拋去查找的消耗，你刪除了某一個元素，堆本身的性質可能就破壞了，這個是得不償失的。 。
這個你可以用stl中的set，實現大部分採用的紅黑樹實現，查找、插入、刪除都非常有效率