2025/08/18 by Fatourou, Panagiota, Ruppert, Eric, Xiradakis, Ioannis
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.13399
This work provides the first concurrent implementation specifically designed for a double-ended priority queue (DEPQ). We do this by describing a general way to add an ExtractMax operation to any concurrent priority queue that already supports Insert and ExtractMin operations. The construction uses two linearizable single-consumer priority queues to build a linearizable dual-consumer DEPQ (only one process can perform Extract operations at each end). This construction preserves lock-freedom. We then describe how to use a lock-based combining scheme to allow multiple consumers at each end of the DEPQ. To illustrate the technique, we apply it to a list-based priority queue.