STL中的优先队列,只有删除队首元素的方法,并没有删除队中某个元素的方法。
我知道,队列的定义就是只允许操作队首队尾。
但是,优先队列不就是一个堆的实现吗?
常见的堆的实现(比如算法第四版)中同样也是只有删除最值元素的方法。没有删除任意元素的方法。
请问,实现删除任意元素的方法有什么弊端吗?
目前我有一个需求:我需要快速的得到一个数组的最值,但是需要动态的维护这个数组(可能会插入一个元素,或者删除某个元素),思来想去觉得堆再合适不过了。然而发现我能找到的堆实现都没有删除任意元素的方法,这让我有些困惑。
The heap can only ensure that the root node element at the top of the heap is the most valuable, and the left and right subtrees of the root node cannot be guaranteed to be ordered. If you want to implement the method of deleting any element, you must first find the element, and the time complexity of the search is
O(N)
, which is too inefficient, so it has not been implemented.Your needs can be met with a balanced tree, such as
in C++ STLset
.Since it is a priority queue, it is ordered, and the heap used to implement it is a special data structure. Regardless of the cost of searching, if you delete a certain element, the nature of the heap itself may be destroyed. This It’s not worth the gain. .
You can use
set
in stl to implement most of the red-black tree implementations. Searching, inserting, and deleting are all very efficient