When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to Wikipedia and other sources) a min priority queue has "decrease-key" and a max priority queue has "increase-key"? why not have both "set-key" and if you decrease it or increase it, do what you should do to keep the heap property invariant?

I mean what if I call decrease-key on a min heap and give a bigger value? Will it throw an exception? Why not just call it "set-key" and handle any kind of value?


Good question. One of the important applications of the data structure PriorityQueue is in Dijkstra's algorithm. Each node gets a distance from the initial node, which is updated when shorter paths are discovered. Hence updates only change the key in one direction.

The problem in the implementation of DecreaseKey is not that it is only decreasing (rather than updating the value). For a binary heap there are quite efficient methods both for increasing and decreasing. They both swap nodes with other nodes along a path in the tree (either upwards or downwards). The problem is actually knowing where to find the key. You cannot efficiently search for it, so a separate "index" has to be kept. When an update is done along a path, not only the decreased key is changed in the indax, but also the other keys along the path.

For abstract data structures we want to specify only the operations that are important in a particular context. So we have DecreaseKey only, given the Dijkstra motivation. Although for binary heaps extending the operations might be elementary, this might not be the case for other implementations of the PriorityQueue, like Leftist Heaps, Fibonacci Heaps, or Brodal Heaps.

What any particular implementation will do when the new value is in the wrong direction is up to that implementation.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.