8

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.

Deduplicator
  • 44,692
  • 7
  • 66
  • 118
OgiciBumKacar
  • 311
  • 1
  • 3
  • 10
  • 2
    In the STL, heaps are decoupled from actual container implementations. Have a look at [`std::make_heap`](https://en.cppreference.com/w/cpp/algorithm/make_heap). It lets you pass a custom comparator, in your case that could be `std::greater<>{}`. – lubgr Jul 30 '19 at 12:09
  • Yes I have been using that but it just felt really weird to use pop_heap() and then pop_back() when Im trying to delete an element so I thought there might be a better alternative. Thank you. – OgiciBumKacar Jul 30 '19 at 12:11
  • 3
    @lubgr Be aware that `std::make_heap` and all heap algorithms / items in the standard library make max heaps, not min heaps. Thus, `std::greater<>{}` would make a min heap. The easiest way to remember this is to imagine the heap utilities as implementation details for heapsort. – Justin Jul 30 '19 at 16:09
  • @Justin good point, I confused the min heap - `std::greater`, max heap - `std::less`. – lubgr Jul 30 '19 at 20:53

3 Answers3

19

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.

JFMR
  • 23,265
  • 4
  • 52
  • 76
  • Then to create a min heap my declaretion would look like ```priority_queue> q; ``` right? In the page you linked theres also a vector in the template arguements but I can't understand the reasoning for that. – OgiciBumKacar Jul 30 '19 at 12:22
  • @OgiciBumKacar Yes. The vector is the underlying container. – JFMR Jul 30 '19 at 12:23
  • @OgiciBumKacar you should use ```std::priority_queue, std::greater > q;``` – mascai Aug 22 '20 at 08:34
  • Why is `std::less` the template that corresponds to a max heap? Wouldn't `std::greater` make more sense intuitively as the root node with the largest value for data-type `T` has the *greatest* priority? – E. Kaufman Dec 28 '20 at 06:33
  • @E.Kaufman In the `std::priority_queue`, the "largest" element always comes at the *top*. However, what "largest" means depends on the *comparison function*: It must be defined in such a way so that `true` is returned if its first argument *comes before* (i.e., it is "smaller" than) its second argument. In other words, the comparison function must return `true` if its second argument is "larger" than its first argument – i.e., when `true`, the second argument would become the *top of the heap* before the first argument does. Therefore, if `std::less` is used, the heap corresponds to a max-heap – JFMR Dec 28 '20 at 10:09
6

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;
A-Sharabiani
  • 17,750
  • 17
  • 113
  • 128
0

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.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • 1
    This is really splitting hairs. The way the standard requires the containers to behave there is really nothing but an RB-Tree that can be used for the associative containers and the unordered containers are required to be a "hash map"/"hash set" (although in a very non-optimal way *bucket iterators*). – NathanOliver Jul 30 '19 at 12:27
  • 1
    @NathanOliver Are you sure that no other balanced search tree be used besides RB-tree? There's not necessarily any advantage in using it, but would not AVL tree satisfy all requirements? Regardless, as I said, the associative containers are in practice implemented using those data structures. It's not just splitting hairs though; If the standard did provide a generic tree data structure, then it should be augmentable to implement different kinds of trees. But it doesn't; It provides an associative container with interface that is implementable using a tree instead. – eerorika Jul 30 '19 at 12:33