Customizing Priority Queues in C++

seagull
A nifty feature of priority queues in C++ is that you can implement a max heap or a min heap by simply changing the compare type. For most purposes, std::less and std::greater can do the job, provided that you use built-in types or custom types that provide a < or > operator and strict weak ordering.

A priority_queue can be implemented by a couple of different containers, with vector being the default.  In addition, you can provide a Compare type that must comply with strict weak ordering.

 

template<typename T, typename Container=std::vector<T>,
    typename Compare=std::less<typename Container::value_type>> 
        class priority_queue;

Here’s a priority queue with a max heap, followed by a priority queue with a min heap (and yes, it’s counterintuitive that max heap uses std::less and min heap uses std::greater).

priority_queue<int, vector<int>, less<int>> max_pq;
priority_queue<int, vector<int>, greater<int>> min_pq;

max_pq.push(1); max_pq.push(2); max_pq.push(3);
min_pq.push(1); min_pq.push(2); min_pq.push(3);

// prints 3 2 1
while (!max_pq.empty()) {
  cout << max_pq.top() << ' ';
  max_pq.pop();
}
cout << '\n';

// prints 1 2 3
while (!min_pq.empty()) {
  cout << min_pq.top() << ' ';
  min_pq.pop();
}
cout << '\n'

Nothing earth-shattering here. However, if you have a user-defined type, you have several mechanisms at your disposal. Assume that we have the following type

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;
};

A student has a GPA and a given age.  We want to give priority to students with the highest GPA.  Let’s look at the options:

Provide comparison operators

Comparison operators can be done as a member function, as a friend function if it accesses private member variables of the type, or as a free function if it makes use of only publicly accessible parts of the type. Once you have comparison operators, the type can be safely used with std::less and std::greater (should you provide both operators).

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;

  // Define it as a member function
  bool operator < (const student& rhs) const { return gpa < rhs.gpa; }

  // Define it as as a friend if it accesses private member variables,
  // or as a free function if it does not.
  // (in this case it does not, but it's for illustration).
  friend bool operator >(const student& lhs, const student& rhs);
};

bool operator >(const student& lhs, const student& rhs) {
  return gpa > rhs.gpa;
}

int main() {
  priority_queue<student, vector<student>, std::less> max_gpa;
  priority_queue<student, vector<student>, std::greater> min_gpa;

  student alice(3.98,15), bob(3.97, 18), charlie(3.95, 16);
  max_gpa.push(alice);
  max_gpa.push(bob);
  max_gpa.push(charlie);

  // prints 3.98 3.97 3.95
  while (!max_gpa.empty()) {
    cout << max_gpa.top().gpa << ' ' << endl;
    max_gpa.pop();
  }

  min_gpa.push(alice);
  min_gpa.push(bob);
  min_gpa.push(charlie);

  // prints 3.95, 3.97, 3.98
  while (!min_gpa.empty()) {
    cout << min_gpa.top().gpa << ' ' << endl;
    min_gpa.pop();
  }
}

Roll your own  function object…

Simply define a type with a function call operator as shown below. The signature for the function call operator makes it a binary predicate.

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;
};

struct less_gpa {
  bool operator() (const student& lhs, const student& rhs) { 
    return lhs.gpa < rhs.gpa;
  }
};

struct greater_gpa {
  bool operator() (const student& lhs, const student& rhs) { 
    return lhs.gpa > rhs.gpa;
  }
};

int main() {
  priority_queue<student, vector<student>, less_gpa> max_gpa;
  priority_queue<student, vector<student>, greater_gpa> min_gpa;

  student alice(3.98,15), bob(3.97, 18), charlie(3.95, 16);
  max_gpa.push(alice);
  max_gpa.push(bob);
  max_gpa.push(charlie);

  // prints 3.98 3.97 3.95
  while (!max_gpa.empty()) {
    cout << max_gpa.top().gpa << ' ';
    max_gpa.pop();
  }
  cout << '\n';

  min_gpa.push(alice);
  min_gpa.push(bob);
  min_gpa.push(charlie);

  // prints 3.95, 3.97, 3.98
  while (!min_gpa.empty()) {
    cout << min_gpa.top().gpa << ' ';
    min_gpa.pop();
  }
  cout << '\n';
}

…Or use std::binary_function as the base class for your function object

The only benefit to using a binary function object is if you need the predefined typedefs for the argument and return types and use them in generic programming.  You still must provide the function call operator and be able to access the necessary elements.

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;
};

struct less_gpa : public std::binary_function<student, student, bool> {
  bool operator() (const student& lhs, const student& rhs) { 
    return lhs.gpa < rhs.gpa;
  }
};

struct greater_gpa : public std::binary_function<student, student, bool> {
  bool operator() (const student& lhs, const student& rhs) { 
    return lhs.gpa > rhs.gpa;
  }
};

Use a lambda expression

Technically, you will use a copy of the closure generated by the lambda expression and assigned to the f variable. Scott Meyers gives a great explanation here.

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;
};

int main()  
 // Binary predicate with lambda
  auto f = [](const student& lhs, const student& rhs) -> bool {
    return lhs.gpa < rhs.gpa;
  };

  // Notice the decltype and passing f in the constructor
  priority_queue<student, vector<student>, decltype(f)> max_gpa(f);

  student alice(3.98,15), bob(3.97, 18), charlie(3.95, 16);

  max_gpa.push(alice);
  max_gpa.push(bob);
  max_gpa.push(charlie);

  // prints 3.98 3.97 3.95
  while (!max_gpa.empty()) {
    cout << max_gpa.top().gpa << ' ';
    max_gpa.pop();
  }
  cout << '\n';

And if you need two or more criteria…

All of the options above will work when you have only one criterion for the priority queue, but what happens if you want to apply two or more criteria?  Say that you want to give the highest priority to the student with the highest GPA, but in case of a tie, you want to give it to the younger student. In this case you can apply any of the methods above, but in your comparison, you have to consider the additional criteria.  In the code below, when the age GPA is the same, the return value is true if the lhs student is older–and in a max heap priority queue, the younger student will be given higher priority.

struct student {
  student(double gpa, int age) : gpa{gpa}, age{age} {}
  
  double gpa;
  int age;
};

int main()  
  // Binary predicate with lambda
  auto f = [](const student& lhs, const student& rhs) -> bool {
    if (lhs.gpa < rhs.gpa)
      return true;
    else if (lhs.gpa == rhs.gpa && 
             lhs.age > rhs.age)
      return true;
    else
      return false;
  };

  // Notice the decltype and passing f in the constructor
  priority_queue<student, vector<student>, decltype(f)> max_gpa(f);

  student alice(3.98,15), bob(3.97, 18), charlie(3.98, 16);

  max_gpa.push(alice);
  max_gpa.push(bob);
  max_gpa.push(charlie);

  // prints (3.98, 15) (3.98, 16) (3.97, 18)
  while (!max_gpa.empty()) {
    const student& s = max_gpa.top();
    cout << '(' << s.gpa << ", " << s.age << ')' << ' ';
    max_gpa.pop();
  }
 cout << '\n';

 

Advertisements
This entry was posted in algorithms, data structures, software. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s