Comparison and analysis of some algorithms for implementing priority queues
Loading...
Authors
Goksel, Alinur
Subjects
Priority queue
Analysis of algorithms
Worst case analysis
Heap
K-ary tree
Single linked-list
Leftist tree
Linked tree
AVL-tree
2-3 tree
Fixed priority
Analysis of algorithms
Worst case analysis
Heap
K-ary tree
Single linked-list
Leftist tree
Linked tree
AVL-tree
2-3 tree
Fixed priority
Advisors
Smith, Douglas R.
Date of Issue
1980-06
Date
June 1980
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
A priority queue is a data structure for maintaining a collection of items, each having an associated key, such that the item with the largest key is easily accessible. Priority queues are implemented by using heap, k-ary tree, single linked-list, leftist tree, linked tree, AVL-tree, 2-3 tree, and fixed priority property. Required storage for each method was obtained and the worst case time analysis was done in terms of the number of key comparison and key exchanges during the insertion and deletion process. Finally, each of these methods were run on PIP-11 UNIX TIME SEARING SYSTEM at NPS using different random number generators to get the average CPU times for insertion and deletion process.
Type
Thesis
Description
Series/Report No
Department
Computer Science
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funding
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
Copyright is reserved by the copyright owner