首页 > STL的优先队列中为何没有删除某个任意元素的方法呢?

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

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

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


既然是优先队列那么就是有序的,而且用来实现它的堆是一个特殊的数据结构,抛去查找的消耗,你删除了某一个元素,堆本身的性质可能就破坏了,这个是得不偿失的。。
这个你可以用stl中的set,实现大部分采用的红黑树实现,查找、插入、删除都非常高效


堆只能保证堆顶的根节点元素是最值,根节点的左右子树之间是不能保证有序的。如果要实现删除任意元素的方法,首先要查找到该元素,而查找的时间复杂度是O(N)的,效率太低,因此没有实现。

你的需求用一个平衡树可以满足,比如C++ STL里面的set.

【热门文章】
【热门文章】