Priority queue with both decrease-key and increase-key operations
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;
}