Before revision: In the paper "Fast Fibonacci heaps with worst case extensions"  we have described heaps with both Meld, DecreaseKey and DecreaseKey interfaces, allowing operations with guaranted worst case assymptotically optimal times.
After revision: In the paper "Fast Fibonacci heaps with worst case extensions" we have described heaps with both Meld, DecreaseKey and DecreaseKey interfaces, allowing operations with guaranteed worst-case asymptotically optimal times.