The Analysis of a Practical and Nearly Optimal Priority Queue.

Abstract

The properties of the binomial queue, a new data structure for implementing priority queues that can be efficiency merged are explored in detail. New methods of representing binomial queues are given which reduce the storage overhead of the structure and increase the efficiency of operations on it. One of these representations allows any element of an unknown priority queue to be deleted in log time, using only two pointers per element of the queue. A complete analysis of the average time for insertion into and deletion from a binomial queue is performed. This analysis is based on the result that the distribution obtained after repeated insertions and deletions.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1977
Accession Number
ADA040538

Entities

People

  • Mark R. Brown

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I
  • Energy and Power Technologies
  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Air
  • Artificial Intelligence
  • Buses
  • Computer Programming
  • Computer Science
  • Computers
  • Construction
  • Costs
  • Inserts
  • Language
  • Numbers
  • Operating Systems
  • Programming Languages
  • Tensile Strength
  • Tin
  • Trees (Data Structures)

Readers

  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.
  • Systems Analysis and Design