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

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.

Leave a Comment