Which priority queue is faster in practice?

Question

Most used operation: FindMin. Less commonly: Insert and ExtractMin. Rarely: DeleteNode. Very rare: Merge.

Which of the following priority queues is faster in practical terms, under the listed conditions?

• Naive implementation based on sorted doubly linked list
• Simple heap
• Leftist heap
• Binomial heap
• Fibonacci heap
• 2-3 heap
• Pairing heap
• Thin heap
• Thick heap
• Skew Binomial Heap
• Brodal-Okasaki queue

Answer 1

My experience, based on work I did more than five years ago, is that a 3-heap outperforms a binary heap in the general case. Skip list heaps and pairing heaps slightly outperform a 3-heap, but at a higher memory cost. All three of the above outperformed Fibonacci heap.

Brodal queue is theoretically the most efficient. But, as Brodal himself said, they are "quite complicated" and "[not] applicable in practice." https://en.wikipedia.org/wiki/Brodal_queue

A lot of people talk about Fibonacci heap efficiency, and asymptotic analysis says that it should outperform other types of heaps. Empirical data tends not to bear that out. There are definite disadvantages of Fibonacci heap, as described in https://en.wikipedia.org/wiki/Fibonacci_heap#Worst_case.

If you're looking to implement a heap, I'd suggest starting with a binary heap. Or a 3-heap, which is a simple optimization. My next step, if I needed more performance, would be the Pairing Heap. It's easy to implement and quite efficient.

Beyond that, I don't have any advice. The performance numbers I've seen on the other types of heaps don't show a clear winner.