Thanks @carl-aa. I looked at the theory part (not the implementation), looks like an ordinary binary heap.
prioqueue.pdf (wm.edu) pp25 ranks the binary heap among the slowest implementations. It quickly finds the next event in O(log(n)), but then loses out on costly operations to rebalance the tree.
For me it boils down to (anyone disagreeing, please speak up or provide improvements)
- According to the paper, for less than 10 pending events, a simple unsorted list beats them all. My simplistic view: for a binary search in an ordered list, log2(10) is already larger than 3, multiply with search index calculation including division takes about the same effort.
- For less than 1e6 pending events, use a sorted-list based PQ and use binary search for insertion. The last point is regularly neglected in textbooks and you end up with O(n) instead of O(log(n)).
- For more events, use a hash-based PQ as in DataStructures.jl