STL中的优先队列,只有删除队首元素的方法,并没有删除队中某个元素的方法。
我知道,队列的定义就是只允许操作队首队尾。
但是,优先队列不就是一个堆的实现吗?
常见的堆的实现(比如算法第四版)中同样也是只有删除最值元素的方法。没有删除任意元素的方法。
请问,实现删除任意元素的方法有什么弊端吗?
目前我有一个需求:我需要快速的得到一个数组的最值,但是需要动态的维护这个数组(可能会插入一个元素,或者删除某个元素),思来想去觉得堆再合适不过了。然而发现我能找到的堆实现都没有删除任意元素的方法,这让我有些困惑。
高洛峰2017-04-17 13:34:57
堆只能保證堆頂的根節點元素是最值,根節點的左右子樹之間是不能保證有序的。如果要實現刪除任意元素的方法,首先要查找到該元素,而查找的時間複雜度是O(N)
的,效率太低,因此沒有實現。
你的需求用一個平衡樹可以滿足,例如C++ STL裡面的set
.
PHP中文网2017-04-17 13:34:57
既然是優先隊列那麼就是有序的,而且用來實現它的堆是一個特殊的資料結構,拋去查找的消耗,你刪除了某一個元素,堆本身的性質可能就破壞了,這個是得不償失的。 。
這個你可以用stl中的set
,實現大部分採用的紅黑樹實現,查找、插入、刪除都非常有效率