priority_queue and heap sort

Why this matters

In the last lesson you wrote your own min-heap, so you know what happens inside a push and a pop. In real code you rarely write one from scratch. C++ ships a ready-made heap in the standard library, called std::priority_queue, and nearly every interview answer that uses a heap uses it. You need to know its exact behaviour, including the surprises that catch beginners: the default is a max-heap, pop returns nothing, and top on an empty queue is undefined.

This lesson has two goals. The first is to make you fluent with priority_queue: writing min-heaps, storing structs with a custom order, and using pairs as priorities. The second is to show heap sort, which is the classic use of a heap for sorting. You will see two versions of heap sort. One uses a priority_queue and an extra array. The other sorts inside the array you already have, with no extra space, and it is the version interviewers ask you to write.

You do not need to remember the details of the last lesson to follow this one, but it helps to remember the three operations: push, pop and top. Each one touches a path in the tree, so each costs about log n steps.

What a priority queue is

A queue is a line where the first item in is the first item out. A priority queue is a line where the most important item comes out first, no matter when it arrived. A hospital emergency room works this way. A patient who arrived early with a minor cut waits behind a patient who arrived later with a heart attack. The line is ordered by urgency, not by arrival.

A priority queue has three basic operations:

• push(x) adds an item.
• top() returns the most important item without removing it.
• pop() removes the most important item.

A heap is the most common way to build a priority queue. The most important item sits at the root, so top costs O(1), and push and pop cost O(log n). That is why the names are used together: a heap is one way to build a priority queue, and priority_queue is the C++ name for that container.

The default is a max-heap

Here is the first declaration to learn:

#include <queue>
priority_queue<int> pq;

With no extra arguments, priority_queue<int> is a max-heap. The largest value has the highest priority, so top returns the largest item. Beginners often expect the smallest, so remember this default.

The full declaration has three parts: the element type, the container that stores the elements, and the comparison that decides the order. The defaults are vector<int> and less<int>:

priority_queue<int, vector<int>, less<int>> pq;   // same as priority_queue<int>

The comparison less<int> says that a has lower priority than b when a < b. So the greatest value, meaning the one with the highest priority, is at the top. That is the max-heap.

A min-heap with greater

To get the smallest value first, change the comparison to greater<int>. Now a has lower priority than b when a > b, so the smallest value is the top:

priority_queue<int, vector<int>, greater<int>> pq;   // min-heap

The header <functional> provides greater and less. You need it for these names, so include it when you use them. Writing min_priority_queue does not compile, because the standard library does not have that name. Students often guess it, and the compiler then reports that the name is not found.

Here is a program that uses both forms. It reads some numbers, prints the largest one first in a max-heap, and then prints the smallest one first in a min-heap. Type this into the Input box:

5
3 9 4 1 7

The output is:

top: 9
largest first: 9 7 4 3 1
smallest first: 1 3 4 7 9

Notice the loop pattern. You read top, then call pop as a separate step. This is required because pop returns nothing. The next section explains that in detail.

Also notice that maxHeap and minHeap both received the same five pushes, so each one holds five values. The loop drained each heap separately. After the loops, both are empty, and empty() returns true.

The operations, and what they return

The standard priority_queue has a small set of operations. Here they are, with their costs and their return types:

The most surprising row is pop, which returns nothing. In many other containers, a "remove the first item" function returns the removed item. Here it does not. If you write this:

int best = pq.pop();

the compiler refuses. The message from g++ looks like this:

error: void value not ignored as it ought to be

The fix is to read top first and then pop:

int best = pq.top();
pq.pop();

The reason for this design is that returning the removed value would force a copy even when the caller does not need it. The standard library chose to keep pop simple and make the caller read top first.

Also notice what the table does not contain. There is no way to look at the second item, no index operator, and no way to iterate over the items in order. A heap only promises the root. If you need to walk over all items, you must pop them, or copy the queue and pop the copy. Interviewers often ask about this limit, so keep it in mind.

Undefined behaviour on an empty queue

Our own MinHeap class from the last lesson threw an error when you called top on an empty heap. The standard priority_queue does not. Calling top or pop on an empty priority_queue is undefined behaviour. The word means the C++ standard does not say what happens. The program may crash, may print garbage, or may appear to work until a later change breaks it.

So always check empty() before you read top or call pop. This is the single most common crash with heaps in C++. A loop that reads top and pops once more than the number of items is a classic bug:

while (true) {
    cout << pq.top() << "\n";   // no empty check: undefined when the queue is empty
    pq.pop();
}

The correct loop checks first:

while (!pq.empty()) {
    cout << pq.top() << "\n";
    pq.pop();
}

Storing structs with a custom order

Numbers are easy. Real programs store records: tasks, events, requests, edges of a graph. Each record has a priority field, and the order you want depends on that field. For that, you write your own comparison.

Suppose a task has a name and a priority number. A smaller priority number means the task is more urgent, so priority 1 should come before priority 5. If two tasks have the same priority, the alphabetically smaller name should come first, so the output is stable to read. The comparison must say when one task has lower priority than another. Here is a comparison struct:

struct Task {
    string name;
    int priority;   // smaller number means more urgent
};
 
struct MoreImportantLater {
    bool operator()(const Task& a, const Task& b) const {
        if (a.priority != b.priority) return a.priority > b.priority;
        return a.name > b.name;
    }
};

Read the function carefully. It returns true when a has lower priority than b. A task with a bigger priority number is less urgent, so a.priority > b.priority means a is the less important one. When priorities are equal, the task with the bigger name is less important, so a.name > b.name. The task at the top is the one that no other task beats: the smallest priority number, and among equal priorities, the smallest name.

Then you give the struct to the queue as the third argument:

priority_queue<Task, vector<Task>, MoreImportantLater> queue;

The next program reads tasks and prints them in the order the queue releases them. Type this into the Input box:

4
write 3
buy 1
call 1
rest 5

The output is:

buy 1
call 1
write 3
rest 5

Trace the decision for the two tasks with priority 1. Both buy and call have priority 1, so the comparison goes to the name. buy is alphabetically smaller, so it is the most important of the two, and it comes out first. Then call. Then write with priority 3, and finally rest with priority 5.

A lambda instead of a struct

You can also pass a lambda, which is a small function written inline. In C++17 you must create the lambda first and then pass its type with decltype, because each lambda has its own unique type:

auto moreImportantLater = [](const Task& a, const Task& b) {
    if (a.priority != b.priority) return a.priority > b.priority;
    return a.name > b.name;
};
priority_queue<Task, vector<Task>, decltype(moreImportantLater)> queue(moreImportantLater);

Both forms do the same job. The struct is easier to read when the order is used in several places, and the lambda is shorter when the order is used once. Pick one and stay consistent in a program.

Pairs as priorities

Another common approach is to store a pair. A pair<int, string> compares by its first field, and when the first fields are equal, by its second field. That is exactly the order we want for tasks, so you can avoid writing a comparator:

priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> queue;
queue.push({3, "write"});
queue.push({1, "buy"});

The greater comparison makes the smallest pair the top. The top is {1, "buy"}. Pairs are shorter to write, but a struct names each field, which makes the code easier to read later. Use pairs for quick contest work and structs for code that other people read.

Heap sort with a priority queue

Now we can sort with a heap. The idea is simple. Push every value into a min-heap. Then pop them all. Each pop returns the smallest value that remains, so the values come out in ascending order. This is heap sort in its simplest form.

Here is the cost. Each push costs O(log n), so n pushes cost O(n log n). Each pop costs O(log n), so n pops cost O(n log n). The total is O(n log n). The extra space is an entire heap, which holds n values, so the space is O(n).

The priority queue version is short, and it is good to know. But it uses extra memory. The next section shows the version that sorts in place.

In-place heap sort

Heap sort does not need a second array. You can sort inside the array you already have, by turning the array into a max-heap and then moving the largest value to the end, one at a time. The method works in two stages.

Stage one: build a max-heap from the whole array. This is the same heapify you learned in the last lesson, but with a max-heap rule, so each parent is at least its children. The loop starts at the last parent and moves back to the root. It costs O(n).

Stage two: repeat until the array is sorted. Swap the root, which is the largest value, with the last unsorted position. The sorted part now sits at the end and does not need to move again. Then sift the new root down, but only within the unsorted part. The unsorted part shrinks by one each time.

Let us trace it on a small array, [4, 1, 3]. We will use the max-heap rule.

1. Build a max-heap. The loop starts at i = 3 / 2 = 1, so it sifts index 0. Index 0 holds 4, with children 1 and 3. Since 4 is already larger than both, nothing moves. The array is [4, 1, 3], already a max-heap.
2. Swap the root with the last position. The array is [3, 1, 4]. The value 4 is now in its final place.
3. Shrink the heap to two values, [3, 1], and sift the root down. Index 0 holds 3, child 1 holds 1. Since 3 is larger, nothing moves.
4. Swap the root with the last unsorted position. The array is [1, 3, 4]. Now 3 is in place. The heap has one value, so the loop stops.

The array is sorted: [1, 3, 4]. The loop uses the sift-down code from the last lesson, changed to look for the largest child instead of the smallest. The next program does the whole thing for eight numbers. Type this into the Input box:

8
4 1 7 3 9 2 8 5

The output is:

1 2 3 4 5 7 8 9

Notice the parameter end in siftDown. It is an exclusive limit. Positions at or after end are already sorted and are not part of the heap, so the children check uses left < end and right < end. That single detail is what makes the in-place version work. If you forget to pass the shrinking limit, the sift-down reads the sorted tail and moves it back into the heap, and the output is wrong.

The loop for the sorted part, for (size_t end = n; end > 1; end--), stops when one value is left. A heap of one value is already in order.

Why heap sort is not used everywhere

Heap sort has a good worst case: O(n log n) time with O(1) extra space. That is better than quicksort's worst case, which is O(n squared). Yet most standard libraries use a different algorithm for everyday sorting. There are two reasons.

First, heap sort has poor memory access. The moves jump between far-apart positions in the array, because the children of an index are far away once the index is large. The processor's cache works best when the program walks through memory in order, and heap sort does not do that. In practice, quicksort and merge sort run faster on typical data, even though their worst cases are worse.

Second, heap sort is not stable. A stable sort keeps the original order of equal values. Imagine sorting people by age, where two people have the same age. A stable sort keeps them in the order they appeared in the input. Heap sort swaps the root with a far position, so equal values can change order. For example, if two items with the same key are placed so that the root swap moves the later one first, the earlier one may end up after it. If your sort must be stable, use std::stable_sort or merge sort.

Still, heap sort is worth knowing. It shows that a heap can sort, and it has a guaranteed bound that quicksort lacks. Interviewers ask for it because it tests whether you understand sift-down and the in-place idea.

The standard library's heap algorithms

The <algorithm> header has functions that do the heap work on any range with random access, such as a vector. You do not need to wrap the data in a priority_queue to use them. The main ones are make_heap, push_heap, pop_heap and sort_heap.

• make_heap(first, last) turns a range into a max-heap, in O(n).
• push_heap(first, last) fixes the heap after you add a value at the last position. You add the value with push_back first, then call this.
• pop_heap(first, last) moves the largest value to the last position, and repairs the rest of the range as a heap. You then remove that last value with pop_back.
• sort_heap(first, last) sorts a heap in place into ascending order.

The next program uses all four. Type nothing into the Input box, because the data is fixed in the program:

The output is:

after make_heap: 9 6 4 1 5 3 2 1
front is 9
moved to back: 9
after pop: 6 5 4 1 1 3 2
after push 10: 10 6 4 5 1 3 2 1
sorted: 1 1 2 3 4 5 6 10

Check the first line. The max-heap of those numbers has 9 at the root, and the parent rule holds: 6 and 4 are below 9, 1 and 5 are below 6, and so on. After pop_heap, the value 9 sits at the back, and then pop_back removes it. The heap of the remaining values has 6 at the root. Pushing 10 puts it at the end, and push_heap lifts it to the root. Finally sort_heap turns the whole heap into a sorted array.

Be careful with sort_heap. It needs a valid heap as input. If you call it on an array that is not a heap, the result is not sorted, and the standard does not promise anything. Use sort for plain arrays.

Choosing between a heap, a sorted set and a sort

Three tools overlap here, and choosing the right one is an interview skill. A sorted set (std::set or std::multiset) keeps values in order inside a balanced tree. It can insert, find and erase any value in O(log n), and it reads the smallest value with begin(). A priority_queue only reads and removes the top, but its operations are simpler and its memory is a plain vector, so it is usually faster for a pure priority queue. A sort works best when every value is known before you start, because one O(n log n) sort then answers every later read in O(1).

Use a priority_queue when values arrive over time and you only ever need the most important one. Use a set when you must also remove a value that is not at the top, such as a task that was cancelled, or change the priority of a task that is already waiting. The set pays more memory and a bigger constant for that flexibility. Use a sort when the whole list is known up front and you need every value in order once.

Here is the comparison for the task problem. The queue releases each task in O(log n), but it cannot cancel a waiting task without extra work. A set can erase a cancelled task in O(log n), but you must first find it. A sort gives all tasks in order once, but each new task forces another sort. For a live system with arrivals and cancellations, many programs use a priority_queue with lazy deletion, which the mistakes section above describes.

How the comparator decides, step by step

It helps to watch the comparator make one decision at a time. Take two tasks, buy with priority 1, and write with priority 3. Call the comparator with a set to buy and b set to write.

1. The priorities are 1 and 3, which differ, so the first if is taken.
2. The function returns a.priority > b.priority, which is 1 > 3, so false.
3. false means buy is not less important than write. So buy belongs above write in the queue.

Now swap the arguments. With a set to write and b set to buy, the function returns 3 > 1, which is true, so write is less important, as it should be.

Next take buy and call, both with priority 1. The first if is skipped because the priorities are equal. The function returns a.name > b.name, which is "buy" > "call", and that is false. So buy is not less important than call, and buy comes out first. This is the rule the program depends on. Equal priorities always fall through to a second rule, so every pair has a clear answer.

Real-world uses of priority queues

Operating systems use priority queues to decide which process runs next. Network routers keep urgent packets near the front. Shortest-path algorithms such as Dijkstra's algorithm keep the closest unexplored node at the top. Event simulators keep the next event in time at the top, so the simulation jumps from one event to the next. A print server holds jobs by urgency. Each use relies on the same three facts: the top is read in O(1), each push and pop costs O(log n), and equal priorities must be decided on purpose.

Complexity and space

The table shows the trade-off between the two heap sorts. The priority queue version is shorter to write, and it uses a second container. The in-place version uses no extra space, and it needs a careful sift-down with the shrinking limit.

Testing an order by hand

Before you trust a comparator, test it on a small set where you can predict the answer. Take the four tasks from the program, write 3, buy 1, call 1 and rest 5. Write them in any order you like, and then sort them by the rule in words: smaller priority first, and for equal priorities, alphabetically smaller name first. The result is the list the program prints.

Now shuffle the input. Put rest 5 first and call 1 last, and run the program again. The output must not change, because the queue decides the order from the values, not from when they arrived. If the output does change, something in the comparison depends on the arrival order, and the bug is in the comparator.

Test the tie-break on purpose. Give two tasks the same priority, and check that the one with the smaller name always comes first, whichever order you push them in. A good test has at least one tie in every position of the input, because a missing tie-break often works when the tied tasks happen to arrive in the right order.

Common mistakes and what they look like

Mistake 1: expecting pop to return the value

As we saw, pop returns nothing. The error message is:

error: void value not ignored as it ought to be

Read the value with top first, then call pop.

Mistake 2: forgetting the include

Using priority_queue without #include <queue> gives an error like this:

error: 'priority_queue' is not a member of 'std'

Using greater without #include <functional> gives a similar error about greater. The fix is to add the header that names the item. vector needs <vector>, swap needs <utility> or <algorithm>, and so on.

Mistake 3: a comparison that is not strict

The comparison must be a strict ordering: a is "less" than b only when it truly has lower priority. A comparison that uses <= or >= can break the heap, because two equal items can each claim to be less than the other. The standard calls this a violation of the strict weak ordering requirement, and the program may misbehave in ways that depend on the data. Always use < or > in a comparator. If two items are equal, fall through to a second field, as our task comparator does.

Mistake 4: a non-empty assumption

Calling top on an empty queue reads garbage or crashes. The check while (!pq.empty()) must come before every top and every pop that is not guaranteed to have a value. A common symptom is a program that works on the test data and crashes on an empty input, which is often the first edge case the grader tries.

Mistake 5: changing a priority after the push

Suppose you push a task, then change its priority field in your own copy. The queue does not know about the change, because it only compares items when it moves them. The heap rule may be broken, and top may return the wrong item. A priority_queue has no way to update an item in place. If priorities change, the standard approach is to push a new copy with the new priority and skip stale copies when they come out. That technique is called lazy deletion, and you will see it in the module assignment.

Mistake 6: heap sort on a shrinking range

The in-place sort uses the limit end to ignore the sorted tail. If you use a.size() inside sift-down by mistake, the sorted tail returns to the heap, and the values come out in the wrong order. Write the limit as a parameter, as the code does.

Debugging walkthrough: why does my queue come out in the wrong order?

Suppose you wrote a task queue and the tasks come out in the wrong order. A method like the one from the last lesson works well here.

1. Print the priority of each task as you push it. Check that the priorities are the numbers you typed.
2. Check the comparison by calling it directly on two tasks you know. For example, MoreImportantLater{}(t1, t2) should be true when t1 is less urgent. Write a small test with a few tasks and print the result. A wrong sign in the comparison is the most common cause.
3. Check that the comparison handles ties. Two tasks with the same priority must come out in a fixed order, by name. If your comparison returns false both ways for equal priorities, the order is not defined.
4. Print the whole queue by popping it, and compare with what you expected. If only the ties are wrong, the bug is in the tie-breaking line.

In the trace, check the most urgent task first, then the next, and so on. Most order bugs are a reversed sign or a missing tie-break.

Edge cases you should test

• An empty queue. empty() must return true, and the loop must not run.
• A single task. It comes out alone, with no comparison needed.
• Many tasks with the same priority. The tie-break decides the order, and it must be stable across runs.
• Negative priorities. The comparison works the same way, so -5 is more urgent than 2 if you use the smaller-is-urgent rule.
• Heap sort on one value or on zero values. The loop for (size_t end = n; end > 1; end--) does nothing, so the array stays as it is, which is correct.
• Heap sort on an array with many equal values. The result is still sorted, but the order of equal values is not kept, because heap sort is not stable.

Interview questions you should be ready for

What is the default order of priority_queue<int>? It is a max-heap. top returns the largest value.

How do you make a min-heap? Give greater<int> as the third template argument, and include <functional>.

Why does pop return void? So that it never makes an unneeded copy of the removed value. Read top first, then call pop.

Is priority_queue stable? No. Two items with equal priority may come out in either order. If order matters, add a second field, such as a sequence number, to the comparison.

Can you change a value inside a priority_queue? Not directly. You push a new value and mark the old one stale, or you use a different structure, such as a balanced tree, that supports updates.

Why is heap sort slower in practice than quicksort? Its memory access is scattered, so the cache works less well. The number of comparisons is similar, but the actual running time is usually longer.

Practice

1. Write the declaration of a max-heap of double values. Then write the declaration of a min-heap of double values.

2. What does this print? priority_queue<int> pq; pq.push(5); pq.push(1); pq.push(8); pq.pop(); cout << pq.top();

3. Change the first program so it prints the second-largest value too, without using a sorted copy. Explain why you pop once and read top again.

4. Add a field int id to Task and make the tie-break use id instead of name. Test with two tasks that have equal priority and different ids.

5. Explain why while (!pq.empty()) must come before pq.top(), and what might happen if you swap the order.

6. Write a program that reads n and n integers, and prints the sum of the three largest values using a priority_queue. Assume n is at least 3.

7. Change the in-place heap sort so it sorts in descending order. Name the one line you change.

8. Find an input for which the priority-queue heap sort and std::sort give the same output, and an input for which they give different output. Explain why there can be a difference.

9. Write the comparator for tasks where a higher priority number means more urgent. Explain which sign you flipped compared with the lesson.

10. Using make_heap, pop_heap and pop_back, write code that prints a vector of integers in descending order without a priority_queue.

11. A student writes int x = pq.pop(); and gets an error. Explain the error and show the fix in two lines.

12. Explain in plain words why heap sort is O(n log n) even when the input is already sorted.

What you now know

• priority_queue<int> is a max-heap by default. priority_queue<int, vector<int>, greater<int>> is a min-heap.
• top reads the most important item, pop removes it and returns nothing, and both are undefined on an empty queue, so check empty() first.
• A struct or a pair can be stored with a custom comparison. Break ties with a second field so the order is fully decided.
• Heap sort turns an array into a heap and removes the largest value to the end, one at a time. The in-place version costs O(n log n) time and O(1) extra space, but it is not stable.
• The <algorithm> heap functions make_heap, push_heap, pop_heap and sort_heap work on any random-access range.