首頁  >  問答  >  主體

c++ - Decrease key 的含义

优先级队列中的decrease-key是什么意思,表示的是什么操作?

大家讲道理大家讲道理2765 天前611

全部回覆(1)我來回復

  • 怪我咯

    怪我咯2017-04-17 13:33:38

    如果你問的是STL中的priority_queue的話,我想到c++11為止是沒有提供decrease-key的方法的。
    我在做prim演算法的時候也遇到過這個問題,如果去查看libc++中priority_queue的源碼,你會發現它只不過是一個適配器,是在vector上使用make_heap生成的。但是你可以用同樣的方法也在vector上建造堆得到你想要的容器。另外你也可以使用set中的紅黑樹,它有和priority_queue一樣的時間複雜度,只是常數值更大一些而已。

    回覆
    0
  • 取消回覆