STL的优先队列中为何没有删除某个任意元素的方法呢?
STL中的优先队列,只有删除队首元素的方法,并没有删除队中某个元素的方法。
我知道,队列的定义就是只允许操作队首队尾。
但是,优先队列不就是一个堆的实现吗?
常见的堆的实现(比如算法第四版)中同样也是只有删除最值元素的方法。没有删除任意元素的方法。
请问,实现删除任意元素的方法有什么弊端吗?
目前我有一个需求:我需要快速的得到一个数组的最值,但是需要动态的维护这个数组(可能会插入一个元素,或者删除某个元素),思来想去觉得堆再合适不过了。然而发现我能找到的堆实现都没有删除任意元素的方法,这让我有些困惑。
堆只能保证堆顶的根节点元素是最值,根节点的左右子树之间是不能保证有序的。如果要实现删除任意元素的方法,首先要查找到该元素,而查找的时间复杂度是
O(N)
的,效率太低,因此没有实现。你的需求用一个平衡树可以满足,比如C++ STL里面的
set
.