Since 2004, I and my research collaborators have been studying the performance of different priority queues for different sets of operations to be supported. At the theoretical level, we have measured the goodness in terms of the comparison complexity of different operations. As the other optimization criteria, we have considered how to reduce the number of instructions, branch mispredictions, cache misses, and element moves. At the practical level, we have used the actual running time as the key performance indicator. We have done most of our experiments on synthetic operation sequences, but we have also done some application engineering.

In this talk I will briefly survey the theoretical results obtained and I will discuss the methodological issues encountered when performing the practical experiments. As a teaser, consider the following questions:

• What is the best priority queue?
• When to implement a data structure?
• Does a factor of two matter?
• Does the space efficiency matter?
• What is the effect of different hardware phenomena?
• How to measure the practical performance?
• What to do next?

It goes without saying that I do not have complete answers to these questions.

@inproceedings{Kat2014A,
  author = {Jyrki Katajainen},
  title = {Seeking for the best priority queue: {L}essons learnt},
  booktitle = {Algorithm Engineering (Dagstuhl Seminar 13391)},
  series = {Dagstuhl Reports},
  volume = {3},
  number = {9},
  publisher = {Schloss Dagstuhl---Leibniz-Zentrum f\"{u}r Informatik},
  year = {2014},
  pages = {74--75},
}