Soft heaps are pretty neat. They are like normal min-heaps, but support all operations you care about in O(1) instead of O(log n) time. The catch is that they are allowed to make a configurable proportion of errors.

They are basically only useful in theory, not in practice. They allow construction of some asymptotically optimal algorithms.