# Priority queue with both decrease-key and increase-key operations

A Fibonnaci Heap supports the following operations:

• insert(key, data) : adds a new element to the data structure
• find-min() : returns a pointer to the element with minimum key
• delete-min() : removes the element with minimum key
• delete(node) : deletes the element pointed to by node
• decrease-key(node) : decreases the key of the element pointed to by node

All non-delete operations are $O(1)$ (amortized) time, and the delete operations are $O(\log n)$ amortized time.

Are there any implementations of a priority queue which also supportincrease-key(node) in $O(1)$ (amortized) time?

• @Raphael if you increase the key of the minimum element so that it is now the largest key, it's not immediately obvious (at least to me) that you don't have to do a super-constant amount of rebalancing.
– Joe
Mar 29, 2012 at 22:35

Assume you have a priority queue that has $O(1)$ find-min, increase-key, and insert. Then the following is a sorting algorithm that takes $O(n)$ time:

vector<T>
fast_sort(const vector<T> & in) {
vector<T> ans;
pq<T> out;
for (auto x : in) {
out.insert(x);
}
for(auto x : in) {
ans.push_back(*out.find_min());
out.increase_key(out.find_min(), infinity);
}
return ans;
}

• I had assumed that (de|in)crease-key only did plus or minus one.
– Raphael
Mar 30, 2012 at 7:13
• And does there exist a DS that allows increase-key operation in constant time but decrease in logarithmic (or more)? (For a min-heap) Jul 2, 2018 at 0:23
• @GonzaloSolera: The impossibility proof in this answer doesn't care about decrease-key; O(1) find-min, increase-key, and insert are already a problem together (and the proof's dependence on insert isn't really necessary; O(n) heapify is enough, or we can probably reuse the same heap over multiple sorts to prove it violates comparison sort bounds regardless of the cost of heapify or insert). Jul 2, 2018 at 17:23
• Okay sorry, I missed read that. Thanks for your comment! Jul 3, 2018 at 9:22