Buckets, Heaps, Lists, and Monotone Priority Queues.
We introduce the heap-on-top (hot) priority queue data structure that combines the multilevel bucket data structure of Denardo and Fox with a heap.  Our data structure has superior operation bounds than either structure taken alone.  We use the new data structure to obtain an improved bound for Dijkstra's shortest path algorithm. We also discuss a practical implementation of hot queues.  Our experimental results in the context of Dijkstra's algorithm show that this implementation of hot queues performs very well and is more robust than implementations based only on heap or multilevel bucket data structures.
Introduction
A priority queue is a data structure that maintains
a set of elements and supports operations insert,
decrease-key, and extract-min. Priority queues are
fundamental data structures with many applications.
Typical applications include graph algorithms (e.g. [14])
and event simulation (e.g. [5]).
An important subclass of priority queues used in
applications such as event simulation and in Dijkstra's
shortest path algorithm [13] is the class of monotone pri-
This work was done while the author was visiting NEC
Research Institute.
y Supported by the Department of Defense, with partial support
from NSF Award CCR-9357849, with matching funds from
IBM, Schlumberger Foundation, Shell Foundation, and Xerox
Corporation.
queues. Intuitively, a priority queue is monotone
if at any time keys of elements on the queue are at least
as big as the key of the most recent element extracted
from the queue. In this paper we deal with monotone
priority queues.
Unless mentioned otherwise, we refer to priority
queues whose operation time bounds depend only on
the number of elements on the queue as heaps. The
fastest implementations of heaps are described in [4, 14,
19]. Alternative implementations of priority queues use
buckets (e.g. [2, 7, 11, 12]). Operation times for bucket-
based implementations depend on the maximum event
duration C, defined in Section 2. See [3] for a related
data structure.
Heaps are particularly efficient when the number of
elements on the heap is small. Bucket-based priority
queues are particularly efficient when the maximum
event duration C is small. Furthermore, some of the
work done in bucket-based implementations can be
amortized over elements in the buckets, yielding better
bounds if the number of elements is large. In this sense,
heaps and buckets complement each other.
We introduce heap-on-top priority queues (hot
queues), which combine the multi-level bucket data
structure of Denardo and Fox [11] and a heap. These
queues use the heap instead of buckets when buckets
would be sparsely occupied. The resulting implementation
takes advantage of the best performance features
of both data structures. We also give an alternative and
more insightful description of the multi-level bucket data
structure. (Concurrently and independently, a similar
description has been given by Raman [17].)
Hot queues are related to radix heaps (RH) 1 of
Ahuja et al. [2]. An RH is similar to the multi-level
buckets, but uses a heap to find nonempty buckets. To
get the best bounds, the heap operation time in an RH
should depend on the number of distinct keys on the
heap. The most complicated part of [2] is modifying
Fibonacci heaps [14] to meet this requirement. In
contrast, the hot queue bounds do not require anything
special from the heap. We can use Fibonacci heaps with
no modifications and achieve the same bounds as RH.
Using the heap of Thorup [19], we obtain even better
bounds. As a side-effect, we obtain an O(m
implementation of Dijk-
stra's shortest path algorithm, improving the previous
bounds. Since Thorup's bounds depend on the total
number of elements on the heap, RH cannot take immediate
advantage of this data structure.
We believe that data structures are especially interesting
if they work well both in theory and in practice.
A preliminary version of the hot queue data structure [6]
did not perform well in practice. Based on experimental
feedback, we modified the data structure to be more
practical. We also developed techniques that make hot
queues more efficient in practice.
We compare the implementation of hot queues to
implementations of multi-level buckets and k-ary heaps
in the context of Dijkstra's shortest paths algorithm.
Our experimental results show that hot queues perform
best overall and are more robust than either of the other
two data structures. This is especially significant because
a multi-level bucket implementation of Dijkstra's
algorithm compared favorably with other implementations
of the algorithm in a previous study [7] and was
shown to be very robust. For many problem classes, the
hot queue implementation of Dijkstra's algorithm is the
best both in theory and in practice.
Due to the page limit, we omit some proofs, details,
and experimental data. A full version of the paper
appears in [8].
Preliminaries
A priority queue is a data structure that maintains
a set of elements and supports operations insert,
decrease-key, and extract-min. We assume that elements
have keys used to compare the elements and denote
the key of an element u by ae(u). Unless mentioned
otherwise, we assume that the keys are integral. By
the value of an element we mean the key of the ele-
ment. The insert operation adds a new element to the
queue. The decrease-key operation assigns a smaller
value to the key of an element already on the queue.
bounds depend on C.
The extract-min operation removes a minimum element
from the queue and returns the element. We denote
the number of insert operations in a sequence of
priority queue operations by N .
To gain intuition about the following definition,
think of event simulation applications where keys correspond
to processing times. Let u be the latest element
extracted from the queue. An event is an insert or a
decrease-key operation on the queue. Given an event,
let v be the element inserted into the queue or the element
whose key was decreased. The event duration is
ae(u). We denote the maximum event duration
by C. An application is monotone if all event durations
are nonnegative. A monotone priority queue is a priority
queue for monotone applications. To make these
definitions valid for the first insertion, we assume that
during initialization, a special element is inserted into
the queue and deleted immediately afterwards. Without
loss of generality, we assume that the value of this element
is zero. (If it is not, we can subtract this value
from all element values.)
In this paper, by heap we mean a priority queue
whose operation time bounds are functions of the number
of elements on the queue. We assume that heaps
also support the find-min operation, which returns the
minimum element on the heap.
We call a sequence of operations on a priority queue
balanced if the sequence starts and ends with an empty
queue. In particular, implementations of Dijkstra's
shortest path algorithm produce balanced operation
sequences.
In this paper we use the RAM model of computation
[1]. The only nonobvious result about the model we
use appears in [9], where it is attributed to B. Schieber.
The result is that given two machine words, we can find,
in constant time, the index of the most significant bit in
which the two words differ.
3 Multi-Level Buckets
In this section we describe the k-level bucket data
structure of Denardo and Fox [11]. We give a simpler
description of this data structure by treating the element
keys as base-\Delta numbers for a certain parameter \Delta.
Consider a bucket structure B that contains k levels of
buckets, where k is a positive integer. Except for the top
level, a level contains an array of \Delta buckets. The top
level contains infinitely many buckets. Each top level
bucket corresponds to an interval
We choose \Delta so that at most \Delta consecutive buckets at
the top level can be nonempty; we need to maintain only
these buckets. 2
We denote bucket j at level i by B(i; j). A bucket
contains a set of elements in a way that allows constant-time
additions and deletions, e.g. in a doubly linked
list.
Given k, we choose \Delta as small as possible subject
to two constraints. First, each top level bucket must
contain at least (C by the
definition of C, keys of elements in B belong to at most
level buckets. Second, \Delta must be a power of two
so that we can manipulate base-\Delta numbers efficiently
using RAM operations on words of bits. With these
constraints in mind, we set \Delta to the smallest power of
two greater or equal to (C
We maintain -, the key of the latest element extracted
from the queue. Consider the base-\Delta representation
of the keys and an element u in B. By definitions
of C and \Delta, - and the k least significant digits
of the base-\Delta representation of ae(u) uniquely determine
ae(u). If - and ae are the numbers represented by the k
least significant digits of - and ae(u), respectively, then
otherwise. For we denote by - i the i-th least
significant digit of the base-\Delta representation of -. We
denote the number obtained by deleting the least
significant digits of - by - k . Similarly, for 1
denote the i-th least significant digits of ae(u) by u i and
we denote the number obtained by deleting least
significant digits of ae(u) by u k .
The levels of B are numbered from k (top) to 1
(bottom) and the buckets at each level are numbered
from 0 to \Delta \Gamma 1. Let i be the index of the most significant
digit in which ae(u) and - differ or 1 if Given
- and u with ae(u) -, we say that the position of u
with respect to - is (i; u i ). If u is inserted into B, it is
inserted into B(i; u i ). For each element in B, we store
its position. If an element u is in B(i; j), then all except
significant digits of ae(u) are equal to the
corresponding digits of - and u
The following lemma follows from the fact that keys
of all elements on the queue are at least -.
Lemma 3.1. For every level i, buckets B(i;
are empty.
At each level i, we maintain the number of elements
at this level. We also maintain the total number of
elements in B.
The extract-min operation can change the value of
-. As a side-effect, positions of some elements in B may
change. Suppose that a minimum element is deleted and
2 The simplest way to implement the top level is to "wrap
around" modulo \Delta.
the value of - changes. Let - 0 be the value of - before the
deletion and let - 00 be the value of - after the deletion.
By definition, keys of the elements on the queue after
the deletion are at least - 00 . Let i be the position of
the least significant digit in which - 0 and - 00 differ. If
differ only in the last digit), then for
any element in B after the deletion its position is the
same as before the deletion. If i ? 1, than the elements
in bucket B(i; - 00
respect to - 0 are exactly those
whose position is different with respect to - 00 . These
elements have a longer prefix in common with - 00 than
with - 0 and therefore they belong to a lower level with
respect to - 00 .
The bucket expansion procedure moves these elements
to their new positions. The procedure removes
the elements from B(i; - 00
puts them into their positions
with respect to - 00 . The two key properties of
bucket expansions are as follows:
ffl After the expansion of B(i; - 00
are in correct positions with respect to - 00 .
Every element of B moved by the expansion is
moved to a lower level.
Now we are ready to describe the multi-level bucket
implementation of the priority queue operations.
ffl insert
To insert an element u, compute its position (i;
and insert u into B(i; j).
ffl decrease-key
Decrease the key of an element u in position (i;
as follows. Remove u from B(i; j). Set ae(u) to the
new value and insert u as described above.
ffl extract-min
(We need to find and delete the minimum element,
update -, and move elements affected by the change
of -.)
Find the lowest nonempty level i.
Find the first nonempty bucket at level i.
delete an element from B(i; j), set
ae(u), and return u. (In this case old and new values
of - differ in at most the last digit and all element
positions remain the same.)
examine all elements of B(i;
a minimum element u from B(i; j). Set
and expand B(i; j). Return u.
Next we deal with efficiency issues.
Lemma 3.2. Given - and u, we can compute the position
of u with respect to - in constant time.
Iterating through the levels, we can find the lowest
nonempty level in O(k) time. Using binary search, we
can find the level in O(log time. We can do even
better using the power of the RAM model:
Lemma 3.3. If k - log C, then the lowest nonempty
level of B can be found in O(1) time.
As we will see, the best bounds are achieved for k -
log C.
A simple way of finding the first nonempty bucket
at level i is to go through the buckets. This takes O(\Delta)
time.
Lemma 3.4. We can find the first nonempty bucket at
a level in O(\Delta) time.
Remark. One can do better [11]. Divide buckets at
every level into groups of size dlog Ce, each group containing
consecutive buckets. For each group, maintain
a dlog Ce-bit number with bit j equal to 1 if and only
if the j-th bucket in the group is not empty. We can
find the first nonempty group in O
log C
time and the
first nonempty bucket in the group in O(1) time. This
construction gives a log C factor improvement for the
bound of Lemma 3.4. By iterating this construction p
times, we get an O
log p C
bound.
Although the above observation improves the multi-level
bucket operation time bounds for small values of
k, the bounds for the optimal value of k do not improve.
To simplify the presentation, we use Lemma 3.4, rather
than its improved version, in the rest of the paper.
Theorem 3.1. Amortized bounds for the multi-level
bucket implementation of priority queue operations are
as follows: O(k) for insert, O(1) for decrease-key,
Proof. The insert operation takes O(1) worst-case
time. We assign it an amortized cost of k because
we charge moves of elements to a lower level to the
insertions of the elements.
The decrease-key operation takes O(1) worst case
time and we assign it an amortized cost of O(1).
For the extract-min operation, we show that its
worst-case cost is O(k plus the cost of bucket
expansions. The cost of a bucket expansion is proportional
to the number of elements in the bucket. This cost
can be amortized over the insert operations, because,
except for the minimum element, each element examined
during a bucket expansion is moved to a lower level.
Excluding bucket expansions, the time of the operation
is O(1) plus the O(\Delta) for finding the first nonempty
bucket. This completes the proof since
Note that in any sequence of operations the number
of insert operations is at least the number of
extract-min operations. In a balanced sequence, the
two numbers are equal, and we can modify the above
proof to obtain the following result.
Theorem 3.2. For a balanced sequence, amortized
bounds for the multi-level bucket implementation of priority
queue operations are as follows: O(1) for insert,
O(1) for decrease-key, O(k+C 1=k ) for extract-min.
For the extract-min bound is O(C). For
2, the bound is O(
C). The best bound of
O
log C
log log C
is obtained for
log log C e.
Remark. The k-level bucket data structure uses
4 Hot Queues
A hot queue uses a heap H and a multi-level bucket
structure B. Intuitively, the hot queue data structure
works like the multi-level bucket data structure, except
we do not expand a bucket containing less than t ele-
ments, where t is a parameter set to optimize perform-
ance. Elements of the bucket are copied into H and
processed using the heap operations. If the number of
elements in the bucket exceeds t, the bucket is expanded.
In the analysis, we charge scans of buckets at the lower
levels to the elements in the bucket during the expansion
into these levels and obtain an improved bound.
A k-level hot queue uses the k-level bucket structure
with an additional special level k + 1, which is needed
to account for scanning of buckets at level k. Only two
buckets at the top level can be nonempty at any time,
1. Note that if the queue is nonempty,
then at least one of the two buckets is nonempty. Thus
bucket scans at the special level add a constant amount
to the work of processing an element found. We use
wrap-around at level k of k.
An active bucket is the bucket whose elements are
in H. At most one bucket is active at any time, and
H is empty if and only if there is no active bucket. We
denote the active bucket by B(a; b). We make a bucket
active by making H into a heap containing the bucket
elements, and inactive by reseting the heap to an empty
heap. (Elements of the active bucket are both in the
bucket and in H.)
To describe the details of hot queues, we need the
following definitions. We denote the number of elements
in B(i; j) by c(i; j). Given -,
\Delta, we say that an element u is in the range
of B(i;
by replacing each of the least significant digits of
- by 0 1). Using RAM operations, we can check if
an element is in the range of a bucket in constant time.
We maintain the invariant that - is in the range of
there is an active bucket.
The detailed description of the queue operations is
as follows.
ffl insert
If H is empty or if the element u being inserted is
not in the range of the active bucket, we insert u
into B as in the multi-level case.
Otherwise u belongs to the active bucket B(a; b).
t, we insert u into H and B(a; b). If
t, we make B(a; b) inactive, add u to
B(a; b), and expand the bucket.
ffl decrease-key
Decrease the key of an element u as follows. If u
is in H, decrease the key of u in H. Otherwise,
let (i; j) be the position of u in B. Remove u from
j). Set ae(u) to the new value and insert u as
described above.
ffl extract-min
If H is not empty, extract and return the minimum
element of H. Otherwise, proceed as follows.
Find the lowest nonempty level i. Find the first
nonempty bucket at level i by examining buckets
starting from B(i; - i ).
delete an element from B(i; j), set
ae(u), and return u.
examine all elements of B(i; delete a
minimum element u from B(i; j). Set
t, expand B(i; j). Otherwise, make B(i;
active. Return u.
Correctness of the hot queue operations follows
from the correctness of the multi-level bucket operations,
Lemma 3.1, and the observation that if u is in H and v
is in B but not in H, then ae(u) ! ae(v).
Lemma 4.1. The cost of finding the first nonempty
bucket at a level, amortized over the insert operations,
is O(k\Delta=t).
Proof. We scan at most one nonempty bucket during
a search for the first nonempty bucket. We scan an
empty bucket at level i at most once during the period
of time while the prefix of - including all except the last
digits remains the same. Furthermore, we scan
the buckets only when level i is nonempty. This can
happen only if a higher-level bucket has been expanded
during the period the prefix of - does not change. We
charge bucket scans to insertions of these elements into
the queue. Over t elements that have been expanded are
charged at most k times each, giving the desired bound.
Theorem 4.1. Let I(N ), D(N
the time bounds for heap insert,
decrease-key, find-min, and extract-min opera-
tions. Then amortized times for the hot queue operations
are as follows: O(k
for decrease-key, and O(F (t)+X(t)+ kC 1=k
extract-min.
Proof. Two key facts are crucial for the analysis.
The first fact is that the number of elements on H
never exceeds t since each level accounts for at most t
elements. The second fact is Lemma 4.1. Given the first
fact and Theorem 3.1, the bounds are straightforward.
For Fibonacci heaps [14], the amortized time bounds
are I(N
O(logN ). This gives O(k), O(1), and O(log t
amortized bounds for the queue operations insert,
decrease-key, and extract-min, respectively. Setting
log C and
log C), O(1), and
O(
log C) amortized bounds. Radix heaps achieve the
same bounds but are more complicated.
For Thorup's heaps [19], the expected amortized
time bounds are I(N
This gives O(k), O(1), and
expected amortized time bounds
for the queue operations insert, decrease-key, and
extract-min, respectively. Here ffl is any positive
constant. Setting
3 C and
O(log3 C), O(1), and O(log3 +ffl C) expected amortized
time.
Similarly to Theorem 3.2, we can get bounds for a
balanced sequence of operations.
Theorem 4.2. Let I(N ), D(N
the time bounds for heap insert,
decrease-key, find-min, and extract-min opera-
tions, and consider a balanced sequence of the hot queue
operations. The amortized bounds for the operations
are as follows: O(I(t)) for insert, O(D(t)
decrease-key, and O(k
extract-min.
Using Fibonacci heaps, we get O(1), O(1), and
amortized bounds for the queue
operations. Consider extract-min, the only operation
with nonconstant bound. Setting
log C ,
we get an O(logC) bound. Setting
log C
we get an O(logC) bound. Setting
log C and
we get an O(
log C) bound.
Remark. All bounds are valid only when t - n. For
should use a heap.
Remark. Consider the 1- and 2-level implementations.
Although the time bounds are the same, the two-level
implementation has two advantages: It uses less space
and its time bounds remain valid for a wider range of
values of C.
Using Thorup's heaps and setting
3 C and
expected
amortized time bounds.
The above time bounds allow us to get an improved
bound on Dijkstra's shortest path algorithm. Suppose
we are given a graph with n vertices, m arcs, and
integral arc lengths in the range [0; C]. The running
time of Dijkstra's algorithm is dominated by a balanced
sequence of priority queue operations that includes
O(n) insert and extract-min operations and O(m)
decrease-key operations (see e.g. [18]). The maximum
event duration for this sequence of operations is C. The
bounds for the queue operations immediately imply the
following result.
Theorem 4.3. On a network with N vertices, m arcs,
and integral lengths in the range [0; C], the shortest path
problem can be solved in O(m
expected
time.
This improves the deterministic bound of O(m
log C) of [2]. (The hot queue implementation based
on Fibonacci heaps matches this deterministic bound.)
5 Implementation Details
Our previous papers [7, 15] describe implementations
of multi-level buckets. Our implementation of hot
queues augments the multi-level bucket implementation
of [15]. See [15] for details of the multi-level bucket
implementation.
Consider a k-level hot queue. As in the multi-level
bucket implementation, we set \Delta to the smallest power
of two greater or equal to C 1=k . Based on the analysis
of Section 4 and experimental results, we set t, the
maximum size of an active bucket, to d C 1=k
log C e.
The number of elements in an active bucket is often
small. We take advantage of this fact by maintaining
elements of an active bucket in a sorted list instead of a
heap until operations on the list become expensive. At
this point we switch to a heap. We use a k-heap with
worked best in our tests. (See e.g. [10].)
To implement priority queue operations using a
sorted list, we use doubly linked list sorted in non-decreasing
order. Our implementation is designed for
the shortest path application. In this application, the
number of decrease-key operations on the elements of
the active bucket tends to be very small (in [16], this fact
is proven for random graphs). Because of this, elements
inserted into the list or moved by the decrease-key operation
tend to be close to the beginning of the list. A
different implementation may be better for a different
application.
The insert operation searches for the element's
position in the list and puts the element at that position.
One can start the search in different places. Our
implementation starts the search at the beginning of the
list. Starting at the end of the list or at the point of the
last insertion may work better in some applications.
The extract-min operation removes the first element
of the list.
The decrease-key operation removes the element
from the list, finds its new position, and puts the element
in that position. Our implementation starts the search
from the beginning of the list. Starting at the previous
position of the element, at the end of the list, or at
the place of the last insertion may work better in some
applications.
When a bucket becomes active, we put its elements
in a list if the number of elements in the bucket is below
1 and in a heap otherwise. (Our code uses
We switch from the list to the heap using the following
rule, suggested by Satish Rao (personal communica-
Switch if an insert or a decrease-key operation
examines more than T
ative, which may work better in some applications but
performed worse in ours, is to switch when the number
of elements in the list exceeds T 1 .
6 Experimental Setup
Our experiments were conducted on a Pentium Pro with
a 166 MHz processor running Linux 1.3.68. The machine
has 64 Meg. of memory and all problem instances fit
into main memory. Our code was written in C++
and compiled with the Linux gcc compiler version 2.7.0
using the -O6 optimization option.
We made an effort to make our code efficient. In
particular, we set the bucket array sizes to be powers of
two. This allows us to use word shift operations when
computing bucket array indices.
The full paper reports on experimental results for
five types of graphs. Two of the graph types were
chosen to exhibit the properties of the algorithm at two
extremes: one where the paths from the start vertex
to other vertices tend to be order \Theta(n), and one in
which the path lengths are order \Theta(1). The third graph
type was random sparse graphs. The fourth type was
constructed to have a lot of decrease-key operations in
the active bucket. This is meant to test the robustness
of our implementations when we violate the assumption
(made in Section 5) that there are few decrease-key
operations. The fifth type of graphs is meant to be
easy or hard for a specific implementation with a specific
number of bucket levels.
We tested each type of graph on seven implement-
ations: k-ary heaps, with k=4; k-level buckets, with k
ranging from 1 to 3, and k-level hot queues, with k ranging
from 1 to 3. Each of these has parameters to tune,
and the results we show are for the best parameter values
we tested.
Most of the problem families we use are the same
as in our previous paper [15]. The next two sections
describe the problem families.
6.1 The Graph TypesTwo types of graphs we explored
were grids produced using the GRIDGEN generator
[7]. These graphs can be characterized by a length
x and width y. The graph is formed by constructing x
layers, each of which is a path of length y. We order
the layers, as well as the vertices within each layer, and
we connect each vertex to its corresponding vertex on
adjacent layers. All the vertices on the first layer are
connected to the source.
The first type of graph we used, the long grid, has
a constant width - 16 vertices in our tests. We used
graphs of different lengths, ranging from 512 to 32; 768
vertices. The arcs had lengths chosen independently and
uniformly at random in the range from 1 to C. C varied
from 1 to 100; 000; 000.
The second type of graph we used was the wide
grid type. These graphs have length limited to 16
layers, while the width can vary from 512 to 32; 768
vertices. C was the same as for long grids.
The third type of graphs includes random graphs
with uniform arc length distribution. A random graph
with n vertices has 4n arcs.
The fourth type of graphs is the only type that is
new compared to [15]. These are based on a cycle of n
vertices, numbered 1 to n. In addition, each vertex is
connected to d \Gamma 1 distinct vertices. The length of an
arc (i; j) is equal to 2k 1:5 , where k is the number of arcs
on the cycle path from i to j.
The fifth type of graphs includes hard graphs.
These are parameterized by the number of vertices, the
desired number of levels k, and a maximum arc length C.
From C we compute p, the number of buckets in each
level assuming the implementation has k levels. The
graphs consist of two paths connected to the source. The
vertices in each path are at distance p from each other.
The distance from the source to path 1 is 0; vertices
in this path will occupy the first bucket of bottom level
bins. The distance from the source to path 2 is
making these vertices occupy the last bucket in each
bottom-level bin. In addition, the source is connected
to the last vertex on the first path by an arc of length
1, and to the last vertex of the second path by an arc of
length C.
A summary of our graph types appears in Table 1.
6.2 Problem FamiliesFor each graph type we examined
how the relative performance of the implementations
changed as we increased various parameters. Each
type of modification constitutes a problem family. The
families are summarized in Table 2. In general, each
family is constructed by varying one parameter while
holding the others constant. Different families can vary
the same parameter, using different constant values.
7 Experimental Results
The 2- and 3-level bucket structures are very robust
[7, 15]. In most cases, 2- and 3-level hot queues perform
similarly to, although usually slightly better than, the
corresponding multi-level bucket structures. One level
hot queues are significantly more robust than one level
buckets, but not as robust as 2- and 3-level hot queues.
Due to the shortage of space, we present experimental
results for the hard problems only. These problems
separate hot queues from multi-level buckets.
In the tables, k denotes the implementation: "h"
for heap, "bi" for buckets with i levels, and "hi" for
hot queue with i levels. We report running times and
counts for operations that give insight into algorithm
performance. For the heap implementation, we count the
total number of insert and decrease-key operations.
For the bucket implementations, we count the number
of empty buckets examined (empty operations). For
the hot queue implementations, we count the number
of empty operations and the number of insert and
decrease-key operations on the active bucket. We plot
the data in addition to tabulating it.
We were unable to run 1-level bucket and hot queue
implementations on some problems because of memory
limitations. We leave the corresponding table entries
blank.

Tables

3 and 4 give data for the hard-2 and hard-
3 families, designed to be hard for 2- and 3-level bucket
implementations, respectively. With at most two elements
on the heap at any time, the heap implementation
is the most efficient on the hard problems.
For the hot queue implementations, no bucket is
expanded and the action is confined to the two special
top level buckets. Thus hot queues perform almost as
well as heaps. The only exception is h1 for the largest
value of C it could handle, where its running time is
about 1:5 times greater than for other value of C. We
have no explanation for this discrepancy.
The hard-2 problems are hard for b1 and b2, and,
as expected, these implementations do poorly on this
family. Similarly, all bucket implementation do worse
than the other implementations on the hard-3 family.
Concluding Remarks
In theory, the hot queue data structure is better than
both the heap and the multi-level bucket data structures.
Our experiments show that the resulting implementation
is more robust than the heap or the multi-level bucket
data structures.
The new heap of Raman [17] instead of Thorup's
heap improves our time bound: a factor of log ffl C is
replaced by p
log log C.
Hot queues seem more practical than radix heaps.
The latter data structure requires more bookkeeping.
In addition, the hot queue heap usually contains much
fewer elements, and our implementation takes advantage
of this fact.
The 2-level hot queue data structure seems as robust
as the 3-level hot queue and is usually somewhat faster.
This data structure should be best in most applications.
The 3-level structure may be more robust for large
values of C because the value of t is much smaller,
reducing the sensitivity to the parameters for active
buckets. The 1-level hot queue may be useful in event-
simulation applications because it can be viewed as a
robust version of the calendar queue data structure.

Acknowledgments

We would like to thank Bob Tarjan for stimulating
discussions and insightful comments, Satish Rao for
suggesting an adaptive strategy for switching from lists
to heaps, and Harold Stone for useful comments on a
draft of this paper.



--R

The Design and Analysis of Computer Algorithms.



Calandar Queues: A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem.

Shortest Paths Algorithms: Theory and Experimental Evaluation.

Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking.
Introduction to Algorithms.

Algorithm 360: Shortest Path Forest with Topological Ordering.
A Note on Two Problems in Connexion with Graphs.
Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms.
Implementations of Dijkstra's Algorithm Based on Multi-Level Buckets
Expected Performance of Dijkstra's Shortest Path Algorithm.
Fast Algorithms for Shortest Paths and Sorting.
Data Structures and Network Al- gorithms
On RAM Priority Queues.
--TR

--CTR
Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
Stephen Alstrup , Thore Husfeldt , Theis Rauhe , Mikkel Thorup, Black box for constant-time insertion in priority queues (note), ACM Transactions on Algorithms (TALG), v.1 n.1, p.102-106, July 2005
Piet Van Mieghem , Fernando A. Kuipers, Concepts of exact QoS routing algorithms, IEEE/ACM Transactions on Networking (TON), v.12 n.5, p.851-864, October 2004
Klaus Brengel , Andreas Crauser , Paolo Ferragina , Ulrich Meyer, An experimental study of priority queues in external memory, Journal of Experimental Algorithmics (JEA), 5, p.17-es, 2000
Ran Mendelson , Mikkel Thorup , Uri Zwick, Meldable RAM priority queues and minimum directed spanning trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
Mikkel Thorup, Integer priority queues with decrease key in constant time and the single source shortest paths problem, Journal of Computer and System Sciences, v.69 n.3, p.330-353, November 2004
Haim Kaplan , Robert E. Tarjan , Kostas Tsioutsiouliklis, Faster kinetic heaps and their use in broadcast scheduling, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.836-844, January 07-09, 2001, Washington, D.C., United States
priority queues;data structures;shortest paths