Priority Queue

Info

A priority queue is a queue which is sorted by priority

Think of it like a queue (line) for a roller coaster. First person in line will ride first, last person in line will ride last. BUT if someone has a fast pass, they will be given priority. The first person in the fast lane will ride first, the last person in the fast lane will be the last one in the fast lane to ride, but will ride before the first person in the normal line.

List of Lists (LOL) Implementation

See Linked List

Figure

Complexities ( elements, distinct priorities):

Enter:
Leave:
First:

Heap Implementation

See Heap.

Each element is ordered by priority. Duplicate priorities are treated the same, and will remain in order.

Complexities ( elements, distinct priorities):

Enter:
Leave:
First:

Heap is better choice unless there are very few priorities