SimdQuickHeap: The QuickHeap Reconsidered
Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams · 2026
Read SimdQuickHeap: The QuickHeap Reconsidered by Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-25681.txt.
Introduction
Breitling, Koerkamp, and Williams present SimdQuickHeap, a priority queue built for processors that handle several data items at once. Ordinary binary heaps suffer frequent cache misses and resist such vector instructions. The authors rearrange the QuickHeap layout, placing pivots side by side with elements grouped in buckets between them. The design keeps expected logarithmic cost per operation. It runs faster than the monotone radix heap and the superscalar sample queue in synthetic tests, and fastest on graph benchmarks.
Catalog record
| CREATOR | Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41136 |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.25681
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
SimdQuickHeap: The QuickHeap Reconsidered Johannes Breitling, Ragnar Groot Koerkamp, Marvin Williams Abstract Motivation. Priority queues are data structures that maintain a dynamic collection of elements and allow inserting new elements and removing the smallest element. The most widely known and used priority queue is likely the implicit binary heap, even though it is has frequent cache misses and is hard to optimize using e.g. SIMD instructions. Contributions. We introduce the SimdQuickHeap, a variant of the QuickHeap that was introduced by Navarro and Paredes in 2010. As suggested by the name, the data structure bears some similarity to QuickSort. We modify the data layout of the original QuickHeap to have all pivots adjacent in memory, with elements between consecutive pivots stored in dedicated buckets . This allows efficient SIMD implementations for both partitioning of buckets and scanning the list of pivots to find the bucket to append newly inserted elements to. The SimdQuickHeap has amortized expected complexity O ( log n ) O(\log n) per operation, which improves to O ( 1 W log n ) O(\frac{1}{W}\log n) in non-degenerate cases, where W W is the number of words in a SIMD register. In this case, the I/O-complexity is amortized O ( 1 B ) O(\frac{1}{B}) per push and O ( 1 B log 2 n M ) O(\frac{1}{B}\log_{2}\frac{n}{M}) per pop . Results. In synthetic benchmarks, the SimdQuickHeap is up to twice as fast as the next-best competitor, including the non-comparison radix heap, and needs around 1.5 log 2 n 1.5\log_{2}n comparisons and log 2 n \log_{2}n nanoseconds per pair of push and pop operations. On graph benchmarks with Dijkstra’s shortest path algorithm and Jarnik-Prim’s minimum spanning tree algorithm, the SimdQuickHeap is consistently the fastest. Karlsruhe Institute of Technology, [email protected]://orcid.org/0009-0000-9706-0074 Karlsruhe Institute of Technology, [email protected]://orcid.org/0000-0002-2091-1237 Karlsruhe Institute of Technology, [email protected]://orcid.org/0000-0002-1990-0899 We thank Peter Sanders for discussions related to this work and feedback on a draft of this paper. ccs Theory of computation Data structures design and analysis keywords Heap; SIMD; Priority Queue † † runningauthor: J. Breitling, R. Groot Koerkamp, M. Williams † † copyright: J. Breitling, R. Groot Koerkamp, M. Williams † † supplement: Software: https://github.com/RagnarGrootKoerkamp/quickheap 1 Introduction The Priority Queue (PQ) is a fundamental data structure that manages a collection of elements with associated priorities, allowing the insertion of new elements and the extraction of the element with the highest priority. PQs are central to a wide range of algorithms that rely on dynamically reordering and prioritizing tasks, such as perhaps most famously Dijkstra’s shortest-path algorithm [ 26 ] , but also job scheduling, discrete event simulation, and branch-and-bound searches. As a result, PQs have been studied extensively, resulting in a large variety of priority queue designs (see \cref sec:related). Despite being among the oldest designs, (implicit) binary heaps are probably still the most widely used priority queues in practice 1 1 1 They are available in the standard libraries of many programming languages, including C ++ , Java, C#, Go, Rust, and Python. . There are compelling reasons for their prevalence: they are conceptually simple, easy to implement, and have \Theta(\log_{2}n) worst-case running time with small constants for both insertions and deletions. While many theoretically superior designs have been proposed, most of them are prohibitively complex for practical use, and surprisingly, only a few priority queue designs that are faster in practice have emerged. One such design is the QuickHeap [ 44 ] , introduced in 2010 by Navarro and Paredes. It uses a recursive partitioning scheme reminiscent of quicksort [ 36 ] , hence the name 2 2 2 Although not a heap in the tree-like sense, the layers between the pivots ( \cref fig:heaps) do form a linear tree with unordered sets of elements as nodes. . However, it has received little attention in the literature. \Cref fig:heaps shows a schematic overview of the QuickHeap among other priority queue designs. We show that, due to its partitioning scheme, the QuickHeap lends itself to the SIMD ( single instruction, multiple data ) paradigm much more naturally than binary heaps and most other heaps based on merging trees or streams of elements. SIMD instructions are steadily becoming faster, more efficient, more powerful, and are capable of operating on wider registers. In light of these advancements, we argue that the QuickHeap should be reconsidered. Figure 1: Overview of some heaps. Black dots indicate single elements, and arrows point from larger to smaller elements. Vertical blocks indicate a sorted list of elements, while horizontal blocks indicate an unsorted list of elements. The QuickHeap stores pivots separating the buckets. Contributions. We present SimdQuickHeap , an adaptation of the QuickHeap that achieves significantly improved performance through optimized data layout and SIMD instructions. To our knowledge, it is the first practical SIMD-optimized priority queue implementation. The push and pop operations have an amortized worst-case run time bound of O(\log n) and O(1) , respectively. In most practical cases, the SIMD implementation speeds up both operations by a factor of the SIMD register width W . Like the QuickHeap, the SimdQuickHeap is cache-oblivious with an amortized I/O-complexity of amortized O(\tfrac{1}{B}\log\tfrac{n}{M}) per operation for a main memory of M words and block size B , assuming M=\Omega(\log n) . On synthetic benchmarks, SimdQuickHeap is up to 2\times faster than state-of-the-art implementations including the radix heap and superscalar sample queue [ 57 ] . On real-world instances of Dijkstra’s shortest path algorithm [ 26 ] and Jarník-Prim’s minimum-spanning-tree algorithm [ 38 , 47 ] , it is consistently the fastest method. Notably, while the run time of most tree-based and pointer-based priority queues grows relative to the \Omega(\log_{2}n) lower bound as n increases, SimdQuickHeap’s run time improves, falling below \log_{2}n nanoseconds per push - pop pair. Notation and Definitions. Given a universe of elements \mathcal{U} and a strict weak ordering < on \mathcal{U}\cup\{-\infty,\infty\} , the priority queue (PQ) data structure is a dynamic collection of elements \mathcal{Q} over \mathcal{U} (with duplicates permitted) that supports the following two operations: push(e) Insert an element e\in\mathcal{U} into \mathcal{Q} . pop() Remove and return a minimal element e\in\mathcal{Q} , i.e., no e^{\prime}\in\mathcal{Q} with e^{\prime}<e exists. For convenience, we assume top ( pop without removing) and size (returns \lvert\mathcal{Q}\rvert ) to also be available. We deliberately do not consider a decreaseKey operation (that replace arbitrary elements in the PQ by smaller ones), since it usually requires stable references to elements, adding significant implementation complexity and runtime overhead. While our definition admits distinct, equivalent elements, we refer to all equivalent elements as equal elements for simplicity. 2 The Original QuickHeap In 2006, Paredes and Navarro presented incremental quick select [ 45 ] , an algorithm that takes a list of n elements and then repeatedly returns the next-smallest element, such that returning the k smallest elements in an online setting takes \mathcal{O}(n+k\log k) time. The authors note that their construction can be generalized to a proper priority queue. Consequently, in follow-up work from 2010, they present the QuickHeap [ 44 ] . The QuickHeap organizes the elements in disjoint buckets B_{1},\ldots,B_{\ell} that are separated by pivots p_{1}>\ldots>p_{\ell-1} such that \infty\succ B_{1}\succeq p_{1}\succ B_{2}\succeq p_{2}\succ\dots\succeq p_{\ell-1}\succ B_{\ell}\succ-\infty, where \succeq ( \succ