Consider a min-heap implementation with heap-like trees, but with bounded-ary (say quake heap --- they use the "tournament" idea to reduce the branching down to at most 2, as opposed to other heaps such as Fibonacci heaps, 2-3 heaps, and Brodal queues). To implement an increase-key on a particular node x, we cut-off its O(1) children instead. So this is equivalent to performing O(1) decrease-key operations, which takes O(1) amortized time.