I'm using a priority queue that initially bases the priority of its elements on a heuristic. As elements are dequeued the heuristic is updated and elements currently in the queue may have their keys increased.

I know there are heaps (Fibonacci heaps specifically) that have amortized O(1) decrease key operations, but are there any heap structures that have similar bounds on the increase key operations?

For my application this is far from a performance issue (a binary heap works fine) it's really just about academic curiosity.

Edit: to clarify, I'm looking for a data structure that has a faster than O(logn) time for the **increase key** operation, not decrease key. My application never decreases the key as the heuristic over-estimates the priority.