Comparison and Analysis of Some Algorithms for Implementing Priority Queues

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 key comparisons and key exchanges during the insertion and deletion process. Finally, each of these methods were run on PDP-11 UNIX TIME SHARING SYSTEM at NPS using different random number generators to get the average CPU time for insertion and deletion process.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1980
Accession Number
ADA090095

Entities

People

  • Alinur Goksel

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computer Science
  • Computers
  • Lists (Data Structures)
  • Nodes
  • Notation
  • Plastic Explosives
  • Random Number Generators
  • Rotation
  • Sequences
  • Technical Information Centers
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Database Systems and Applications
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.