I was thinking of ways to optimise a (heap-based) priority queue in certain scenarios, like in best-first path search algorithms (Dijkstra, A*, etc.).

One possible optimisation is to delay insertions until the next extraction. The inserted elements can be kept in a buffer (a simple stack) until the next extractions, and then inserted with some kind of optimised "bulk insertion" method.

Another possible tweak is to check if the element to be inserted has a higher priority than all the waiting ones, and if so, to store it in a second stack, which is to be used for the subsequent extraction. If the priority of the element to be inserted is not the highest but higher than the priorities of all the elements in the heap, then the elements from the second stack can replace the elements at the top of the heap, while the replaced elements are moved to the buffer for delayed insertion. This tweak however would add a noticeable overhead, so it is not clear if it would be an optimisation in any scenario.

Has such or similar modifications of (heap-based) priority queues been studied or used in practice?

  • $\begingroup$ I've discovered a bunch of papers on the topic of optimising binary heaps, most by Stefan Edelkamp, Amr Elmasry, and Jyrki Katajainen. Need to take a look. $\endgroup$ – Alexey May 1 '19 at 14:03

There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg & Silverstein.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.