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

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

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

ringa_lee
ringa_lee

ringa_lee

全部回覆(2)
小葫芦

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

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

洪涛

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

熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板