c++ - STL的优先队列中为何没有删除某个任意元素的方法呢?
ringa_lee
ringa_lee 2017-04-17 13:32:57
0
2
909

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

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

ringa_lee
ringa_lee

ringa_lee

reply all(2)
小葫芦

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 set.

in C++ STL
洪涛

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

Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template
About us Disclaimer Sitemap
php.cn:Public welfare online PHP training,Help PHP learners grow quickly!