Priority Queues

A Bunch of Interfaces We Can Support

Linear Data Structures (supported by array-backed lists or linked lists)

• Stack
  • First-in, last-out.
  • Like (ideal) plane boarding: the first people to board are at the back, and therefore are also the last to leave.
• Queue
  • First-in, first-out.
  • Like a bank: first customer in line gets served first.
• Steque
  • Add to either end, take only from the front.
  • Like the milk refrigerator at the grocery store. Employees put milk in from the back. At the front, customers can take milk, and put it back if they change their minds.
• Deque
  • Add to and remove from either end.
  • Like a freight train: you can attach/detach cars on either end, but not in the middle.
• List
  • Stores items in a linear order. Allows access/insertion/removal at any position.
  • Like a… list of things.

Associative Containers (supported by BSTs or hash tables)

• Set
  • Stores unique keys, not necessarily in any order.
  • Supports insert/lookup/remove of any key.
• Map
  • Associates unique keys with values (not necessarily unique).
  • Supports looking up the value associated with a key, and inserting/removing key/value pairs.
  • (Example: Python dictionary)
• Multiset
  • Pretty much like a set, but allows duplicate keys.
• Multimap
  • Pretty much like a map, but allows duplicate keys, each with their own value.

New Interface: Priority Queue

Let's recap some sequences we know about that let us add and remove items in a specific order.

• Stack — We remove the newest item (like the plate dispensers in the dining hall; plates are added and removed from the top of the stack).
• Queue — We remove the oldest item (like the line for the Exhibition Grill in the dining hall—the person waiting longest gets served next)

Now, with a Priority Queue, we remove the highest priority item (like waiting for a table in a fancy LA restaurant, where “more important people” keep getting seated ahead of you).

Specifically,

• Every item is inserted with a ordered key (e.g., a priority).
  • We can decide whether higher or lower values are more important.
  • For our discussion, we'll treat lesser values as more important (i.e., priority 1 is more important than priority 5).
• Main operations:
  • INSERT — Add a new item with a given key.
  • GET-MIN — Return the item with smallest key (equal keys come out in arbitrary order).
  • POP-MIN — Remove the item with the smallest key.

Say we have the following code:

PriorityQueue pq;
pq.insert("First", 5); // Item, key
pq.insert("Second", 3);
pq.insert("Third", 10);

for (size_t i = 0; i < 3; ++i) {
    cout << pq.getMin() << " ";
    pq.popMin();
}

It will be “Second First Third”, because “Second” has the smallest key, 3; “First” has the next smallest, 5; and “Third” has the largest, 10.

What Are Priority Queues For?

We won't have time in CS 70 to deeply study the many applications of priority queues, but if you continue to study CS, you will surely come across some of them!

One particularly important use of priority queues is in algorithms for the shortest-path problem: find the shortest path between two vertices on a weighted graph. A priority queue is often used to keep track of (and give easy access to) the shortest paths found so far. The shortest-path problem sits at the foundation of approaches to many real-world problems, including routing of Internet traffic, automated driving directions, pathfinding in video games, natural-language parsing, and many others.

Priority queues are also important for Huffman codes (a foundational data-compression technique), load-balancing jobs on a cluster of servers, and, as we will see, can be used to implement a cool sorting algorithm.

(When logged in, completion status appears here.)