ISSN:
1572-9125
Keywords:
algorithm analysis
;
binary trees
;
priority queues
;
event scheduling
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A special kind of priority queue structure, priority trees (p-trees), and an algorithm for building such trees are investigated. The main part of the paper is devoted to a mathematical analysis of the algorithm showing that the expected number of key comparisons to insert a “random” element into a “random”p-tree withn nodes isO((logn)2). Also some practical experiments, comparing different types of priority queue strategies, are presented.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01931680
Permalink