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

c++ priority-queue c++-standard-library standard-library max-heap
OgiciBumKacar picture OgiciBumKacar · Jul 30, 2019 · Viewed 9k times · Source

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

里纳尔迪 picture 里纳尔迪 · Jul 30, 2019

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.

Related questions

declaring a priority_queue in c++ with a custom comparator

I'm trying to declare a priority_queue of nodes, using bool Compare(Node a, Node b) as the comparator function (which is outside the node class). What I currently have is: priority_queue<Node, vector<Node>, Compare&…

Read More
How can I create Min stl priority_queue?

The default stl priority queue is a Max one (Top function returns the largest element). Say, for simplicity, that it is a priority queue of int values.

Read More
How to remove element not at top from priority_queue?

In my program I need to delete an element from a priority queue that is not at the top. Can that be done? If not, please suggest a way to do so except creating your own heap.

Read More