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一样的时间复杂度，只是常数值更大一些而已。