External-Memory Priority Queues with Optimal Insertions

Priority queues are fundamental data structures with a host of applications. For example, algorithmic applications for priority queues range from classic results for sorting (such as heapsort) [13, 31, 32] and network optimization [19] to recent instance-optimal results for graph algorithms [22, 23]. In addition, priority queues have been developed for external-memory models [3, 6, 12, 18, 25, 26], ideal-cache models [4, 9], concurrent models [29], and RAM models [30]. Thus, it is desirable to design efficient priority queue data structures.

Throughout the paper, we assume a priority queue stores a multi-set of elements, where each element is a $⟨\mathrm{𝑘𝑒𝑦},\mathrm{𝑣𝑎𝑙𝑢𝑒}⟩$ pair, and the keys are from some totally ordered universe. In the following, a comparison between two elements refers to the comparison of the two elements’ keys.

Part of the reason priority queues are so broadly applicable is that they are defined in terms of two simple and useful operations:

• $\mathrm{■}$

  $\text{Insert}(e)$ inserts an element $e$.

• $\mathrm{■}$

  $\text{DeleteMin}()$ extracts and returns an element from the priority queue with minimum key. If several elements have equal keys, an arbitrary one of those is returned. This operation requires the priority queue to be non-empty before the operation.

Moreover, in internal memory, it is possible to design priority queues that hold $N$ elements and achieve $𝒪\left(1\right)$ time for Insert and $𝒪\left(\lg N\right)$ time for DeleteMin, either in the worst case [14] or amortized [13, 31]¹¹1$\lg x$ denotes the binary logarithm of $x$.. Unfortunately, prior to this work, we are not aware of any efficient data structures in external-memory models [1, 20, 21] that can match the performance of these classic internal-memory data structures.

In Sections 3–7, we describe the details of an external-memory priority queue achieving Lemma 2 below, where we bound the total number of comparisons and I/Os performed by a sequence of priority queue operations in terms of the total numbers of Insert and DeleteMin operations performed, denoted $I$ and $D$, respectively. In Section 8, we then apply global rebuilding to make the bounds depend on the current number of elements in the priority queue, achieving the amortized bounds in Theorem 1.

Our priority queue consists of an internal-memory part and an external-memory part; see Figure 1 for an overview. Each element is stored exactly once in our data structure. In internal memory we store a min-buffer, a pivot element, and an insert-buffer, where the elements in the min-buffer are all smaller than or equal to the pivot, and the elements in the insert-buffer and external memory are all larger than or equal to the pivot element. By default, Insert and DeleteMin are performed in internal memory without performing any I/Os. If internal memory contains too many elements, $\mathrm{\Theta }\left(M\right)$ elements are moved from the insert-buffer to the external part. To perform DeleteMin when the min-buffer is empty, $\mathrm{\Theta }\left(M\right)$ smallest elements from external memory are moved to internal memory. We call moving $\mathrm{\Theta }\left(M\right)$ elements between internal and external memory a transfer. In the subsequent sections, we describe the two parts in detail. We let $ℳ$ be a parameter for our construction, such that $ℳ$ is even, $ℳ$ is divisible by $B$, and $ℳ=\mathrm{\Theta }\left(M\right)$. We choose $ℳ$ such that the $𝒪\left(ℳ\right)$ space internal-memory data structure in Section 3 fits into internal memory. To be able to choose $ℳ$, $M$ is required to be sufficiently large and the internal memory to be able to hold a sufficiently large number of blocks of size $B$. If $M=𝒪\left(1\right)$, then an internal-memory data structure like a binomial queue already achieves the result of Lemma 2, and if the number of blocks fitting in internal memory is too small we can simulate a smaller block size with a constant blow up in the I/O complexity. I.e., in the following we w.l.o.g. can assume that $M$ and $M/B$ are sufficiently large to be able to choose $ℳ$.

The internal-memory part consists of a min-buffer $S$, a pivot element $p$, and an insert-buffer $L$. The pivot is larger than or equal to any element in the min-buffer, and smaller than or equal to any element in the insert-buffer and external memory. The insert-buffer is an unordered array of at most $ℳ$ elements. The min-buffer stores the overall at most $ℳ$ smallest elements in the priority queue, and is implemented using an internal-memory linear-space priority queue supporting Insert in amortized $𝒪\left(1\right)$ time and DeleteMin in amortized $𝒪\left(\lg n\right)$ time, where $n$ is the number of elements in the min-buffer. The min-buffer can, e.g., be implemented using a binomial queue [31] or the implicit post-order heap by Harvey and Zatloukal [24]. The total space for the internal part is $𝒪\left(ℳ\right)$.

$\text{Insert}(e)$ first compares $e$ to the pivot $p$. If $e\le p$, $e$ is inserted in the min-buffer using the min-buffer’s Insert operation. Otherwise, $e$ is appended to the insert-buffer. If the min-buffer overflows, i.e., gets size $ℳ+1$, we find a new pivot $p^{\prime }$ by applying the linear-time internal-memory median finding algorithm by Blum, Floyd, Pratt, Rivest, and Tarjan [5] to the elements in the min-buffer. The median, i.e., the $\left(\frac{ℳ}{2}+1\right)$th smallest element, becomes the new pivot $p^{\prime }$, the $\frac{ℳ}{2}$ larger elements and the old pivot $p$ are appended to the insert-buffer, and the $\frac{ℳ}{2}$ smaller elements are inserted into a new empty min-buffer structure using its Insert operations. If the insert-buffer overflows, i.e., gets size $>ℳ$ (due to the insertion of a single element or the old pivot $p$ and $\frac{ℳ}{2}$ elements being moved from the min-buffer to the insert-buffer), we transfer $ℳ$ elements from the insert-buffer to the external part (see Section 4).

For DeleteMin, if the min-buffer is non-empty, the smallest element is extracted from the min-buffer using the min-buffer’s DeleteMin operation and returned. Otherwise, the min-buffer is empty and the pivot $p$ is the smallest element to be returned. To establish a new pivot $p^{\prime }$ and min-buffer, the $\frac{ℳ}{2}$ smallest elements are extracted from external memory (see Section 4) and transferred to the insert-buffer (except when the external part is empty). This ensures that the $\frac{ℳ}{2}$ smallest elements in the insert-buffer are now smaller than or equal to all elements in the external part. The $\frac{ℳ}{2}$th smallest element in the insert-buffer is selected as the new pivot $p^{\prime }$ in linear time using the internal-memory selection algorithm [5]. If the insert-buffer contains elements, we set the pivot $p$ to be $+\mathrm{\infty }$. The at most $\frac{ℳ}{2}-1$ elements smaller than or equal to the new pivot $p^{\prime }$ in the insert-buffer are deleted from the insert-buffer and inserted into the min-buffer structure using its Insert operation. The old pivot $p$ is returned as the extracted minimum.

Note that a transfer either moves $ℳ$ elements from the internal to the external part, or $\frac{ℳ}{2}$ elements from the external to the internal part, i.e., the external memory always contains a multiple of $\frac{ℳ}{2}$ elements. Note also that the size of the insert-buffer is unchanged during DeleteMin, provided that there are elements in external memory. Otherwise, the number of elements in the insert-buffer decreases by $\frac{ℳ}{2}$.

Initially, the pivot $p=+\mathrm{\infty }$, such that all elements are inserted into the min-buffer until the priority queue contains $ℳ+1$ elements, where a real element is selected as the pivot and $\frac{ℳ}{2}$ elements are moved to the insertion-buffer and a new min-buffer is created for the $\frac{ℳ}{2}$ smallest elements using repeated insertions.

The external-memory part supports the insertion of a batch of $ℳ$ elements and the extraction of the $ℳ/2$ smallest elements. It consists of a set of $\mathrm{\Delta }$-heaps, where $\mathrm{\Delta }=\frac{ℳ}{B}\ge 2$. A $\mathrm{\Delta }$-heap with height $h$ is a tree where all leaves have depth $h$ (the root having depth zero), and all non-leaves have exactly $\mathrm{\Delta }$ children. Each node contains a buffer storing up to $ℳ$ elements. The elements must satisfy extended heap order, i.e., the elements in the buffer of a node $u$ are smaller than or equal to any element in the buffers of the children of $u$. A $\mathrm{\Delta }$-heap is a generalization of a binary heap [32] and is very similar to the external-memory priority queue of Fadel, Jakobsen, Katajainen and Teuhola [18], except that we do not require buffers to be sorted (this would not be possible when insertions only perform amortized $𝒪\left(1\right)$ comparisons.) The buffers in a $\mathrm{\Delta }$-heap store elements in various degrees of sortedness to be able to achieve the stated insertion cost: non-leaves are semi-sorted, whereas leaves are lazy semi-sorted as discussed in Sections 5 and 6, respectively.

The $\mathrm{\Delta }$-heaps are maintained as a sequence of collections ${𝒞}_0,\mathrm{\dots },{𝒞}_H$, where ${𝒞}_h$ contains all $\mathrm{\Delta }$-heaps with height $h$. We maintain the invariant (I1) that and that the total number of leaves in the $\mathrm{\Delta }$-heaps is $\le \frac{I}{ℳ}$ (Lemma 7), where $I$ is the total number of insertions. This invariant ensures that the maximum height $H$ of a $\mathrm{\Delta }$-heap is $\le \lfloor {\log }_{\mathrm{\Delta }}\frac{I}{ℳ}\rfloor$. The buffers of all nodes must satisfy the following invariant (I2): The buffer of a node $u$ stores at most $ℳ$ elements. If no descendant of $u$ stores elements, there is no lower bound on the buffer size of $u$. Otherwise, the buffer of $u$ contains at least $\frac{ℳ}{2}$ elements. Together with the extended heap order, this invariant implies that the $\frac{ℳ}{2}$ smallest elements in a $\mathrm{\Delta }$-heap are stored in the root buffer, except if the $\mathrm{\Delta }$-heap contains fewer than $\frac{ℳ}{2}$ elements, in which case all elements are stored in the root buffer.

When $ℳ$ elements are transferred from the internal to the external part, the $ℳ$ elements become a single node $\mathrm{\Delta }$-heap with height zero that is added to collection ${𝒞}_0$. If the collection is full, that is, $\left|{𝒞}_0\right|=\mathrm{\Delta }$, then a new root $r$ is created for a $\mathrm{\Delta }$-heap of height one with each leaf of ${𝒞}_0$ as its children. Invariant I2 is established for $r$ by recursively pulling the $\frac{ℳ}{2}$ smallest elements from its children and inserting them in the buffer (the pull operation is described below). This leaves ${𝒞}_0$ empty, and $r$ is promoted to ${𝒞}_1$. As in a $\mathrm{\Delta }$-ary number system, this promotion may propagate up through the collections, repeatedly combining $\mathrm{\Delta }$ $\mathrm{\Delta }$-heaps with height $h$ to a $\mathrm{\Delta }$-heap with height $h+1$.

For a node with elements in its buffer, a pull operation moves $\frac{ℳ}{2}$ elements from its children to the buffer of the node while preserving extended heap order, using Lemma 5 in Section 5. Note that this will make the buffer contain at least $\frac{ℳ}{2}$ elements and less than $ℳ$. If a child buffer gets size , we recursively apply the pull operation to the child, provided that not all subtrees below the child are exhausted.

To extract the $\frac{ℳ}{2}$ smallest elements from the external part, first, for each collection ${𝒞}_i$, the $\frac{ℳ}{2}$ smallest elements are found by considering the elements in the buffers of the roots by applying Lemma 5 to the roots of the collection. As the elements are just identified but not pulled from the roots, we call this a virtual pull. Second, the $\frac{ℳ}{2}$ smallest elements among the $(H+1)\frac{ℳ}{2}$ candidates from the virtual pulls are found by applying a linear-time selection algorithm, Corollary 3 below. These elements are removed from their respective roots and transferred to the internal part. For each root buffer now containing elements, we recursively pull $\frac{ℳ}{2}$ elements from its children, to the extent possible.

Note that the total number of elements in external memory is always a multiple of $\frac{ℳ}{2}$, but this is not necessarily true for each $\mathrm{\Delta }$-heap due to the extractions of the smallest $\frac{ℳ}{2}$ elements across all $\mathrm{\Delta }$-heaps.

Given two sequences $X$ and $Y$, we say $X⪯Y$, if for every $x\in X$ and $y\in Y$: $x\le y$. Note that $X⪯Y$ implies no specific order within each individual sequence $X$ or $Y$.

A buffer in external memory is a linked list of blocks $b_1,b_2,\mathrm{\dots },b_{\delta }$, where each block contains $B$ elements, except possibly the first and last blocks, which contain $\le B$ elements. In the following, we simply denote such a linked list as a list. We define a list to be semi-sorted if $b_i⪯b_{i+1}$ for every . All buffers of non-leaf nodes in a $\mathrm{\Delta }$-heap are stored as semi-sorted lists. The following are useful tools for working with semi-sorted buffers.

Blum, Floyd, Pratt, Rivest, and Tarjan [5] proved that the $k$th smallest element in a list with $N$ elements can be found using $𝒪\left(N\right)$ comparisons using a double recursion making repeated use of scanning lists. Analyzed in the external-memory model, this immediately implies that selection can be performed in a linear number of I/Os, and we have the following corollary.

Since $I$ insertions can create $\mathrm{\Theta }\left(I/ℳ\right)$ leaf buffers of size $ℳ$, they cannot all be semi-sorted, as that would require $\mathrm{\Theta }\left(I\lg \mathrm{\Delta }\right)$ comparisons. The lower bound of $\mathrm{\Omega }\left(ℳ\lg \mathrm{\Delta }\right)$ comparisons for the multiple selection problem for each buffer is due to Dobkin and Munro [2, Theorem 1]. Instead, a leaf buffer with $ℳ$ elements is stored as a lazy semi-sorted list, see Figure 2. A lazy semi-sorted list stores the $ℳ$ elements as a sequence of chunks $c_1⪯c_2⪯\mathrm{\cdots }⪯c_d$, where $d=\lceil \lg \frac{ℳ}{B}\rceil +1$ and, initially, the elements inside a chunk are stored in arbitrary order. Chunk $c_1$ stores $B$ elements, $c_i$ stores $B{2}^{i-2}$ elements for , and $c_d$ stores the largest $ℳ-B{2}^{d-2}$ elements. If each chunk is converted into a semi-sorted list, and all chunks are concatenated, we have a semi-sorted list for the buffer. The basic idea is to exploit that a $\mathrm{\Delta }$-heap always accesses the blocks of a semi-sorted buffer left-to-right, implying that we can delay expanding a chunk into a semi-sorted sequence of blocks using Lemma 4 until the first block of the (semi-sorted version of the) chunk is accessed, hence the name lazy semi-sorted. The initial partitioning of a buffer into chunks is done by recursively partitioning the half with the smaller elements using Corollary 3.

When Insert and DeleteMin can be performed entirely within the internal part, no I/Os are performed. The number of comparisons is $𝒪\left(1\right)$ for Insert and $𝒪\left(\lg \min (ℳ,I)\right)$ for DeleteMin, plus the cost of moving elements from the min-buffer to the insert-buffer. If an insertion causes the min-buffer to overflow, we spend $𝒪\left(ℳ\right)$ comparisons moving elements to the insert-buffer and building a new min-buffer. This can only happen once every $\frac{ℳ}{2}$ insertion, so the total cost for this is $𝒪\left(I\right)$ comparisons and no I/Os.

A transfer either moves $ℳ$ elements from the internal to the external part, or $\frac{ℳ}{2}$ elements from the external to the internal part. The following lemma bounds the number of transfers in each direction in terms of $I$ and $D$.

In Sections 3–7, $I$ denotes the total number of insertions performed, allowing the current size $N$ to be arbitrarily smaller than $I$. Since the comparison and I/O bounds of Lemma 2 are dependent on $I$, the bounds are not a function of the current number of elements $N$ in the priority queue. To achieve this, we apply the standard technique of global rebuilding [28, Chapter 5].

The external-memory priority queue presented in this paper supports insertions with asymptotically fewer comparisons and I/Os than previous results. This is particularly beneficial in settings such as event-driven simulations or other incremental computations where execution may terminate before all elements have been extracted from the queue and the cost of insertions dominates. It should be noted that the amortized internal computation time required by our construction is asymptotically the same as the number of comparisons performed (which also holds for the black boxes used by the construction [5, 24, 31]).

The presented data structure is inherently cache-aware. This raises a natural question: does there exist a cache-oblivious priority queue that achieves the same amortized bounds on comparisons and I/Os?

The structure is also highly amortized (e.g., due to global rebuilding, transfers between internal and external memory, recursive pulling, lazy semi-sorted buffers), and a single Insert or DeleteMin operation might require $\mathrm{\Theta }\left(N/B\right)$ I/Os in the worst-case. Another natural question, is whether it is possible to achieve a solution with worst-case guarantees, e.g., such that a window of $B$ priority queue operations requires worst-case $𝒪\left(B\lg N\right)$ comparisons and $𝒪\left({\log }_{M/B}\frac{N}{B}\right)$ I/Os, while maintaining the improved amortized bounds for Insert.