Is there a maxheap in the C++ standard library?

Question

I know the std::priority_queue class implements a minheap. Is there a way to use this as a Max heap? Or is there an alternative Maxheap structure? I know I can use the std::make_heap() function on a std::vector with lambda to create my own Maxheap but then using functions such as std::pop_heap() is weird and I don't think they are easy to use. There should be an easier way just like the min_heap(priority queue) I think.

Answer 1

Regarding std::priority_queue:

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

Since std::less<T> is the default template argument to the Compare template parameter, it is already a max heap by default. If you want a min heap instead (what the quote above suggest), pass std::greater<T> instead of std::less<T> as the template argument.

To summarize:

• Max Heap: pass std::less<T> (this is the default template argument).
• Min Heap: pass std::greater<T>.

---

Note that std::priority_queue is actually a container adapter (in contrast to a data structure). It doesn't specify what underlying data structure is using. However, due to the specified run-time complexity of the operations push(), pop() and top(), it is likely implemented as a heap.