A min-heap with better than O(logn) increase key?

Question

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.

Answer 1

Binary heaps are too unflexible to beat logarithmic complexity. Binomial heaps just allow a more efficient join-operation.

Other heaps with good decrease-key performance are pairing heaps and 2-3 heaps

Answer 2

Binomial heaps take o(log n) time for decrease key operations! Isn't this slower than fibonacci heaps?

Answer 3

Actually, with Fibbonacci heaps, the increase key operation is the same as decrease key. IMHO, it's only a tradition to name the operation "decrease key", because it's used in some algorithms. But the Fibbonacci heap implementation allows both.