C++ priority_queue and the top-k pattern

Before you start

C++ containers and comparators.

Use a binary heap to get the smallest element quickly, and keep the k largest values of a stream.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

std::priority_queue is a binary heap adaptor. By default it is a max-heap: top returns the largest element. push and pop take O(log n) and top takes O(1). To get a min-heap, give it std::greater<int> as the comparison and std::vector<int> as the underlying container.

To find the k largest values among n, keep a min-heap of size k. Each new value is pushed, and if the heap has more than k elements, the smallest is popped. At the end the heap holds the k largest. This takes O(n log k) time and O(k) memory, which is better than sorting everything when k is small and the data is a stream.

Code example

C++

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
  std::priority_queue<int> max_heap;
  for (int v : {5, 1, 8, 3, 9, 2}) {
    max_heap.push(v);
  }
  std::cout << "largest first:";
  while (!max_heap.empty()) {
    std::cout << " " << max_heap.top();
    max_heap.pop();
  }
  std::cout << "\n";

  std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
  for (int v : {5, 1, 8, 3}) {
    min_heap.push(v);
  }
  std::cout << "smallest: " << min_heap.top() << "\n";

  const std::size_t k = 3;
  std::priority_queue<int, std::vector<int>, std::greater<int>> top;
  for (int v : {7, 12, 3, 19, 5, 11, 2, 15}) {
    top.push(v);
    if (top.size() > k) {
      top.pop();
    }
  }
  std::vector<int> result;
  while (!top.empty()) {
    result.push_back(top.top());
    top.pop();
  }
  std::cout << "top 3 ascending:";
  for (int v : result) std::cout << " " << v;
  std::cout << "\n";
}

Output

largest first: 9 8 5 3 2 1
smallest: 1
top 3 ascending: 12 15 19

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <functional>

2#include <iostream>

3#include <queue>

4#include <vector>

6int main() {

7 std::priority_queue<int> max_heap;

8 for (int v : {5, 1, 8, 3, 9, 2}) {

9 max_heap.push(v);

10 }

11 std::cout << "largest first:";

12 while (!max_heap.empty()) {

13 std::cout << " " << max_heap.top();

14 max_heap.pop();

15 }

16 std::cout << "\n";

18 std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

19 for (int v : {5, 1, 8, 3}) {

20 min_heap.push(v);

21 }

22 std::cout << "smallest: " << min_heap.top() << "\n";

24 const std::size_t k = 3;

25 std::priority_queue<int, std::vector<int>, std::greater<int>> top;

26 for (int v : {7, 12, 3, 19, 5, 11, 2, 15}) {

27 top.push(v);

28 if (top.size() > k) {

29 top.pop();

30 }

31 }

32 std::vector<int> result;

33 while (!top.empty()) {

34 result.push_back(top.top());

35 top.pop();

36 }

37 std::cout << "top 3 ascending:";

38 for (int v : result) std::cout << " " << v;

39 std::cout << "\n";

40}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
The default is a max-heap.	`—`	—
Reading top and popping repeatedly returns the values from largest to smallest.	`—`	—
std::greater reverses the order, giving a min-heap.	`—`	—
The smallest of 5, 1, 8, 3 is on top.	`—`	largest first: 9 8 5 3 2 1 smallest: 1
When more than k values are held, the smallest is dropped, since it cannot be among the k largest.	`—`	largest first: 9 8 5 3 2 1 smallest: 1
Draining the heap returns the 3 survivors in ascending order: 12, 15, 19.	`—`	largest first: 9 8 5 3 2 1 smallest: 1 top 3 ascending: 12 15 19

Behind the scenes

How C++ processes this code

The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.

Cost and common mistakes

push and pop O(log n), top O(1). The top-k method is O(n log k).

priority_queue has no iteration and no way to change a priority. To update a priority, push a new entry and ignore the stale one later.
Calling top or pop on an empty queue is undefined behaviour. Check empty() first.
The comparison is inverted compared with sort: with the default std::less the largest element has the highest priority.

Try it yourself

How would you store (distance, node) pairs with the smallest distance first?

Reveal answer and reasoning

Use std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>, std::greater<>>; pairs compare by the first element first.