c++ - Decrease key 的含义

Question

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

Answer 1

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