Which priority queue is faster?

Question

Data Structures

Which priority queue is faster?
I choose from:

• Naive implementation based on a sorted doubly linked list
  
• simple heap
  
• fibonacci heap
  
• Pairing heap
  
• thin pile
  
• fat pile
  
• Skewed binomial heap
  
• Brodal-Okasaki queue
  

I tried to find comparative charts on the Internet, but no matter how much I tormented Google, I did not get an answer.
Planned nature of the load:

• Number of elements in the queue: up to 2^16-1 (< 65536).
  
• The size of the nodes is 64 bytes, of which 16 bytes are payload and the rest is for the fields of the heap node.
  
• Planned implementation language C/C++ or Assembler. x86-64 architecture.
  
• Required operations: FindMin, Insert, ExtractMin, Merge.
  
• Desirable operations (but not critical): DeleteNode.
  
• Most common operation: FindMin. Less common: Insert and ExtractMin. Rare: DeleteNode. Very rare: Merge.
  

According to the found asymptotic estimates, the thin heap, skew binomial heap, and the Brodal-Okasaki queue look the most attractive. But what about performance in practice?

Answer 1

So everything is simple, take practical implementations, write tests that reflect your "planned nature of the load" and take measurements.

Answer 2

God, how difficult it is. You take and make as many queues as you need priorities. And that's it.

Answer 3

I would do on std::deque. Inserting at the beginning and pulling out from the end works for him in a swoop. Sorting and accessing is slightly slower than std::vector, but faster than all the others. You will have to sort after each addition of a node (if you do it lazily, you can sort before access, but it depends on the load, checking before access can eat up all the benefits of laziness). If the additions are not frequent, then you can do it on the vector, the volume is negligible.