c++ - Decrease key 的含义

Question

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

Answer 1

If you are asking about priority_queue in STL, I think there is no decrease-key method until c++11.
I also encountered this problem when doing the prim algorithm. If you look at the source code of priority_queue in libc++, you will find that it is just an adapter, which is generated using make_heap on vector. But you can follow the same method and build a heap on vector to get the container you want. In addition, you can also use the red-black tree in set, which has the same time complexity as priority_queue, but the constant value is larger.