Monthly Archives: August 2013

Custom priority queue in C++

Posted on by
Reply

A priority queue container is a basis for some algorithms on graphs, for instance, Dijkstra Shortest Path.

An implementation has to be efficient in terms of speed while allow to get access to (retrieve and change) a queue elements randomly.

STL library implementation of the priority queue does not support random access to its elements.

Here is presented a custom implementation of a priority queue with a random access property. To make access operations reasonably fast the bucket sorting algorithm is leveraged.

A bucket sorting idea is to have a sorted container of element lists that have equal values. It can be implemented an array with pointers to lists of elements. We follow another approach that could slightly impact speed of the algorithm while removing restrictions caused by the static nature of array. We used a tree (STL map) to store lists. Another option is to use a dynamic array (STL vector) that could be more efficient on the big data sets.

Our PriorityQueue class is built upon two STL maps of custom types queue_t and Id2ValueMap_t. The first map is a collection of STL set containers, that are, actually, the buckets. While the second map is used for instant access to the value of any element.

Priority queue

Priority queue

Aforementioned class has the following declaration.

typedef std::set<uint> bucket_t;
typedef std::map<uint, bucket_t> queue_t;
typedef std::map<uint, uint> id2ValueMap_t;

class PriorityQueue
{
public:
   PriorityQueue();

   void addElement(uint id, uint value);
   bool removeElement(uint id);

   bool getValue(uint id, uint* pValue) const;
   bool modifyValue(uint id, uint oldValue, uint newValue);

   bool getMinimalElement(uint* pId) const;

   bool isEmpty() const;
   bool contains(uint id) const;
   void clear();

private:
   queue_t  _queue;
   Id2ValueMap_t _id2ValueMap;
};

It is critical that both maps contain relevant and consistent information thus inserting to queue will look as follows. Error checking is omitted in all methods implementations for the sake of clarity.

void PriorityQueue:: addElement(uint id, uint value)
{
   queue_t& queue = _queue[value];
   queue.insert(id);

   _id2ValueMap[id] = value;
}

Retrieving an element with minimal value will look similar to the next code.

bool PriorityQueue::getMinimalElement(uint* pId) const
{
   queue_t::const_iterator queue_iter = _queue.begin();

   if (queue_iter == _queue.end())
   {
       return false; /* queue is empty */
   }

   const bucket_t& bucket = queue_iter>second;

   bucket_t::const_iterator bucket_iter = bucket.begin();

   if (bucket_iter == bucket.end())
   {
       return false; /* list is empty */
   }

   *pId = *bucket_iter;

   return true;
}

The following method is used to change a value of an element. Basically it is removing the element from the bucket in first map, adding it again to another bucket plus updating value in the map that is used to quickly get value based on the identifier.

bool modifyValue(uint id, uint oldValue, uint newValue)
{
   queue_t::iterator queue_iter;

   queue_iter = _queue.find(oldValue);

   if (queue_iter == _queue.end())
   {
       return false; /* no element found */
   }

   bucket_t& bucket = queue_iter->second;

   bucket.erase(id);

   return addElement(id, newValue);
}

References
http://www.cplusplus.com/reference/queue/priority_queue/
https://en.wikipedia.org/wiki/Bucket_sort