Priority Queues

Priority Queues
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Motivation

An Observation:
- In some queueing applications, elements are not ordered based on when they arrive but on their priority
A Relevant ADT:
- The Priority Queue

The Priority Queue ADT

PriorityQueue

Values: Elements of any type.

Operations:

Name/Operator Arguments Returns

Constructor A new instance.

dequeue The element with highest priority

enqueue

	`element`	The element to add to the priority queue
	`priority`	The priority of the element

Possible Implementations

A Collection of Queues:
- Works well if you know all of the priorities and they are integer-valued
A d-Heap:
- Works well in general