University of California, Santa Cruz

Prof. Paulo Franca - Spring 2000

Introduction

Syllabus

Guidelines for labs

Lab sections

Take quiz & check grades

Priority Queue

A priority queue is an abstract type so that you can insert and remove items.

bulletEach item or record contains a field that determines the priority of that record
bulletYou always remove the item with the highest priority
bulletIn some situations the priority is expressed in increasing order, so you remove the item with the lowest priority value.

Uses of priority queues:

bulletTask scheduling: always schedule task with highest priority
bulletSimulation: Examine the event that will happen first

What is involved?

Keep records sorted by priority:

bulletlinear array - slow insertion, slow removal
bulletlinked list - slow insertion, fast removal
bulletheap - good insertion and removal