Custom comparators and tie-breaking

Why this matters

A heap always gives back the most important item first. What "most important" means is decided by a comparator. A comparator is a small piece of code that answers one question about two items: should the first one come out before the second one?

Most real queues have more than one rule. A support desk serves the most urgent ticket first, and among tickets with the same urgency it serves the oldest one first. A print server serves the job with the highest priority first, and among jobs with equal priority it serves the one that arrived first. Each of these rules is a comparator with two keys.

If the comparator gives a wrong answer, the heap returns the items in the wrong order. Nothing crashes, and no error message appears. The program simply prints the wrong tasks in the wrong order. That is why this lesson checks each comparator with a real run.

The lesson uses std::priority_queue, the heap type in the C++ standard library. The idea of a heap (a parent that is more important than its children, and a top item) is covered in the earlier lessons of this module and is not repeated here. The next lesson covers bugs in heap code that you write yourself.

Which item comes out first

std::priority_queue keeps the item that is "greatest" on top. The default comparator is std::less, which compares two values with <. So for plain integers, the largest value is on top. A small check makes this clear.

Output from g++ 15 on this machine:

default top: 3
greater top: 1

The rule to remember is this. A comparator cmp(a, b) returns true when a is less important than b, which means a should come out later. The top of the heap is the item that is not less important than any other item in the heap.

Once that rule is clear, a two-key comparator is just an if with two steps: compare the first key, and if the keys are equal, compare the second key.

Example 1: priority first, then due day

Each task has a priority, where a bigger number is more urgent, and a due day, where a smaller number means the task is due sooner. The rule is: the highest priority comes out first. If two tasks have the same priority, the one due sooner comes out first.

The comparator is a struct with a function call operator (a member function named operator()). The heap calls it with two tasks.

Output:

priority 3, due day 5: deploy
priority 3, due day 7: fix bug
priority 2, due day 4: reply to email
priority 2, due day 9: write report
priority 1, due day 1: lunch

Take one pair and check the answer by hand. Compare "fix bug" (priority 3, due day 7) with "deploy" (priority 3, due day 5). The priorities are equal, so the comparator moves to the due days. The call is cmp(fix bug, deploy), which evaluates a.due > b.due, that is 7 > 5, which is true. So "fix bug" is the less urgent one, and "deploy" comes out first. The output agrees.

The second key uses > instead of <. This looks odd, but it follows from the rule that the top is the greatest item. A task due on day 5 must count as greater than a task due on day 7, so that it sits on top. Writing a.due < b.due is a common mistake here. Section "Common mistakes" shows what that does.

Example 2: a tie-break with an index

Sometimes two items have the same keys. Take a queue of jobs that all have priority 1. The comparator says that no job is more urgent than another, so the heap has no reason to put one before another. The order that comes out is not defined by the rule.

This program pushes five jobs with the same priority, and then one job with a higher priority.

Output from this build:

F A C E B D 

Job F comes first, which is correct. The jobs A to E all have priority 1, and they come out in the order A, C, E, B, D. That order is not the order in which they were pushed. A different version of the standard library could give a different order. A program that depends on it is fragile.

The fix is a tie-break key, a second key that decides the order when the first keys are equal. A simple tie-break is an index: a number that counts pushes, so each job gets 0, then 1, then 2, and so on. Among jobs with equal priority, the one with the smaller number is earlier in the queue, so it comes out first.

Output:

D A B C E 

D has the highest priority, so it comes first. Then A, B, C and E come out in the order they were pushed. The result is the same on every run and every build, because the comparator never answers "equal" for two different jobs.

The index is an extra field, but it does not need to be meaningful to the user. It only has to be different for every item. A counter that goes up by one on each push is the usual choice. The comparator uses the index only when the other keys are equal, so it does not change the main order.

A note on push: it is a lambda that takes the name by value and moves it into the struct with std::move. The lambda captures next and the queue by reference, and it increments next each time. Moving a string avoids copying it, and the program does not use name again after the move.

Example 3: a lambda comparator

A comparator does not have to be a struct. A lambda (a small function written inline) works too, and it is shorter for simple rules. The lambda's type has no name that you can write, so the program gets it with decltype, which means "the type of this expression".

In C++20, a lambda that captures nothing can be created with no arguments. That means the queue can be declared without passing the comparator in.

Output:

T-3 severity 3 age 8
T-2 severity 3 age 1
T-4 severity 2 age 9
T-1 severity 2 age 5

Severity 3 tickets come first. Between T-2 (age 1) and T-3 (age 8), the comparator returns a.age_hours < b.age_hours, so the ticket with the smaller age is the less urgent one, and the older ticket T-3 sits on top. The same rule applies to the severity 2 tickets, where T-4 (age 9) comes before T-1 (age 5).

A lambda with a capture, such as [limit], cannot be created without arguments. The section on common mistakes shows the error. The fix is to pass the lambda object to the queue constructor, which was tested with a capture of 10 and gave 8 27 4 13 for the inputs 13, 4, 27 and 8, sorted by the value modulo 10.

Example 4: a comparator that breaks the heap

So far, every comparator answered the question in a consistent way. A heap depends on that consistency. The C++ standard calls the required property a strict weak ordering. In plain words, it means three things. "Less than" never says that an item is less than itself. If a is less than b, then b is not less than a. And if two items are both equal to a third item, they are equal to each other. Breaking these rules gives undefined behaviour, which means the standard does not say what happens. The program can print the wrong answer, crash, or seem to work.

Using <= instead of <

A common slip is to write <= in the comparator, because it looks like a small change. Here the comparator says that item a is less than item b when their keys are equal. Two items with the same key are then less than each other, which breaks the first rule above.

On this build, the program prints 12 lines and shows no error. The keys come out in the right order, 2 then 1 then 0, but the ids inside each group come out in an order that the program never asked for. Nothing looks wrong, which is the danger.

Compile the same file with the debug mode of the standard library. This mode checks the comparator while the program runs.

g++ -std=c++20 -Wall -D_GLIBCXX_DEBUG -o bad bad.cpp && ./bad

The debug build stops and prints this line among its message:

Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

The message says that the comparator claims an item is less than itself. The fix is to change <= to <. Use the debug build when you write a new comparator. It is slower, but it turns a silent wrong answer into a message that names the problem.

Keys that change while the item is inside the heap

A heap places each item by comparing its key at the time of the push. If the key changes later, the heap does not know. The heap is then in a state that its own rules do not describe.

This program stores pointers to tasks, so the heap sees the task's current priority each time it compares. The program changes the priority of task b after pushing it.

Output:

top: a
pop a (priority 5)
pop b (priority 9)
pop c (priority 4)

After the change, task b has the highest priority, 9, so it should be on top. The heap still has a on top, because it placed b lower when b had priority 3. Then b comes out after a and before c, which is the wrong order for these priorities. The right order is b, a, c.

The rule to follow is simple: do not change the key of an item while it is in the heap. If the key must change, take the item out, change it, and push it again. A heap that supports changing keys in place is covered by the indexed heap lesson in this module.

Common mistakes

Reversing the rule. A comparator with a.due < b.due in Example 1 gives the opposite result. The tasks due later come out first. Running the reversed version gives this output:

fix bug (due 7)
deploy (due 5)
write report (due 9)
reply to email (due 4)
lunch (due 1)

Within each priority, the task due latest is on top. The fix is to swap the two keys in the return line, or to remember the rule that the top is the greatest item.

Thinking the default queue is a min heap. priority_queue<int> returns the largest value first. Use greater<int> for the smallest first, as shown at the start of this lesson.

Forgetting a tie-break. Without a tie-break, equal items come out in an order the code does not control. The jobs example above shows this. The output looked plausible, so the bug was easy to miss.

Using a type with no comparison. A comparator that uses < on a struct needs the struct to define <, or the default comparator needs it. Pushing a struct into a plain std::priority_queue with no comparator gives this error on g++ 15:

error: no match for ‘operator<’ (operand types are ‘const Task’ and ‘const Task’)

The fix is to pass a comparator, as in Example 1.

Declaring the queue without the comparator object. A lambda that captures a variable cannot be created without arguments. This code fails:

int limit = 10;
auto cmp = [limit](int a, int b) { return (a % limit) < (b % limit); };
priority_queue<int, vector<int>, decltype(cmp)> pq;

g++ 15 prints the following first line of its error (the file name and line depend on your program):

example.cpp:9:53: error: no matching function for call to ‘std::priority_queue<int, std::vector<int>, main()::<lambda(int, int)> >::priority_queue()’

The fix is to pass the object: priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);. This version prints 8 27 4 13 for the inputs 13, 4, 27 and 8.

Using <= or >=. These are the same mistake as in Example 4. Equal items must not be less than each other.

Changing keys in place. The results in Example 4 show how a changed key breaks the order of the heap.

Practice

Exercise 1. Write a comparator for words. A longer word comes out first. When two words have the same length, the alphabetically smaller word comes out first. Push these words into the queue: pear, fig, banana, kiwi, apple, date. What order comes out?

Show the answer

The comparator is:

struct ByLengthThenAlpha {
    bool operator()(const string& a, const string& b) const {
        if (a.size() != b.size()) return a.size() < b.size();
        return a > b;
    }
};

The return a > b line is the tie-break. A word that is alphabetically later is the less urgent one. The output from a run of this comparator is banana apple date kiwi pear fig. Banana is the longest word, apple has five letters, and the three four-letter words come out in alphabetical order: date, kiwi, pear. Fig is last because it has three letters.

Exercise 2. Find the bug in this comparator, which is meant to put the item with the higher score first:

struct Bad {
    bool operator()(const Item& a, const Item& b) const {
        return a.score >= b.score;
    }
};

Show the answer

Equal scores make cmp(a, b) return true and cmp(b, a) return true, so two items with the same score are each less than the other. This breaks the rule that "less than" must never be true for an item compared with itself. The fix is a.score < b.score. Compiled with -D_GLIBCXX_DEBUG and 12 items with scores 0, 1 and 2, this version stops with Error: comparison doesn't meet irreflexive requirements, assert(!(a < a)).

Exercise 3. Change Example 1 so that equal priority and equal due day are broken by the order of arrival. Which field do you add, and where is the push counter kept?

Show the answer

Add an int seq field to Task, and keep a counter such as int next = 0; in the code that pushes. Each push stores next++ in seq. The comparator then adds one more line after the due-day check: return a.seq > b.seq;. Earlier pushes have smaller numbers, so they come out first among equal tasks.

Exercise 4. Predict the output of this program, then run it to check.

struct Item { int key; int id; };
struct Cmp {
    bool operator()(const Item& a, const Item& b) const { return a.key < b.key; }
};
int main() {
    priority_queue<Item, vector<Item>, Cmp> pq;
    pq.push({2, 1});
    pq.push({5, 2});
    pq.push({5, 3});
    pq.push({1, 4});
    while (!pq.empty()) { cout << pq.top().id << ' '; pq.pop(); }
}

Show the answer

The keys are 2, 5, 5 and 1. The two items with key 5 are ids 2 and 3, and the comparator does not say which one comes first. The run on g++ 15 printed 2 3 1 4. Another build could print 3 2 1 4 and still follow the rule, so a program should not depend on it. Adding a tie-break on id, such as if (a.key != b.key) return a.key < b.key; return a.id > b.id;, makes the order of the two key-5 items fixed.

Exercise 5. A changed key breaks the heap. Predict what this program prints, and what it should print.

struct ByValue {
    bool operator()(const int* a, const int* b) const { return *a > *b; }  // min heap
};
int main() {
    int vals[3] = {4, 7, 6};
    priority_queue<const int*, vector<const int*>, ByValue> pq;
    for (int i = 0; i < 3; ++i) pq.push(&vals[i]);
    vals[0] = 10;  // changed while inside the heap
    cout << "top: " << *pq.top() << '\n';
}

Show the answer

The program prints top: 10. The heap placed the pointer to the value 4 on top when that value was 4. Changing the value to 10 does not move the pointer inside the heap, so the root is still that pointer, and it now reads 10. The smallest value in the queue is 6, so the correct top is 6. The fix is to remove the item, change it, and push it again.

Summary

• A comparator cmp(a, b) returns true when a should come out after b. The top of a std::priority_queue is the greatest item by that rule.
• Two keys are compared in order: the first key, and if they are equal, the second key.
• An index that goes up by one at each push makes the order of equal items fixed.
• A comparator must never say that an item is less than itself. Use < or >, not <= or >=, and check with -D_GLIBCXX_DEBUG while you develop.
• Do not change a key while the item is in the heap. Take it out, change it, and push it again.