A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms
Orr Tamir, Adam Morrison, Noam Rinetzky · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
Existing concurrent priority queues do not allow to update the priority of an element after its insertion. As a result, algorithms that need this functionality, such as Dijkstra's single source shortest path algorithm, resort to cumbersome and inefficient workarounds. We report on a heap-based concurrent priority queue which allows to change the priority of an element after its insertion. We show that the enriched interface allows to express Dijkstra's algorithm in a more natural way, and that its implementation, using our concurrent priority queue, outperform existing algorithms.