Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"?

Question

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?

Answer 1

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.

Answer 2

The naming of the method is probably deliberate in some textbooks (e.g. CLRS) because:

1. The logic for "floating down" or "bubbling up" a key in a binary heap is straightforward if you know which direction (up/down) you are going. E.g. "bubbling up" a key is simply a recursive call on the node parents, vs floating down where you need to compare with each child, before proceeding recursively.
2. Many algorithms that use max / min heaps require you to only increase or decrease keys, so it's enough to provide the corresponding "floating down" or "bubbling up" method.

Note that if you wanted to implement a generic "set key" method you could simply combine these two routines to decide which direction to go based on whether or not you need to bubble up or float down the key.

To add to what Hendrick said, it's worth noting that even for e.g. Dijkstra's or Prim's algorithms where technically speaking a decrease key operation is enough, using a binary heap does not necessarily require you to keep track of the position of each key.

In these algorithms a given key is extracted from the heap only once. For example, in Dijkstra a graph node is only added once to the shortest paths tree, and in Prim's algorithm, an edge may only be added once to the minimum spanning tree.

Thus, instead of keeping track of key positions (or searching for them when the algorithm needs to decrease them), on can simply insert the new (in this case lower) value for the key in the heap (leading to duplicates in the heap), and then, once you extracted the "key" from the heap (technically satellite data since the key is not what you are greedily consuming), you can ignore all of its subsequent extractions (e.g. using a set with $O(1)$).

Such set and key duplicates in the heap would obviously cost you $O(n)$ in space complexity, but you could think of the combined solution as a "decrease key" method that requires no knowledge or tracking of positions in the heap.