Return to Answer

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 tracking of positions in the heap.

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.

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 simple 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, and you could think of the combined solution as a "decrease key" method that requires no knowledge of positions in the heap.

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 tracking of positions in the heap.

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

1. The logic for "floating down" or "bubbling up" a key in a binary heap is simple 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 "float down" or "bubble 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, if you are willing to e.g. incur extra cost in space complexity.

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 the key has actually been extracted from the key, you can ignore subsequent extractions of the same key (e.g. using a set with $O(1)$). Such set and key duplicates in the heap would obviously still cost you $O(n)$ in space complexity, and you could think of the combined solution as a "decrease key" method that requires no knowledge of positions in the heap.

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 simple 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, and you could think of the combined solution as a "decrease key" method that requires no knowledge of positions in the heap.