The Art of Multiprocessor Programming, Revised Reprint

15

Priority Queues

15.1 Introduction

A priority queue is a multiset of items, where each item has an associated priority, a score that indicates its importance (by convention, smaller scores are more important, indicating a higher priority). A priority queue typically provides an add() method to add an item to the set, and a removeMin() method to remove and return the item of minimal score (highest priority). Priority queues appear everywhere from high-level applications to low-level operating system kernels.

A bounded-range priority queue is one where each item’s score is taken from a discrete set of items, while an unbounded-range priority queue is one where scores are taken from a very large set, say 32-bit integers, or floating-point values. ...