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 queue

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;

priority queue

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);

priority queue

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.

priority queue

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.

This document and its content are copyright © Marty Stepp, 2017. All rights reserved. Any redistribution, reproduction, transmission, or storage of part or all of the contents in any form is prohibited without the authors' expressed written permission.