2026-07-26T02:54:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6606 2024-03-06T10:36:49Z ddc:004 open_access

A Heap-Based Concurrent Priority Queue with Mutable Priorities for Faster Parallel Algorithms Tamir, Orr Morrison, Adam Rinetzky, Noam priority queues concurrent data structures Dijkstra's single-source shortest path algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Orr Tamir and Adam Morrison and Noam Rinetzky 2016 Is Part Of LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2015.15 urn:nbn:de:0030-drops-66068 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.15 eng https://creativecommons.org/licenses/by/3.0/legalcode