An Empirical Comparison of Priority-Queue and Event-Set Implementations

Jones, Douglas W.

Abstract

This collection of algorithms was the basis of the paper An Empirical Comparison of Priority Queue and Event Set Implementations in Communications of the ACM, 29, April 1986, pages 300-311. This paper was the first to show the speed and stability of the splay-tree data structure. The following data structures are included here: Linear linked list, leftist trees, Blackstone's two-list structure, implicit heaps, Henriksen's indexed list, binomial queues, pagodas, bottom-up skew heaps, top-down skew heaps, splay trees, and pairing heaps.

Keywords

splay tree
event
discrete event

Notes

Splay tree

Related Papers

Bibtex

 @ARTICLE {jones_queue86,
   author = {Douglas W. Jones},
    title = {An Empirical Comparison of Priority-Queue and Event-Set Implementations},
  journal = {Comm. ACM},
   volume = {29},
    pages = {300 -- 311},
    month = {April},
     year = {1986}
}
Back to Intro By Author By Importance By Keyword By Title By Reference