The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Home Queues and Priority Queues Array Implementation of Priority Queue
 
del.icio.us Reddit Facebook StumbleUpon MySpace Twitter

Array Implementation of Priority Queue

In the implementation of the Priority Queue, every time we specify the type of the items in the queue, we specify the type of the cargo. For example, the instance variables are an array of Node and an integer:

class PriorityQueue {
    private:
       pvector<Node> array;
       int index;
};

As usual, index is the index of the next available location in the array. The instance variables are declared private so that other classes cannot have direct access to them.

The constructor and empty are similar to what we have seen before. I chose the initial size for the array arbitrarily.

    public:
      PriorityQueue () {
        array.resize(16);
        index = 0;
      }

      bool empty () {
        return index == 0;
      }

insert is similar to push:

    void insert (Node item) {
        if (index == array.length()) {
            resize ();
        }
        array[index] = item;
        index++;
    }

I omitted the implementation of resize. The only substantial method in the class is remove, which has to traverse the array to find and remove the largest item:

    Node remove () {
        if (index == 0) return null;

        int maxIndex = 0;

        // find the index of the item with the highest priority
        for (int i=1; i<index; i++) {
            if (array[i].cargo > array[maxIndex].cargo) {
                maxIndex = i;
            }
        }

        // move the last item into the empty slot
        index--;
        array[maxIndex] = array[index];
        return array[maxIndex];
   }

As we traverse the array, maxIndex keeps track of the index of the largest element we have seen so far. What it means to be the "largest" is determined by >.
Home Queues and Priority Queues Array Implementation of Priority Queue

Last Update: 2005-12-05