C++ STL/Priority Queue; Min Max Heap of Integer

From Software Engineers Wiki
Jump to: navigation, search

Implement min heap and max heap using std::priority_queue

Answer

  • Min heap: Minimum number on the top. The comparator return true if left is greater than the right.
  • Max heap: Maximum number on the top. The comparator return true if left is smaller than the right.

One of way to define a max heap is as follows. For integer, it doesn't need special comparator if the priority queue is for max heap.

std::priority_queue<int> pqueue;

To use custom comparator.

class CIntCompare {
public:
        bool operator()(const int left, const int right) { return left < right; }
};

std::priority_queue<int, std::vector<int>, CIntCompare> pqueue;

You may use predefined comparator. std::less<int> for max heap, std::greater<int> for min heap.

std::priority_queue<int, std::vector<int>, std::less<int>> pqueue;

Another way is use lambda as comparator. The priority_queue takes the comparator as a template argument. Lambda functions are objects, and can't be used as template arguments.

auto int_compare = [](const int left, const int right) { return left < right; };
std::priority_queue<int, std::vector<int>, decltype(int_compare)> pqueue(int_compare);
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox