Heaps and Priority Queues in C++ – Part 3: Queues and Priority Queues

Published March 20, 2018 - 3 Comments

Heaps, that we saw how to manipulate with the STL, are in a close relationship with queues and priority queues.

Let’s what those structures are, how to manipulate them in C++ and what the link between all this is.

This is Part 3 in our series about heaps and priority queues:

Part 1: Heaps Basics
Part 2: Building, Unbuilding and Sorting Heaps (video)
Part 3: Queues, Priority Queues and Heaps
Part 4: What Heaps Brings That Priority Queues Don’t (video)

Queues: wait your turn

A queue is a structure to which you can add successive pieces of data, and retrieve them in the order that you put them.

It’s called a queue as in when you queue up in the line at the supermarket: people get out of the queue in the same order as they got in.

queue C++

To represent a queue in C++ you can use std::queue from the <queue> header, that wraps another container and exposes the interface of a queue that is, essentially:

push: add a new element to the queue,
pop: remove the oldest element of the queue,
front: access the the oldest element of the queue,
back: access to the newest element of the queue.

To remember which of front or back gives access to the oldest or newest element of the queue, you can think of it this way: “one gets in at the back of the queue”. Like at the supermarket:

queue

Here is a snippet of code with the state of the queue in comment at each line:

#include <iostream>
#include <queue>

std::queue<int> numbers;

numbers.push(1); // queue contains: 1
numbers.push(2); // queue contains: 2 1
numbers.push(3); // queue contains: 3 2 1
numbers.push(4); // queue contains: 4 3 2 1

std::cout << numbers.front() << '\n'; // prints 1
std::cout << numbers.back() << '\n'; // prints 4

numbers.pop(); // queue contains: 4 3 2

std::cout << numbers.front() << '\n'; // prints 2
std::cout << numbers.back() << '\n'; // prints 4

The underlying container of a queue is a std::deque by default, because it offers both a push_back and a pop_front interface. So std::queue contains a std::deque and uses its methods to expose the interface of a queue.

Note that accessing front and back is in constant time, and that you cannot access the other elements of the queue. In particular, the queue does not offer a begin/end interface like the other STL containers such as std::vector do.

So if you must access the entire queue at a given time, in order to display it for example, std::queue is not the right container. You will have to use a std::deque or a std::vector that offers a richer (but less targeted) interface.

When are queues useful? An example is when doing an inorder traversal of a tree, or a breadth-first search traversal of a graph. More on those in later posts.

Priority queues: jump the line

A priority queue is a queue that does not have the “first in, first out” logic.

In a priority queue, you can add successive pieces of data and retrieve the one that has the “highest priority” in constant time.

So to implement a priority queue, you also need a comparison between its elements to determine which one has the “highest priority”.

In C++ you can use std::priority_queue that wraps another container (by default, std::vector). std::priority_queue uses operator< by default (via the function object std::less) to compare the elements. So the element of highest priority is the largest one.

std::priority_queue also accepts a custom comparator to replace std::less. For instance you could use std::greater so that the element of highest priority is the smallest one. Or you could also use a custom comparator, to compare the keys of the elements for example, or to compare user defined types.

std::priority_queue offers the interface of a priority queue, which is:

push: add a new element to the queue,
pop: remove the largest element of the queue,
top: access the largest element of the queue.

Note the difference with the interface of a simple queue: the priority queue does not give access to the element most recently inserted (the equivalent of back in the queue). Instead, the elements get swallowed up by the priority queue, and it only spits out the top element.

priority_queue

When are priority queues useful? One example is to process incoming events that have various priorities. You want to process the events according to their priority, and not according to their order of arrival.

The link between heaps and priority queues

When reading about priority queues, didn’t their ability to retrieve the largest element reminded you of something?

Heaps, of course!

max heap C++ STL

Indeed, in heaps basics we saw that they offer an easy access to the largest elements, by positioning it at their root.

In fact, the relationship between heaps and priority queues is even closer than that: heaps are an implementation of priority queues.

Indeed, in a heap we can add data, and access and remove the largest element, so they can implement the interface of a priority queue. Let’s see this in more details.

Let’s consider the following heap (implemented as an array):

std::vector<double> numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

std::make_heap(begin(numbers), end(numbers));

// numbers is now {9, 8, 6, 7, 4, 5, 2, 0, 3, 1}

If the above is not crystal clear, maybe you want to have a look at Part 1 Heaps Basic.

Let’s see how to perform the main functions of the interface of a priority queue with the STL algorithms on heaps.

Adding an element

In a priority queue we need to be able to add an element with the push method.

Let’s add the new element 4.12. Here is how to do it by using the STL algorithms on heap:

numbers.push_back(4.12);
std::push_heap(begin(numbers), end(numbers));

Printing out the contents of the heaps gives:

9 8 6 7 4.12 5 2 0 3 1 4

Accessing the largest element

In a priority queue, we need to access the largest element with the top method. It is located at the beginning of the array and can be accessed in constant time with:

numbers.front()

which returns 9 here.

Removing the largest element

Finally, a priority queue needs to be able to remove its largest element with its pop method. The algorithm pop_heap moves the first element of the array to its end and rearranges the other elements into a heap:

std::pop_heap(begin(numbers), end(numbers)); // 9 is at the end
numbers.pop_back(); // 9 is gone, 8 is the new top

Printing out the elements of the heap now gives:

8 7 6 4 4.12 5 2 0 3 1

Notice how 8, which was the second largest element, has now taken the position of the largest element at the beginning.

To sum this all up:

Priority queues can be implemented by heaps, and heaps can be implemented by arrays.

Why bother with the heaps?

Now that we’ve seen how to implement the interface of a queue with the STL algorithms on heaps, you may wonder: why not just use the interface of std::priority_queue and be done with it?

Using push, pop and top is simpler than calling the algorithms on heaps and the methods on std::vector, isn’t it? Plus, by exposing the whole range, there is a risk of messing up with the order of the element, and breaking the heap property.

So why? Why the heaps?

This is what we delve in in Part 4 of heaps and priority queues in C++: What heaps bring that priority queues don’t.