Skip to main content
Computer Science

Return to Question

remove a reference, minor fixes
Source Link
Alexey
Alexey
  • 251
  • 1
  • 13

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 bulk_insert (see, for example, Figure 3 in Towards ultimate binary heaps)some kind of optimised "bulk insertion" method.

Another possible tweak is to check if the inserted element to be inserted has a higher priority than all the otherswaiting ones, and if so, to store it in a second stack, which is to be used for the nextsubsequent extraction. If the priority of an insertedthe element to be inserted is not the highest but higher thatthan the prioritypriorities of all the elements in the proper priority queue (in the heap), then the elements from the second stack can replace the elements at the start of the queue (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?

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 bulk_insert (see, for example, Figure 3 in Towards ultimate binary heaps).

Another possible tweak is to check if the inserted element has a higher priority than all the others, and if so, to store in a second stack, which is to be used for the next extraction. If the priority of an inserted element is not the highest but higher that the priority of all the elements in the proper priority queue (in the heap), then the elements from the second stack can replace the elements at the start of the queue (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?

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?

Source Link
Alexey
Alexey
  • 251
  • 1
  • 13

Priority queue with a buffer for delayed insertion and other tweaks

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 bulk_insert (see, for example, Figure 3 in Towards ultimate binary heaps).

Another possible tweak is to check if the inserted element has a higher priority than all the others, and if so, to store in a second stack, which is to be used for the next extraction. If the priority of an inserted element is not the highest but higher that the priority of all the elements in the proper priority queue (in the heap), then the elements from the second stack can replace the elements at the start of the queue (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?