Explain behavior of default priority_queue::top()?

user_8728860 0
Viewed 43

The std::priority_queue, by default uses a std::vector<int> and the std::less comparator. By default, priority_queue is a max heap.

The docs for top() states:

The top element is the element that compares higher in the priority_queue, and the next that is removed from the container when priority_queue::top is called.

This member function effectively calls member front of the underlying container object.

Therefore a default constructed priority_queue of integers constructed like so:

auto maxheap = priority_queue<int>();
maxHeap.push(1);
maxHeap.push(3);
cout << maxHeap.top(); // outputs 3

However, going back to the description of top(), the docs state that, effectively, the member front on the underlying container object is called. If I create a vector and sort using std::less to mimic the underlying container of our maxHeap:

auto vec = vector<int>{3, 1};
sort(vec.begin(), vec.end(), less<int>()); // {1, 3}
cout << vec.front(); // outputs 1

Because std::less sorts in ascending order, calling vec.front() ends up returning the smallest value.

There's some disconnect in my understanding of how the default behavior of priority_queue::top() and what the docs say. Can some explain this to me?

priority-queue stl c++
1 Answers

You're using the wrong algorithm, you can read at https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue that std::priority_queue doesn't use std::sort, but std::make_heap.

If you use it in your example as well, you get the output you're expecting.

std::vector<int> queue{1, 3};
std::make_heap(queue.begin(), queue.end(), std::less<>{});
std::cout << queue.front() << '\n';

Output: 3
user_83492520
Related