std::priority_queue

std::priority_queue video (17 minutes) (Spring 2021)

This is a simple demonstration of how std::priority_queue can be used.

cppreference.com/.../priority_queue

We have already done the hard part in the previous lecture, implementing a Priority Queue with a Min Heap, so this is a shorter code example.

Min Heap vs Max Heap

std::priority_queue takes a Comparator as a template argument. This gives us the chance to set "Min Heap" vs "Max Heap" behavior. In other words, we can give smaller, or larger, elements the priority based on the Comparator passed in.

As written below, with Comparator returning "leftSide greater than rightSide", (similar to std::greater), this will be a Min Heap Priority Queue. Smaller elements will have higher priority.

If the Comparator was switched to returning "leftSide less than rightSide" (similar to std::less), then it would behave like a Max Heap Priority Queue. Larger elements would have priority.

Type Definition, and Comparator behavior

As you can see below, the elements we pass into the Priority Queue are of type "int string pair". Since the comparator compares the first element, the int is the priority index/key.

typedef pair<int, string> PriorityString;

struct PriorityStringComparator {
  constexpr bool operator()(const PriorityString& lhs, const PriorityString& rhs) const {
    return lhs.first > rhs.first;
  }
};

Priority Queue Operations and Interface

As you can see below, push(), pop(), top(), and empty() are used to add elements to the Priority Queue, then output elements in priority order until the Priority Queue is empty. Using an implementation that is written for you is easy!

#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <queue>

using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
using std::priority_queue;
using std::vector;
using std::string;

typedef pair<int, string> PriorityString;

struct PriorityStringComparator {
  constexpr bool operator()(const PriorityString& lhs, const PriorityString& rhs) const {
    return lhs.first > rhs.first;
  }
};

typedef priority_queue<PriorityString, vector<PriorityString>, PriorityStringComparator>
    PriorityStringQueue;

int main() {
  PriorityStringQueue q;
  q.push(make_pair(111, "1 a"));
  q.push(make_pair(333, "3 c"));
  q.push(make_pair(222, "2 b"));
  while (!q.empty()) {
    cout << q.top().second << endl;
    q.pop();
  }
  return 0;
}

Thanks

Thanks to Brian Foster for writing up these notes based on the video lectures.