CS 106B: Programming Abstractions (C++), Autumn 2015

Lecture Preview: Priority Queues

(Suggested book reading: Programming Abstractions in C++, Chapter 16 section 16.5)

Today we'll learn about a new abstract data type (ADT) or collection called a priority queue. A priority queue is like a regular queue, except that the elements are enqueued with a given "priority" number attached to each one. When you dequeue an element later, the element with the lowest number as its priority (considered to be the most "urgent" element) is the one that is removed from the queue and returned.

Priority queues are useful for many applications such as scheduling jobs in an operating system, printer job queues, prioritizing paths to explore in a maze, AI algorithms, games, and more.

Priority queues are represented in the Stanford C++ library by the class PriorityQueue, defined in pqueue.h. Here is a short example of code that uses a priority queue:

PriorityQueue<string> faculty;
faculty.enqueue("Marty", 5);     // low priority
faculty.enqueue("Eric", 2);      // high priority
faculty.enqueue("Cynthia", 4);
faculty.enqueue("Mehran", 3);
while (!faculty.isEmpty()) {
    cout << faculty.dequeue() << endl;   // Eric Mehran Cynthia Marty
}

An efficient way to implement a priority queue is using an array structure named a heap where the elements are arranged in a particular way. Each element at index i is thought of as being a "parent" that has two "children". The children are located at indexes 2*i and 2*i + 1. The idea of a heap is to store the data in such a way that parents always have lower or equal priorities than those of their children. For example, in the figure below, the value at index 1 has lower priority than its children at indexes 2 and 3;

When you want to enqueue (add) a new element to a priority queue, you first place it at the end of the array.

pq.enqueue("k", 1);

Next, you look at the newly added element's parent (the index half as large). While the element is out-of-order with respect to its parent, you swap them (called "bubbling up") the element. The figures below illustrate the process.

The reason for bubbling up elements is to ensure that the lower priority elements are kept toward the front of the array, so that operations like peek and dequeue will be very efficient. We will discuss priority queues in much more detail in lecture, as well as implementing priority queues for ourselves as our next homework assignment.