Access Restriction

Author Goh, Rick Siow Mong ♦ Thng, Ian Li-Jin
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2004
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Algorithm analysis ♦ Henriksen's ♦ Calendar queue ♦ Discrete event simulation ♦ Future event list ♦ Pending event set ♦ Priority queue ♦ Simulator ♦ Skew heap ♦ Splay tree ♦ Tree
Abstract Priority queues are essential function blocks in numerous applications such as discrete event simulations. This paper describes and exemplifies the ease of obtaining high performance priority queues using a two-tier list-based structure. This new implementation, called the $\textit{Twol}$ structure, is amalgamated with three priority queues, namely, the Henriksen's queue, splay tree and skew heap, to enhance the efficiency of these $\textit{basal}$ priority queue structures. Using a model that combines traditional average case and amortized complexity analysis, Twol-amalgamated priority queues that maintain $\textit{N}$ active events are theoretically proven to offer O(1) expected amortized complexity under reasonable assumptions. They are also demonstrated empirically to offer stable near O(1) performance for widely varying priority increment distributions and for queue sizes ranging from 10 to 10 million. Extensive empirical results show that the Twol-amalgamated priority queues consistently outperform those basal structures (i.e., without the Twol structure) with an average speedup of about three to five times on widely different hardware architectures. These results provide testimony that the Twol-amalgamated priority queues are suitable for implementation in sizeable application scenarios such as, but not limited to, large-scale discrete event simulation.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2004-12-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 9

Open content in new tab

   Open content in new tab
Source: ACM Digital Library