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?
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&lt;T&gt;
fast_sort(const vector&lt;T&gt; &amp; in) {
  vector&lt;T&gt; ans;
  pq&lt;T&gt; 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;
}