arXiv preprint ·
FastHeapDict: Permanent Slot Indexing for Efficient Decrease-Key Operations in Indexed Priority Queues
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Efficient decrease-key support remains an important practical concern in priority queues used by shortest-path and graph-processing algorithms. Although duplicate-entry heaps avoid explicit decrease-key operations and are simple to implement, they may accumulate many stale entries when tentative priorities are repeatedly improved. This paper presents FastHeapDict, an indexed binary min-heap based on permanent slot indexing. Instead of repeatedly locating keys through hash-table lookups during heap repair, FastHeapDict assigns each key a stable integer slot and stores that slot directly in heap entries. As a result, position updates during sift-up and sift-down operations are performed through integer indexing while preserving the usual indexed-heap interface. We evaluate FastHeapDict in both Python and C++20 using Dijkstra's algorithm as the primary experimental workload. The benchmarks include constructed dense stress graphs, randomized dense graph variants, and comparisons against duplicate-entry heaps and existing priority-queue alternatives. Across the tested Python workloads, FastHeapDict consistently outperforms the duplicate-entry heapq baseline and the tested heapdict and pqdict implementations. In the C++20 implementation, FastHeapDict also achieves strong constant-factor improvements over std::priority_queue duplicates, std::set-based decrease-key, and std::multiset duplicates. These results indicate that permanent slot indexing can provide a compact and effective implementation strategy for indexed priority queues in workloads where priority updates are frequent.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than $1-1/e$
Limits and Constants of OpenAI's Claimed ETH Refutation
Traveling Salesman Problem on Graphs with Proportional Independent Set
Facility Location with Customer Incompatibilities
Multiple Swap Local Search Approximations for Uniform-Cost Capacitated Facility Location with Extensions to Outliers
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.