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

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.

3 Answers

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.

Short Answer

Max Heap:

priority_queue<int> maxHeap; // NOTE: default is max heap 

Min Heap

priority_queue<int, vector<int> , greater<int>> minHeap; 

Headers and namespaces:

#include <vector> #include <priority_queue> using namespace std; 

There is no "heap" container just like there is no "search tree", nor "hash map" (instead of latter two, there are ordered and unordered associative containers, which are in practice implemented using those data structures, because no other data structure can satisfy the requirements specified for those containers).

There is a container adaptor std::priority_queue, which can adapt a SequenceContainer (std::vector is adapted by default), and provides same operations as a max/min heap does, and probably internally is implemented as a some kind of heap.

There is also std::make_heap which can be used to enforce the max heap property on a random-access range.