COMPARATIVE STUDY OF PRIORITY QUEUES
IMPLEMENTAnON
By
DONGHONG WEI
Bachelor ofForeign Languages
Shanxi University
Taiyuan, China
1990
Submitted to the Faculty of the
Graduate College of the
Oklahoma State University
in partial fulfillment of
the requirements for
the degree of
MASTER OF SCIENCE
December, 1999
Oklaho.,..,,'" C '"I/o I It ... :• •~ ,._ .oJ., • , 'f """"':Iry
COMPARATIVE STUDY OF PRIORITY QUEUES
IMPLEMENTATION
Thesis Approved:
DeaOfthe Graduate College
ii
ACKNOWLEDGMENTS
I wish to express my deepest appreciation to my advisor Dr. Jacques Lafrance for
accepting to be my major advisor. His enthusiastic support, constructive guidance,
encouragement, and friendship throughout time of acquaintance have been a constant
source of inspiration and motivation that helped me gain confidence academically and
professionally. My sincere appreciation also extends to Dr. John P. Chandler whose
intelligent suggestion and guidance have made this thesis feasible. r would like to thank
Dr. H. K. Dai for his constructive criticism, direction and wisdom. Grateful appreciation
also goes to the faculty and students of the Department of Computer Science for their
interest, guidance, and friendship.
I wish to sincerely thank my husband for his unconditional love, spiritual support
and endless encouragement.
To my parents, Shuren Wei and Shuzhen Ma, I want to tell them how much I love
them and that r could not have made it through graduate school without their total support
and consistent encouragement.
I dedicate this thesis to my dearest daughter, Connie Yang, who is the reason why
I have worked so feverishly to complete this project.
Finally, I would like to praise God for providing me with confidence, wisdom,
persistence and strength that guided me through the entire process.
iii
TABLE OF CONTENTS
Chapter Page
1. INTRODUCTION.. , ,.. " , ' . .............................. 1
II. LITERATURE REVIElEW.. , ", , ' .. , .. ' , .4
2.1 Priority Queue Data Structure , ', , 5
2.2 Priority Queue and Discrete Event Simulation. , , ,,10
III. DESIGN AND IMPLEMENTATION ISSURES.... , .14
3.1 Performance measurement Techniques , , 14
3.1.1 Access Patterns ," ' , , 14
3.1.2 Time Measurements " , " .,.19
3.2 Design and Implementation... .. . .. . . .. . ... . ,' 20
3.2.1 Implicit Binary Heap Simulation , .. . .. ... 21
3.2.2 Median Pointer Linked List Simulation. , ' .. ,,.23
3.2.3 SPEEDESQ Simulation .. , 24
IV. EVALUATION., .. ...... ,., .. , ' ,., '" ., 27
4.1 Program. .. , , " 27
4.2 Performance of Three Priority Queues 29
v. CONCLUSIONS , , , ,., ' .. ..,.35
LITERATURE CITED. ..".. ..... .. . ..
iv
. 37
LIST OF FIGURES
Figure Page
1. The Basic Operation Model ofa Priority Queue 5
2. Classic Hold Flow Chart 15
3. UplDown Model Flow Chart...... . 17
4. Markov Hold Flow Chart.. . 18
5 Implicit Binary Heap and an Array Representation. .. . .... . .21
6. Implicit Binary Heap Flow Chart.. . .. . .. .22
7. Median Pointer Linked List Data Structure 23
8. Median Pointer Linked List Flow Chart .24
9. SPEEDESQ Data Structure 25
10. SPEEDESQ Flow Chart 26
11. The Simulation Program Flow Chart 28
12. Implicit Binary Heap With Classic Hold, Up/Down and Markov Hold 29
13. Empirical Behavior at Large N of the Implicit Binary Heap 29
14. Median Pointer Linked List with Classic Hold, Up/Down and Markov Hold 30
15. Empirical Behavior at Large N of the Median Pointer Linked List 3 J
16 SPEEDESQ with Classic Hold, Up/Down and .Markov Hold.... ..32
17 Empirical Behavior at Large N of the SPEEDESQ.. .33
18. The Performance of the Three Priority Queues with Markov Hold '" .. 34
v
CHAPTER I
INTRODUCTION
Priority queues are used in a wide variety of applications including operating
systems, realtime systems and discrete event simulations [Ronngren, 1997]. In a priority
queue, each element is ordered by its associated priority [Ayanne, 1990]. The basic
operations are dequeue and enqueue. A dequeue operation removes the element with the
highest priority, and an enqueue inserts a new element into the queue. Ordinary stacks
and queues are special cases of priority queues [Brown, 1988].
The implementation of the priority queues may have a profound effect on the
performance of such applications. Over the years, several performance studies on
priority queues have appeared in the literature. A significant number of these studies
have been performed in the context of discrete event simulation (DES) [Jones, 1986]. The
reason for studying priority queues is twofold: the specific implementation is often
crucial to the performance of the simulator, and the way operations are performed on the
pending event set provides an excellent test case for studying priority queue [Fujimoto,
1990]. The impact of the implementation ofthe pending event set can have a super linear
effect on the performance [Ronngren, 1993]. Although priority queues are used in various
contexts, they are some general quality measures of interest. The most important metric
is the time required to perform the most common operations that are dequeue and
enqueue, and we refer to this time as access time. In most cases, the measure of interest
1
is the amortized access time. Thus it is important to find methods that allow a realistic
and accurate assessment of the access time.
Up till now, the most widely used method for performance studies of priority
queues has been the Classic Hold introduced by Vaucher and Duval [Duval, 1975] and
refined by Jones [Jones, 1986]. It models operation on a fixedsize queue where a series
of hold operations (a dequeue followed by an enqueue) are perfonned. An UplDown
model is proposed by Ronngren et al [Ronngren, 1993], where a sequence of enqueues is
followed by an equally long sequence of dequeues. Markov Hold is proposed by Chung
et al. [Chung, 1993], where operations on the queue are detennined by a twostate
Markov process with states insert (enqueue) and delete (dequeue). By changing the
transition probabilities, the Markov Hold model can represent random sequences of
enqueue and dequeue operations.
Although the three methods mentioned above have been introduced to perform
the studies of priority queues, comparatively studying priority queues with the three
methods and examining the different priority queue algorithms for performing the eventlist
in discrete event simulation programs have not been studied before.
In this thesis I explored the three methods to study the behavior of three different
priority queues, which are arraybased Implicit Binary Heap, linkedlistbased Median
Pointer Linked List and lazyqueuebased SPEEDESQ Comparing the performances of
the three different typical priority queues with the three models, this thesis provides
readers with an accurate and reali stic analysis of each priority queue's access time
complexity for the simulation. Readers can choose the best priority queue or access
2
pattern depending on the application. The thrust ofthis thesis is to provide readers a
paradigm for the study of computation complexity of comparison based problems.
Chapter 2 provides a review of the priority queue data structures and the
implementation of the pending event set by use of priority queues. Chapter 3 provides a
discussion of the design and the implementation details ofthe software that is developed
as part of the thesis. The analysis and evaluation of the software developed are discussed
in Chapter 4. The thesis ends with Chapter 5 that provides a summary and the
conclusions drawn from the study.
3
CHAPTERn
LITERATURE REVIEW
An abstract data type (ADT) is a data type along with the set of operations of that
type. Abstract data types are mathematical abstractions. They can be viewed as an
extension of modular design [Weiss, 1997]. A Queue is one of the most simple and basic
ADT, as John Beidler mentioned [Beidler, 1996]:
A queue is a sequential, homogeneous, variablesized, possibly empty collection
of objects whose attributes and operations satisfy the following:
1. A queue is said to be empty when it contains no obj ects.
2. A queue has two ends, called the front and the rear.
3. The only object in a queue that is visible is the object at the front of the queue.
4. The dequeue operation removes the object currently at the front of the queue.
All remaining objects in the queue, if any, move one position forward toward
the front ofthe queue. The object immediately following the front object
becomes the new front of the queue. If there are no other objects in the queue,
the queue becomes empty.
5 The enqueue operation inserts new objects at the rear of the queue. lfthe
queue was empty, the enqueued object becomes the front object in the queue.
At any time, new objects may be enqueued. When an object is enqueued, it
becomes the rear object in the queue.
The queue constructors modify the queue either by removing the object at the
front of the queue or by adding new objects to the rear of the queue [Beidler, 1996],
therefore, the basic operations are dequeue and enqueue. As the enqueue inserts an
element in the rear of the list, the queue expands. As the dequeue deletes the element at
the front of the list, the queue shrinks [Weiss, 1997]. The order of the objects in the
queue, from front to rear, is the order in which the objects were enqueued. The term
FIFO, firstinfirstout, describes the order of processing of the objects in a queue.
4
However, sometimes some types of data in the queue require the data to be
deleted according to a priority rather than FIFO. Any data structure that upports the
operations of searching, inserting, and deleting minimum or maximum is called a priority
queue [Horowitz, 1996].
The priority queue is a structure for storing and retrieving information [Beidler,
1996]. It has at least the following two operations: dequeue and enqueue. A dequeue
operation removes the element with the highest priority, and an enqueue operation inserts
a new element into the queue. Figure 1 shows the basic model ofa priority queue.
DeleteMax!M.in (H)+1 Priority Queue H rInsert (H)
Figure 1. The Basic Operation Model of a Priority Queue
In the following two sections, I will review seven wellknown priority queue data
structures and discrete event simulation.
2.1 Priority Queue Data Structures
There are obviously several ways to implement the priority queues. The following
seven wellknown data structures will be introduced: Implicit Binary Heaps [Bentley,
1985], Median Pointer Linked Lists, Skew Heaps [Sleator and Tarjan, 1986], Calendar
Queue [Brown, 1988], Henriksen's [Henriksen, 1997], the Lazy Queue [Ronngren, 1993a]
and the SPEEDESQ [Steinman, 1992].
2.1.1 Implicit Binary Heap
A heap [Aho, 1974] is a standard data structure for implementing priority queues.
An Implicit Binary Heap is one of the most elegant of storage structures to represent a
priority queue. The Implicit Binary Heap is defined as a structure on locations 1 through i
of an array with the property that the element in location i is smaller than that in location
5
[il2}, thus including a complete binary tree with the property that th value ofthe parent
is greater than that ofthe child [Munro,1979}. Such a pointer free representation has been
called an implicit data structure. It is well known that the Implicit Binary Heap enables
us to perform the basic priority queue operations. In an enqueue operation, the new
element is placed at the base ofthe heap (i.e., as the rightmost leaf at the lowest level).
To restore the heap property (i.e., that each parent has a higher priority than any of its
children), the new element is compared to its parent and they are swapped if necessary.
This process has to be repeated upward in the heap until either the root is reached or at
some level no swap is needed. In the dequeue operation, delete the element with the
highest priority and then reorder the heap. Both the enqueue and dequeue operations
have a worstcase behavior of0 (log N) [Gaston, 1986], where N is the number of
elements in the queue.
2.1.2 Median Pointer Linked List
The M.edian Pointer Linked List was implemented as a Doubly Linked Circular
List that allows insertions to take place from both the front and the back [Weiss, 1997].
A pointer to the median element (with respect to the number of elements) in the list is
used to identify whether the insertions should be made from the front (timestamp ofthe
new element is less than or equal to that ofthe median element) or the back end of the list
[McCormack and Sargent, 1981]. A dequeue operation on a Median Pointer Linked list
is performed in constant time, whereas the enqueue operation is O(N).
2.1.3 Skew Heap
The Skew Heap [Sleator and Tarjan 1986J(sometimes called a priority queue or
mergeable heap) is a selfadjusting forming heapordered binary tree where any
6
descendant of a node has lower priority than the node itself The selfadjusting data
structures have the following advantages: I) They need less space, since no balance
information is kept. 2) Their access and update algorithms are easy to understand and to
implement. 3) In an amortized sense, ignoring constant factors, they can be at least as
efficient as balanced structures [Sleator, 1986]. The fundamental operation on the Skew
Heaps is a meld operation. A meld operation merges two Skew Heaps into one,
preserving the heap property. Thus a dequeue operation is performed by removing the
topmost (root) node and melding the two resulting subheaps into a single heap. In the
topdown Skew Heap, an enqueue operation is performed as a meld of a onenode Skew
Heap and the existing Skew Heap. The amortized time to perform a dequeue or an
enqueue operation is O(logN) [Sleator and TaIjan 1986] although individual operations
may be D(N) if the heuristics for the balancing of the heap fails.
2.1.4 Calendar Queue
The Calendar Queue suggested by Brown is a multilistbased data
structure[Brown, 1988]. It is a new priority queue implementation for the future event set
problem. It uses an elegant techni.que to manage the overflow problem encountered in
multilistbased implementations. Calendar Queue is modeled after a desk calendar. In
the Calendar queue, there exists no dedicated overflow structure. All elements, including
those that would fall into an overflow structure in an ordinary multi list, are inserted into
the sublists. This is accomplished in the following way: all sublists span equally long
priority (time) intervals where the total length of these subintervals is called a year. When
a new element is inserted into the queue, the sublist into which the new element will fall
is calculated. To ensure good performance, it is required that the sublists, which are
7
implemented as linked lists, are kept short (an average length oftwo elements). This is
accomplished by a resize operation. The resize operation is performed when the queue
size has changed by a factor oftwo. The new length ofthe subintervals is calculated by
using an approximation ofthe distribution based on the first few elements [Brown 1998].
The Calendar Queue has 0(1) access time under many operating conditions although the
resize operations are O(N). The worstcase amortized access time for the Calendar Queue
is O(N).
2.1.5 Lazy Queue
The Lazy Queue [Ronngren et aI., 1993] is a multilistoriented data structure. The
fundamental idea is to divide the future events into several parts and keep only a small
portion ofthe elements completely sorted [Robert, 1997]. The elements are divided into
1) A near future that is kept sorted, 2) A far future that is partially sorted, arid 3) A very
far future that is used as an overflow bucket. As time advances, part of the far future is
sorted by standard sorting techniques and transferred into the near future. This lazy
sorting behavior gives the queue its name. The far future part of the queue is
implemented as an array of unsorted sublists where each sublist corresponds to an equally
long priority interval. The near future consists of a sorted array of elements (transferred
from the far future) and a skew heap is used to insert the new elements that belong to the
near future. Skew heaps are used to implement the very far future of the lazy queue. To
ensure good utilization of the data structures, a set of resize operations was introduced.
Some modifications in the implementations resize operations have been performed that
improve the performance for smaller queue sizes as compared to the results presented in
[Ronngren et al. 1993a]. In particular, there is a resize operation that recalculates both
8
the length of a subinterval and the number of subintervals. Ronngren's operation is used
whenever a resize operation is initiated. However, the criteria for expensive, worst case
of O(NlogN), but they are amortized over the relatively inexpensive ordinary operations.
This results in a near 0(1) access time for many operation conditions. The worstcase
amortized access time can be restricted to O(N) [Ronngren et al., 1993]. A minimum
queue size of256 elements is requested to perform a resize operation. The Lazy queue is
stable only if the sorting algorithm and the implementations of the near and very far
futures are stable.
2.1.6 Henriksen's DataStructure
Henriksen's [Henriksen, 1977] implementation of the pending event set employed
in GPSS/H [Gordon, 1981] uses a linked list and an array of pointers into the list. The
array of pointers is used to perfonn binary searches in the list to find the place where a
new element should be put in an enqueue operation. A heuristic algorithm is employed to
update the auxiliary pointers. The implementation was based on the code given in
Kingston where the array of pointers is used as a circular list of pointers [Kingston,
1986]. The size of the array of pointers is doubled when necessary as the size grows.
However, the array is not decreased in size if the queue size shrinks. The amortized
access time of Henriksen's algorithm is often 0 (log N), and limited by 0';;; in the worst
case [Kingston, 1986]. Dequeue operations are performed in constant time, whereas
enqueue operation can be 0 ( ,J;;).
2.1.7 SPEEDESQ
The SPEEDESQ [Steinman 1992] consists of two single linear linked lists. One
list, referred to as the "dequeuelist", is kept sorted and the other list, the "enqueuelist" is
9
unsorted. New elements are added to the enqueuelist, which can be done in constant time
since the list is kept unordered. The queue also maintains a variable recording of the
highest priority (smallest timestamp) of any element present in the enqueuelist. A
dequeue operation removes the element with the highest priority from the dequeuelist.
In a dequeue operation, the enqueuelist is sorted and merged with the dequeuelist if the
dequeuelist is exhausted or whenever the highest priority element is present in the
enqueuelist. The merge operation is potentially an O(N) which, if frequent, result in a
worstcase performance of o(N). SPEEDESQ has constant enqueue time and a constant
time for many ofthe dequeue operations. However, dequeue operations that involve
sorting of the enqueuelist have an O(NlogN) time complexity.
2.1.8 Expected Performance of the Priority Queues
Table I Summarizes the theoretically expected performance ofthe sequential priority
queues.
Table 1. Expected Performance of Sequential Priority Queues
Queue
o I)
2.2 Priority Queue and Discrete Event Simulation (DES)
Priority queues are used in many applications including realtime systems,
operating systems and simulations. Typical applications require primitive operations
among the following five: INSERT, DELETE, MIN, UPDATE, AND UNION. The
10
operation INSERT (name, labe~ Q) adds an element to queue Q. DELETE (name)
removes the element. Operation MIN (Q) returns the name of the element inQ having the
least label, and UPDATE (name, label) changes the label of the element named. UNION
(Ql, Q2, Q3) merges into Q3 all elements ofQl and Q2; the sets Ql and Q2 become
empty [Chung, 1993].
A variety of applications directly require using priority queues are: job
scheduling, discrete simulation languages where labels represent the time at which events
are to occur, as well as various sorting problems [Jean, 1997]. Priority queues also playa
central role in several good algorithms such as optimal code constructions, Chartre's
prime number generator and Brown's power series multiplication. The applications have
also been found in numerical analysis algorithms and in graph algorithms for such
problems as finding shortest paths and minimum cost spanning tree [Jean, 1997].
The most popular use of priority queues is in the area ofdiscrete event
simulations (DES) [Ronngren, 1997]. Here, a priority queue is used to hold the pending
event set (PES) which contains the generated but not yet evaluated events. in discrete
event simulations, events are simulated as occurring at discrete times determined by
random variables. A data structure stores unprocessed events. The basic action is to
remove the event with the earliest time and process it. This processing may create new
events which must be inserted into the data structure and which will be processed in the
future. To accomplish this, the data structure should support two operations: insert and
deletemin. The data structure, which stores the events (according to their execution
times), is called an eventlist. The eventlist can be represented as a priority queue in
which priorities are assigned according to the time, the higher priority given to the item
11
with the smallest value. The Pending event set (PES) is the set of aU generated but not yet
evaluated events and, in general, is represented by a priority queue. Tile implementation
of the PES is often crucial to simulation performance. An empirical study by Comfort
[Comfort, 1984] indicated that up to 40% of the simulation execution time might be spent
on the management of the PES alone. Therefore, as systems become more complex and a
demand for fast simulators arises efficient implementation ofthe PES becomes
increasingly important [Ronngren, 1997].
In a PES, the simulated times at which the events are scheduled to be executed
(timestamps) are used as priorities. A sequential discrete event simulator operates in a
threestep cycle: remove the events with the smallest time stamp (i.e., highest priority)
from the PES; execute this event; and insert any new events resulting from this execution
into the PES. Thus the two most common operations on the PES data structure are:
dequeues, the removal of the event with the highest priority, and enqueue, the insertion of
a new event. Empirical studies of real simulations [Comfort, 1984] indicate that these
two operations can account for as much as 98% of an operations on the PES, the rest
being other operations such as deletion of arbitrary events and the like. The performance
of the PES is influenced by a number of variables including the initial distribution of
events, the priority increment distributions, access patterns, and the size ofthe event set
Thus the event set implementation must be efficient under a wide variety of operation
conditions and possibly by adaptive to take advantage of these conditions [Jones, 1986].
The requirements of high performance simulation of complex systems and the
observation that these systems are often inherently parallel have motivated the
development of parallel discrete event simulati.on[ Fujimoto, 1990]. In parallel DES
12
(PDES), the inherent parallelism that exists in most simulation models is realized by
allowing logical processes (LPs) to be executed in parallel using several processing
units[Steinman, 1992]. In PDES priority queues are also often used as scheduling queues
for LPs that are ready to execute. This queue may also be shared by several processing
elements.
In this thesis I comparatively studied the performance of the different priority
queues in the discrete event simulation programs.
13
CHAPTERID
DESIGN AND IMPLEMENTATION ISSUES
3.1 Measurement Techniques
When designing experiments to study priority queues, it is important to carefully
choose access patterns and measurement techniques. The choices should reflect the
operating conditions under which the priority queue will be used as well as enabling
accurate measurement ofthe performance metrics of interest. When selecting access
patterns for this thesis, I chose synthetic experiments over real simulations. Synthetic
experiments provide better control over the variables affecting performance, therefore
they better expose the factors that influence performance [Jones, 1986].
3.1.1 Access Patterns
There are three classes of access patterns used to implement the simulation:
Classic Hold, Up/Down Model, and Markov Hold.
Classic Hold
Up till now, the most widely used method for performance studies for priority
queues has been the Classic Hold (See Figure 2) introduced by Vaucher and Duval and
refined by Jones. A hold operation is defined as a dequeue followed by an enqueue
operation. The Classic Hold models the behavior of a discrete event simulation system
performing a sequence of operations. In the Classic Hold experiments, the queue is
initialized to a fixed size and the measurement phase, which consists of a number of
14
NO
Begin
Initialize Queue Size
Build Queue with this
Queue Size
Loop Time =Minimum
Increase Loop Time Value
YES
Increase Queue Size Value
NO
YES
End
Figure 2. Classic Hold Flow Chart
15
hold operations, is performed. The queue size having been built remains fixed
throughout the process of the Classic Hold operation.
UplDown Model
An UplDown Model (See Figure 3) is proposed by Ronngren et a1. [Ronngren,
1993], model the PES's transient behavior where the queue grows to a certain size by a
sequence of enqueues and then shrinks by a same sequence of dequeues. In the
experiment, the measurements start and end with a fixed size queue for this access
pattern.
Markov Hold
Chung et a1. [1993] proposed an elegant generalization of the Classic Hold, called
the Markov Hold model (See Figure 4). In Markov Hold, the operations on the priority
queue are generated by a twostate Markov process that may be in either of the states
insert (enqueue) or delete (dequeue). By changing the state transition probabilities this
model can be used to represent the Classic Hold, UplDown, and a generalized random
sequence of enqueue and dequeue operations. The Markov model can be used to
generate access patterns equivalent to the three classes mentioned.
In the Markov Hold simulation, the state transition is generated by the function
randomNum (). If the function returns even number, enqueue operation is performed. If
the function returns odd number, dequeue operation is performed.
16
Initialize Queue Size
Build Queue with this
Queue Size
NO
NO
Loop Time =Minimum
Increase Loop Time Value
YES
Loop Time =Minimum
Increase Loop Time Value
NO
Loop Time>
Maximum
Increase Queue Size Value
Queue Size>
Set Number
YES
End
Figure 3. UplDown Model Flow Chart
17
Begin
Initialize Queue Size
Build Queue with this
Queue Size
Loop Time =Minimum
NO NO
Is enqueue
operation?
YES
NO
Increase Loop Time Value
YES
Increase Queue Size Value
Queue Size>
Set Number
YES
End
Figure 4. Markov Hold Model Flow Chart
18
3.1.2 Time Measurements
All the simulation was performed on the Compaq Proliant 300 Server with 2
processors of 300MHz. The program code was built and compiled with the Microsoft.
Visual C++ under the Windows 95 environment. Due to insufficient resolution ofthe
available time measurement mechanisms, the function void Jtime (struct _timeb
*timeptr) was used to measure the access time. Jtime does not return a value, but fills in
the fields of the structure pointed to by pointer timeptr that points to _timeb structure.
The Jtime function gets the current local time and stores it in the structure pointed to by
timeptr. The _timeb structure is defined in SYS\TIMEB.H. It contains four fields:
dstflag which is nonzero if daylight savings time is currently in effect for the local time
zone; millitm which is fraction of a second in milliseconds; time which is in seconds since
midnight (00:00:00), January 1, 1970, coordinated universal time (UTC); timezone the
value of which is set from the value of the global variable _timezone (See Example).
Example
/* FTlME.C: This program uses _ftime to obtain the current time and then stores this
time in timebuffer*/
#include <stdio.h>
#include <sty/timeb.h>
void main (void)
{
struct_timeb timebuffer;
char *timeline;
ftime (&timebuffer);
timeline = ctirne(& (tirnebuffertirne));
printf (" The time is %.19s.%hu %s", timeline, timebuffer. millitm,
&timeline[20]);
}
Output
ThetimeisTueMar2115:26:41.341 1995
19
The Jtime routines use the TZ environment variable. IfTZ is not set, the run
time library attempts to use the timezone information specified by the operation system.
Jtime store current system time in variable of type struct _timeb.
3.2 Design and Implementation
I used the three measurement methods (Classic Hold, the Markov Hold, and
Up/Down model) mentioned above to design and implement the performance of the three
different priority queues. These priority queues are the Implicit Binary Heap [Bentley,
1985], the Median Pointer Linked List [McCormack and Sargent, 1981] and the
SPEEDESQ [Steinman 1992]. The followings are the reasons why I choose these three
priority queues:
1. Implicit Binary Heap is a wellknown priority queue. It stands for the arraybased
structures that are popular because of the potential for a logarithmic relationship
between queue size (array size) and the complexity of insert and delete operations.
2. Median Pointer Linked List is a typical and classic ADT to represent priority queues.
It stands for the linkedlistbased structure with more sophisticated pointerbased
algorithms.
3. SPEEDESQ is a twolinkedlist priority queue data structure. It stands for the lazyqueue
oriented data structures that are more recently proposed queue
implementations.
In this simulation program, all codes were written in the C programming
language, since C programming language obtains the advantages of few restrictions, few
complaints, block structures, standalone functions and a compact set of keywords
20
[Schildt, 1990]. Moreover, C programming language has the pow rful portability and
efficiency.
Four operations on the priority queues were implemented in the experiment:
createqueue, dequeue, enqueue and freequeue. .Jtime () function was used to measure
the mean access time.
3.2.1 Implicit Binary Heap Simulation
3
Element in Array
Parent:
Left Child: 2i
!Right Child: 2i + 1
9
5
10
left child
right child
99
6 7
Figure 5. Implicit Binary Heap and an Array Representation
21
Since the Implicit Binary Heap data structure (heap) is a binary tree completely
filled, it can be regarded as an array object. The Implicit Binary Heap thus consists of an
array and an integer element representing the priority (see Figure 5).
Implicit Binary Heap
Move the last element
to the first position in
the array
Figure 6. Implicit Binary Heap Flow Chart
In the heap simulation program (see figure 6), in order to avoid the transient
startup period of the simulation, the initial size of the heap is set up to 16, which is built
by buildFixedSizeQu 0 function. The element of the heap is generated by RandomNum 0
function. The enqueue operation is performed by the enqueueHeap 0 function and the
dequeue operation by dequeueHeap () function. Both operations involve ensuring that the
heap order property is maintained by Build_heap 0 function. The heap size is increased
22
by twice for each time from 16 to 100,000. For each fixed size heap, each acce pattern
loops 5 million times.
3.2.2 Median Pointer Linked List Simulation
The Median Pointer Linked list (See Figure 7) is implemented as a doubly linked
list. The structure is utilized in the design of each cell in the linked list.
101 98
prey . prey
next . next +
•••
30
+ prey
next 4
Median Pointer
• ••
7 99
. prey . prey
next f+ next
Figure 7. Median Pointer Linked List Data Structure
In the simulation program each cell is composed of an integer element and two
pointers referring to the previous and next cell. The queue size of the Median Pointer
Linked List is from 10 to 60,000 and for each queue size, the operations repeat 100,000
times to calculate the average. The list is built by the buildFixedSizeMedlst 0 function.
Each element of the cell is generated by the RandomNum 0 function. A median pointer
is set up to point to the middle position ofthe linked list. Enqueue and dequeue
operations were performed by calling the functions enquToMedLst 0 and
dequFrmMedLst 0 respectively. In the enqueue operation, the element ofthe new cell
will compare with the value of the median pointer. If the element is larger than the
median pointer node, the cell will be inserted from the front ofthe list, otherwise, the cell
will be inserted from the back of the List. The median pointer is updated after finishing
the two operations: when dequeue or equeue operation performs twice, the median
23
pointer moves backward or forward once, otherwise, the median pointer remains still. If
the linked list is empty, median pointer points to the head of the list (See Figure 8).
Median Pointer Linked List
a>b
?
Move the header
pointer to the next
YES
Update
Median Pointer
No
Add this element from
1+1 the end of the list
Update
Median Pointer
Figure 8. Median Pointer Linked List Flow Chart
3.2.3 SPEEDESQ Simulation
The SPEEDESQ (See Figure 9) consists oftwo single linear linked lists: one is
sorted dequeue linked list and the other is unsorted enqueue linked list. The merge
24
operation will occur whenever the dequeue linked list is empty or the highest priority
element is present in the enqueue linked list.
Enqueue List:
(unsorted)
30 777
Next . Next f.
55
••• • ••
Next +
123 388
Next ~ Next
Dequeue List:
(sorted)
101 90
Next . Next ~
12
••• ••• Next +
8 99
Next f+ Next
Figure 9. SPEEDESQ Data Structure
In the design ofthe SPEEDESQ simulation, the sizes ofthe Ii st increased from 10
to 50,000 and for each queue size, the operations repeat 100,000 times to calculate the
average. Two linked list data structures are set up: enqueuelinked list and dequeuelinked
list. Two global variables are declared to record the highest priority of both the
linked lists. The enqueue operation is performed by enquToLst ( ) function, in which the
new element is directly inserted to the enqueue linked list without comparison and
sorting. Each time the enqueue operation is performed, the highest priority variable is
updated by comparing with the new element. The dequeue operation is performed by
dequFrmLst 0 function that is much more complicated. In the dequeue operation, the
head of the linked list needs to be compared with the highest priority variable. If the
25
element is larger dequeue the element from the list. Ifthe element is smaller then sort the
enqueue list and then merge the two linked lists (See Figure 10).
SPEEDESQ
YES
Sort enqueue list
&
Add sorted euqueue
list to dequeu list
Figure to. SPEEDESQ Flow Chart
26
No
CBAPTERIV
EVALUATION
4.1 Program
The program simulated the performances ofthe Implicit Binary Heap, the Median
Pointer Linked List, and the SPEEDESQ. For each priority queue, the Classic Hold,
Up/Down Model and Markov Hold were used as the access patterns. Figure 11 shows the
flow chart of the simulation program.
The results are produced when the program terminates, which are used to
comparatively study and analyze the priority queues and three access patterns as well.
27
Initialize experiment
enviroment for Implicit
Binary Heap
Classic Hold
experiment
Up/Down Hold
experiment
Random Access
experiment
Initialize experiment
enviroment for Median
Pointer Linked List
Classic Hold
experiment
Up/Down Hold
experiment
Random Access
experiment
Initialize experiment
enviroment for
SPEEDESQ
Classic Hold
experiment
Up/Down Hold
experiment
Random Access
experiment
End
Figure 11. The Simulation Program Flow Chart
28
4.2 Performance of the Three Priority Queues
MeEf'l Access TIme
(us)
Implicit Binlry Heep
30
20
15
10
5
• 100 1000 10000
'·brio.,
·Cludc
      UplDown
100000
Queue Size (IogN)
Figure 12. Implicit Binary Heap with Classic Hold, UplDown and Markov Hold
MeasuredTimel
ExpectedTime
Implicit Binary Heap with Markov
(Approx. Fit: y II O.3BBLogX.
1.8
1.5
1.2
0.9
0.6
03
o
סס 10 100 1000 1 oo 10 סס oo
Queue Size
Figure 13. Empirical Behavior at Large N of the Binary Heap with Markov Hold
29

Figure 12 depicts the performance of the Implicit Binary Heap with the three
models. As expected, the Implicit Binary Heap exhibits O(logN) performance.
Figures 13 shows the performance of the Implicit Binary Heap with yaxis
standing for the (measured time)/(expected time) and xaxis for log (N). I derived from
the results of the figure12 the expected time ofthe Implicit Binary Heap for each hold,
i.e. y= O.29810g(X) for the Classic Hold, Y=0.4810g(X) for the Up/Down model and Y=
O.388Iog(X) for the Markov Hold respectively. From the graph, we find that when the
queue size increases, the (measured time) /(expected time) of the Implicit Binary Heap
approaches to a horizontal line. Therefore, we can get the conclusion that the Implicit
Binary Heap shows average 0 (logN) running time for each hold.
Medi.n Pointer Linked List
,~ upmown I
I Markov : i .._ CI ••ic I
_ ..
100000
Queue Size (LogN)
100 1000 10000
1 .
10
10
100
1000
Mean Access Time
(us)
10000
Figure 14. The Median Pointer Linked List with Classic Hold, UplDown and
Markov Hold
30
Median Pointer Linked Ust with Markov
(Approx. Fit: Y=O.111X)
MeasuredTimeJ
ElCpeCtedTime
1.8
1.5
1.2
0.9
0.6
0.3
סס 1 oo 2 סס oo 30000 40000 50000 60000 7 סס oo
Queue Size
Figure 15. Empirical Behavior at Large N of the Median Pointer Linked List
with Markov Hold
For the Median Pointer Linked List, an enqueue operation can be done either from
the front or the back of the list It means that the enqueue operation only searches half of
the list to find the correct insertion location, the average and worst case time complexities
are therefore (+N) and ( t N) respectively. The dequeue operation time complexity is
0(1), since the highest priority is always in the head of the list. From the figure 14 we
can find that the mean access time of the Median Pointer Linked List grows linearly with
the increase ofelements in the queue. With the very small queue size (less than 30), the
Median Pointer Linked List performs very well. From the result of the experiment, I got
the expected time of the list for each hold. They are Y=O.116X for the Up/Down model,
Y=O.lOIX for the Classic Hold and Y=O.lllX for the Markov Hold. Figure 15 shows
3l

the (measured time/expected time) performance ofthe Median Pointer Linked List with
Markov Hold. The graph shows that when queue size (xaxis) increases a certain amount,
the value ofthe (measured time)1 (expected time) approaches to a horizontal line. This
proves that the mean access time of the Median Pointer Linked List grows linearly with
the increase ofthe queue size.
Mean Access Time
(us)
100000
10000
1000
100
10
1
10 100
SPEEOESQ
1000 10000
     UplUown
Markov
   Cla••ic
100000
Queue Size
Figure 16. SPEEDESQ with Classic Hold, UplDown and Markov Hold
Figure 16 shows the performance of the SPEEDESQ with three holds. Like the
Median Pointer Linked List, the SPEEDESQ also performs very well for small queue
size. The SPEEDESQ consists oftwo linked lists. One is an enqueue list that is unsorted,
so the enqueue operation simply inserts an element at the end ofthe enqueue list, which
costs 0(1) time complexity. The other linked list is a dequeue list that is sorted. The
dequeue operation depends on the location of the highest priority element. When the
32

highest priority element is present in the dequeue list, which is located in the head of the
dequeue list, the dequeue operation just deletes the head costing O( 1) running time,
otherwise, it takes O(NlogN) worstcase time complexity to sort and merge the two
linked lists.
MeasuredTimel
ExpectedTIme
1.6
1.2
0.8
0.4
SPEEDESQ with Mar1(ov
(Approx. Fit: Yo.30X)
סס 1 oo 2O<XXl 30000 40000 50000 60000
Queue Size
Figure 17. Empirical Behavior at Large N of the SPEEDESQ with the
Markov Hold
The expected time of the three holds are Y=O.273X for Classic Hold, Y=0.324X
for UplDown and Y=O.30X for Markov Hold respectively. Figure 17 shows the
(measured time) I (expected time) of the SPEEDESQ with Markov Hold. We find that
the graph is a horizontal line. Therefore, we can prove that the performances of the
SPEEDESQ grow linearly with the increase of queue size.
33

Mean Access Time For Three Priority Queues
Me~1lI Access
Time (us)
100000
10000
1000
100
10
1
10 100 1000 10000 100000
Implicit Binary Heap
Median Linked List
     SPEEDESQ
Figure 18. The Performances of the Three Priority Queues with Markov Hold
Figure 18 depicts the performance ofthe three priority queues with Markov Hold
on one graph. We can clearly see the differences among the three priority queues. As
expected, the Implicit Binary Heap exhibits 0 (log N) performance. We also noticed that
both Median Pointer Linked List and SPEEDESQ perform very well when the queue size
less than 30, however they can not compete with the Implicit Binary Heap when the
queue size larger than so.
34

CHAPTER V
CONCLUSION
In this thesis, I presented the performances for a detailed study of three priority
queue algorithms. Three different access patterns (Classic Hold, UplDown, Markov
Hold) were used to measure the mean access time. Having attempted to obtain a
comparative ranking ofthe three priority queues algorithms, we find that we are unable to
recommend anyone particular algorithm as being the best to use in all situations. All
these queues have some weak and strong points. However, the approach to arriving at the
conclusion has given readers some insight into methods for making the choice.
We note that Median Pointer Linked List and SPEEDESQ show good
performance for queue sizes smaller than 30 elements on average. We also find that the
mean access time of the SPEEDESQ is almost twice as much as the Median Pointer
Linked List. This is because searching an element in the sorted linked list of the Median
Pointer Linked List takes (±N) on average whereas for the SPEEDESQ, it takes 0 ( t N)
on average. The dequeue operation for the Median Pointer Linked List always takes 0(1)
time. The enqueue operation for SPEEDESQ always takes 0 (1) and dequeue operation
also takes a (1) time if the merge is not necessary at this point. The Median Pointer
Linked List can be used for the application that requests 0 (I) time complexity of the
dequeue operation. The SPEEDESQ can be used for the application that requests the
running time of the enqueue operation to be 0 (]) without concerning the worst case of
35
dequeue operation. SPEEDESQ is weU suited for implementation on parallel machines
because of its parallel sublists.
The Implicit Binary Heap is the only choice among the three queues that gives
guaranteed performance. In fact, from the results, we find that the mean access time of
Implicit Binary Heap performs so well that the other two linked lists can not compete
with it when the queue size bigger than 50.
The results show that the standard Classic Hold yields results that correspond
closely to the Markov Hold experiments. The Markov Hold model has been suggested as
a generalization of the Classic Hold model. It allows random access patterns that could
better mimic the behavior ofreal simulations. It has been claimed that this capability
could reveal more information on the performance of priority queues. When comparing
among the results obtained using the Classic Hold, UplDown and Markov Hold, we draw
the following conclusions. The Classic Hold and the Up/Down models represent two
extreme cases. When the queue size remains nearly constant, the Classic Hold model
gives as accurate and informative results as the more random access patterns generated
by the Markov Hold Model. For changing queue sizes, the simple Up/Down access
pattern often gives sufficient information. The simplicity of the Classic Hold and the
Up/Down helps reveal more and clearer information on the dependencies ofqueue sizes
on the performance.
36
LITERATURE CITED
Aho, AY., Hopcroft, 1. E. and Ullman, 1. D., The Design and Analysis ofComputer
Algorithms, AddisonWesley, Reading, Mass, 1974;
Ayanne, R., "LRalgorithm: Concurrent operations on priority queues", Proceedings of
the Second IEEE Symposium on Parallel and Distributed Systems, pp. 2225, 1990;
Deldler, 1., "Priority Queue", Data Structures and Algorithms, pp. 243244, 1996;
Brown, R., "Calendar queues: A fast a (1) priority queue implementation for the
simulation event set problem", Commun.ACM 31, 10 (Oct.), pp, 12201227, 1988;
Chung, K., Sang, J. and Rego, v., "A performance comparison of event calendar
algorithms: An empirical approach", Softw. Pract. Exper, 23. 10 (Oct.), pp. 11071138,
1993;
Choi, B. D., "Priority queue with twostate Markovmodulated arrivals", IEEE
Proceedings. Communications V. 145. No 3, 6 (June), pp. 152159, 1998,
Floyd, R.W., "Algorithm 245, Tree sort 3", Corom. ACM 7 (1964), pp. 701, 1964;
37
Fujimoto, R., "Parallel discrete event simulation", Commun.ACM 33, 10 (Oct.), pp. 3153,
1990;
Gston, Gonnet, R. and Munro, 1., "Heaps on Heaps", SlAM 1. Comput. Vol. 15 No.4,
pp. 965971, 1986;
Gonnet, G.R., A Handbook of Algorithms and Data Structures, AddisonWesley,
Reading, MA, 1984;
Henriksen, 1. 0, "An improved events list algorithms", Proceedings ofthe 1977 Winter
Simulation Conference, pp. 547557, 1988;
Horowitz, E., Sahui, S. and Sanguthevar, R, Computer AlgorithmiC, 1996;
Knowlton and Kenneth, c., L6: Bell Telephone Laboratories LowLevel Linked List
Language, 1966;
Knuth, D.E., "Sorting and Searching", The Art of Computer Programming,VoI.3., 1973;
McCormack, W. M. and Sargent, R. G., "Analysis of future event set algorithms for
discrete event simulation", Commun.ACM 24, 12 (Dec.), pp. 801812, 198];
38
Munro, J.I. and Suwanda, H., "Implicit data structures for fast search and update",
Compu!. System Sci, 21 (1980), pp. 236250,1980;
Naor, D., Martel, c.u. and Matloff, N.S., "Performance ofPriority Queue Structures in a
Virtual Memory Environment", The Computer JournaL Vol. 34, No.5, pp. 1428437,
1991 ;
Pugh, W., "Skip lists: A probabilistic alternative to balanced trees", Commun. ACM 33,
6 (June), pp. 668676, 1990;
Ronngren, R., Ayani, R., Fujimoto, R. M. and Das, SR., "Efficient implementation of
event sets in time warp", In Proceedings of the Seventh Workshop on Parallel and
Distributed Simulation (PADS'93), pp. 101108, 1993;
Steinman, I S, "SPEEDES: A unified approach to parallel simulation", In PI e
of the Sixth Workshop on Parallel and Distributed Simulation, pp. 7584, 1982;
Weiss, M. A., Data Structures and Algorithm Analysis in C, ]993;
Williams,lW.J., "Algorithm 23: Heapsort", Corom. ACM, 7(1964), pp. 347348, 1964.
39
dVITA
DONGHONG WEI
Candidate for the Degree of
Master of Science
Dissertation: COMPARATIVE STUDY OF PRIORITY QUEUES
MPLEMENTATION
Major field: Computer Science
Biographical:
Personal Data: Born in Tangshan, Hebei, P.R.China, July 26, 1967, the daughter of
Shuren Wei and Shuzhen Ma.
Education. Graduated from 30th High School ofTaiyuan, Taiyuan, Shanxi, China,
July 1985; received Bachelor of Arts degree in Foreign Languages from
Shanxi University, Taiyuan, Shanxi, China, July 1990; completed the
requirements for the Master of Science degree at Oklahoma State
University in December, 1999.