Cache sizes are nowhere near the size where a O(log n) factor is significant. In 1TB ram you can fit at most 2^36 entries (64-bit key to 64-bit value without a

Cache sizes are nowhere near the size where a O(log n) factor is significant. In 1TB ram you can fit at most 2^36 entries (64-bit key to 64-bit value without additional datastructures). A factor of 36 is easily dominated by CPU-cache behaviour. This analysis should not be done with time complexities but with deeper tools. While binary heaps are notorious for bad CPU-cache behaviour, improvements exist. Thus only benchmarks will convince me.