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

StackExchange Computer Science Q#880, answer score: 10