Increase/Decrease Key Operations
What you'll learn: How to modify an element's priority in a heap and efficiently restore the heap property using the right bubbling direction.
Sometimes you need to change the priority of an element already sitting in your heap—maybe a task becomes more urgent, or a value gets updated. You can't just change the value and walk away; you must restore the heap property by bubbling the modified element in the correct direction.
The Core Idea
When you increase a key in a max-heap (or decrease in a min-heap), you're making it "stronger" relative to its parent—it might now violate the heap order property upward. Solution: bubble it up toward the root, just like insertion.
Conversely, when you decrease a key in a max-heap (or increase in a min-heap), you're making it "weaker"—it might now be out of order with its children. Solution: bubble it down toward the leaves, just like extract.
The Process
- Locate the element (typically you'll have its index)
- Modify its value
- Determine direction:
- If the new value is "better" than before (bigger in max-heap, smaller in min-heap) → bubble up
- If the new value is "worse" → bubble down
- Restore heap property using the appropriate bubbling operation
Analogy
Think of a corporate ladder. If someone gets a promotion (increase priority), they move up past managers who now rank lower. If they get demoted (decrease priority), they move down until they're above only those they outrank.
Complexity
Both operations take O(log n) time in the worst case, since you bubble at most the full height of the heap.
Key Takeaway: Increase/decrease key operations modify an element's priority and restore the heap property by bubbling either up (for "stronger" values) or down (for "weaker" values), both in logarithmic time.