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?
