Section 3 - STL Priority Queues

9B.3.1 Default Behavior of Priority Queues

As we briefly learned, there is a priority_queue adapter in STL which has the essential properties of any priority queue and is implemented using the natural underlying choice, a binary heap. This template provides the same kind of interface that an ordinary STL queue does, namely, the following three primary operations:

1. pop()
2. push()
3. top()

Remember that for STL, as with most language-supplied ADT libraries, in order to return and remove an item from a queue, you need to first call top() to get it, and then call pop() to delete it. Our FHbinHeap priority queue did this in the single operation remove().

priority_queues also support the operations size() and empty(), with the usual meanings.

Since a priority queue always returns and removes the "highest priority" item with top() and pop(), this implies that the underlying objects must have an ordering defined usually (i.e., by default) using the < operator. Furthermore, a priority_queueis a max heap, not a min heap, meaning it will pop() the largest element in < ordering.

priority_queues do not support iterators because the data is not sorted internally (bin heaps are not search trees, remember?).

Here is a little program that demonstrates the max-heap ordering of a priority_queue. The Employee < operator is using the name field as a key, which results in an alphabetical sequence.

// STL priority_queue client
// CS 2C Foothill College
#include <iostream>
#include <string>
#include <queue>
using namespace std;

class Employee
{
public:
   string name;
   int ss;
   Employee(string n, int s) : name(n), ss(s) {}
   void show() { cout << name << " " << ss << endl; }

   bool operator<(const Employee &rhs) const
   {
      return (name < rhs.name);
   }
};

typedef priority_queue<Employee> EmpQueue;

int main()
{
   EmpQueue company;
   Employee e1("mike", 111111), e2("harvey", 333333), e3("don", 222222);

   e1.show();  e2.show(); e3.show();

   cout << "---------------- and now ... " << endl;
   company.push(e1); 
   company.push(e2); 
   company.push(e3); 
   company.push(e2);  // duplicates ok

   while ( !company.empty() )
   {
      cout << company.top().name << " " << company.top().ss << endl;
      company.pop();
   }
}

We expect two things based on the above discussion:

1. The output should come at us in reverse alphabetical ordering (max heap)
2. Duplicates should be allowed.

The run verifies this.

mike 111111
harvey 333333
don 222222
---------------- and now ...
mike 111111
harvey 333333
harvey 333333
don 222222
Press any key to continue . . .

If we change the < operator to use ss# as the order key, we get this output:

mike 111111
harvey 333333
don 222222
---------------- and now ...
harvey 333333
harvey 333333
don 222222
mike 111111
Press any key to continue . . .

Again, it is what we expect. All is well.

9B.3.2 Using a Different Ordering Operation

Often we will want the priority_queue to give us the minimum, not the maximum, item when we pop/top. The obvious, but bizarre, solution is to redefine the < operator in our underlying data type to return !(key_field < rhs.key_field). This would probably have unintended side-effects in other parts of the program, which makes it a bad idea. Furthermore, if we happen to be storing primitive data on our priority_queue, we don't even have the ability to redefine the operator, anyway.

STL gives us a solution. In the priority_queue constructor, we can supply an alternative ordering operation by passing a function pointer or functor as an argument. This function replaces the default < operator as the ordering function. We would like to supply a functor or function pointer that implements the > operator, in order to reverse this behavior. It seems counter-intuitive: to get a min-heap that returns the smallest element when we pop/top, we have to tell the constructor to use the > operator. You might be thinking "min = < and max = >". But remember, < is the default operator, and priority queue already uses this to compute the maximum which it pops. So we need to fool it into thinking that the > operator means "less than", in order to get it to change the behavior.

But how, exactly, do we tell priority_queue to use the > operator? It is a two step process:

1. Define the > opeator for your class.
2. Use this syntax when defining the priority_queue:

    priority_queue< Employee, vector<Employee>, greater<Employee> > my_pq;
   

3. #include <functional> in your file.

For step 1, note that you already have a < defined, so simply add the > operator to return key_data > rhs.key_data. For step 2, we really only want to get the greater<> function pointer in there, but because it is the third parameter in a template in which the last two parameters are default parameters, we are forced to supply the second (nuisance parameter) in order to get to the third. Just use vector for this second parameter.

Why does this work? The two function templates less<> and greater<> are already defined for you -- they use the < or > operator, respectively, of your underlying data type. When you construct a function like greater<int> or greater<Employee>, you are defining a function greater(a, b) that returns a < b or a > b, respectively for the underlying data type. You could actaully define your own greater() or less(), but the point is that there is already one for you which uses the < and > operators.

Here is how we do this in our Employee example. Step 1:

   bool Employee::operator>(const Employee &rhs) const
   {
      return (name > rhs.name);
   }

Step 2:

typedef priority_queue< Employee, vector, greater > EmpQueue;

Let's show the whole enchilada:

// STL priority_queue client
// CS 2C Foothill College
#include <iostream>
#include <string>
#include <queue>
#include <functional>
using namespace std;

class Employee
{
public:
   string name;
   int ss;
   Employee(string n, int s) : name(n), ss(s) {}
   void show() { cout << name << " " << ss << endl; }

   bool operator<(const Employee &rhs) const
   {
      return (name < rhs.name);
   }
   bool operator>(const Employee &rhs) const
   {
      return (name > rhs.name);
   }
};

typedef priority_queue<Employee, vector<Employee>, greater<Employee> > EmpQueue;

int main()
{
   EmpQueue company;
   Employee e1("mike", 111111), e2("harvey", 333333), e3("don", 222222);

   e1.show();  e2.show(); e3.show();

   cout << "---------------- and now ... " << endl;
   company.push(e1); 
   company.push(e2); 
   company.push(e3); 
   company.push(e2);  // duplicates ok

   while ( !company.empty() )
   {
      cout << company.top().name << " " << company.top().ss << endl;
      company.pop();
   }
}

And we must prove that it works. Remember, we are using alphabetical ordering, so our objective is to show that we pop the smaller lexicographic elements off before the larger ones. In the original (look back) we popped mike first and done last. But now:

mike 111111
harvey 333333
don 222222
---------------- and now ...
don 222222
harvey 333333
harvey 333333
mike 111111
Press any key to continue . . .

Perfect.

9B.3.3 Maps and Sets

This same trick can be used with maps and sets. The reason it is not as commonly used in those two scenarios is that often the client does not care about the ordering operation; it is only there to define equality (so that the container knows when an object is already in the set or map). Either less() or greater() will have the same effect when used to determine equality.

However, when you iterate through sets or maps, you might want to do it in the reverse order that is default for that type. Using greater<> in the constructor for those containers will do the job. But so will using reverse iterators (a detail I won't describe here), making the need for overriding the default comparison functor even less important in these sets.