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

Problem Detail: 

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?

Asked By : Joe

Answered By : jbapple

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; } 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/880