CODEWITHSUNDEEP
data-structuresheap
iVeryBadGuy
iVeryBadGuy

Reputation: 33

Which priority queue is faster in practice?

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?

Upvotes: 3

Views: 2060

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134005

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.

Upvotes: 3

Related Questions