Priority Queue Tutorial (C#, C++, Java)


What is a Priority Queue?

An ADT whose primary operations of insert of records, and deletion of the greatest (or, in an alternative implementation, the least) valued record. Most often implemented using the heap data structure. The name comes from a common application where the records being stored represent tasks, with the ordering values based on the priorities of the tasks.

Programming Language(s):

In languages such as C++ and Java, you can easily use a priority queue when you include or import from the standard library.

  • In C++, you can use a priority queue when you include, and declare a new priority queue object like so:
    #include <string>
    #include <queue>
    #include <iostream>
    
    using namespace std;  // This is to make available the names of things defined in the standard library.
    
    int main()
    {
        priority_queue<string>; // Creates a priority queue pq to store strings, and initializes the queue to be empty.
    
        pq.push("the quick");
        pq.push("fox");
        pq.push("jumped over");
        pq.push("the lazy dog");
    
        // The strings are ordered inside the priority queue in lexicographic (dictionary) order:
        // "fox", "jumped over", "the lazy dog", "the quick";
        //  The lowest priority string is "fox";, and the highest priority string is"the quick"
    
        while (!pq.empty()) {
           cout << pq.top() << endl;  // Print highest priority string
           pq.pop();                    // Remove highest priority string
        }
    
        return 0;
    }
            

    Furthermore, you specify more parameters such as some type of comparer, a vector, and data type like so:

    
    #include <iostream>
    #include <queue>
    #include <iomanip>
    
    using namespace std;
    
    struct Time {
        int h; // >= 0
        int m; // 0-59
        int s; // 0-59
    };
    
    class CompareTime {
    public:
        bool operator()(Time& t1, Time& t2)
        {
           if (t1.h < t2.h) return true;
           if (t1.h == t2.h && t1.m < t2.m) return true;
           if (t1.h == t2.h && t1.m == t2.m &amp;amp;&amp;amp; t1.s < t2.s) return true;
           return false;
        }
    };
    
    int main()
    {
        priority_queue<Time, vector<Time>, CompareTime> pq;
    
        // Array of 4 time objects:
    
        Time t[4] = { {3, 2, 40}, {3, 2, 26}, {5, 16, 13}, {5, 14, 20}};
     
        for (int i = 0; i < 4; ++i)
           pq.push(t[i]);
    
        while (! pq.empty()) {
           Time t2 = pq.top();
           cout << setw(3) << t2.h << " " << setw(3) << t2.m << " " <<
           setw(3) << t2.s << endl;
           pq.pop();
        }
    
        return 0;
    }
    
    
  • In Java, you can use a priority queue when you import java.util.PriorityQueue, and declare a new priority queue object like so:
    import java.util.PriorityQueue;
    
    public class PriorityQueueTest
    {
    
    	public static void main(String[] args)
            {
    		int[] ia = { 1, 10, 5, 3, 4, 7, 6, 9, 8 };
    		PriorityQueue<Integer> pq1 = new PriorityQueue<Integer>();
    
    		// use offer() method to add elements to the PriorityQueue pq1
    		for (int x : ia)
                    {
    			pq1.offer(x);
    		}
    
    		System.out.println("pq1: " + pq1);
            }
    }
            
  • Because C#.Net has no actual Priority Queue in the standard library, this tutorial covers an implementation with all useful methods and its a chance to learn how a priority queue works from scratch.

How it works:

Most, if not all, priority queue implementations use a heap (can be either min or max heap). Priority Queue is implemented using a heap because of efficiency and intuitiveness. The node with the most important priority is at the root of the heap (or the front of the queue). You can use either a min-heap or max-heap implementation for the PQ, depending on the situation. For example, Dijkstra’s shortest path algorithm which finds the shortest route to take from a source or starting point, tends to use a min-heap in that the lesser distance, the better.

Priority Queue illustration

Heap

Heap based Priority Queue

Priority Queue Animation (java applet using max-heap)

Methods/Functions:

  • enqueue(): inserts into the priority queue, implementation is derived from the heap insertion method
  • dequeue_min(): dequeues the front of the queue, or in other words, the root of the heap is removed, implementation is derived from heap “removeMin()”
  • decrease_priority(): takes a new key/priority parameter and looks up a target node, updates the node’s priority, and then siftUp() is performed to correct the queuing order
  • empty(): checks for emptiness in the queue
  • peek(): returns the front of the queue, because we use a heap, the code is pretty much like so: return array[0];
  • display(): displays the queue
  • Methods derived from heap data structure: siftUp(), siftDown(), getParentIndex(), getLeftChild(), getRightChild()

Pseudo-code for dequeue_min, siftUp, siftDown, and decrease-priority

  • HEAP-EXTRACT-MIN (A)
    1    if  heap-size [A] < 1
    2          then error “Heap underflow”
    3     min ←  A[1]
    4     A[1] ←  A[ heap-size [A]]
    5     heap-size [A] ←  heap-size [A]-1
    6     SIFTDOWN(0)
    7     return  min

 

  • HEAP-SIFT-UP (A,i)
    1    while  i > 1 and A[ PARENT (i) ] < A[i]
    2                  do Swap A[i] with A[ PARENT (i) ]
    3                         i ←  PARENT (i)

 

  • HEAP-DECREASE-KEY (A,i,k)
    1    if  k > A[i]
    2          then error “New key is larger than current key”
    3     A[i] ←  k
    4     HEAP-SIFT-UP (A,i)

 

  • HEAP-SIFT-DOWN (index)
    1   left = getLeft, right = GetRight, min-index, temp
    2   if right >= heapSize then if left >= heapSize then return; else then min-index = left
    3   else then  array[left] <= array[right] then min-index = left; else then min-index = right 4 if array[index] > array[min-index]
    5     temp = array[min-index]
    6     array[min-index] = array[index]
    7     array[index] = temp
    8     SIFTDOWN(min-index)

Priority Queue C# Implementation:

    ///

<summary>
    /// Priority Queue Data Structure
    /// Author: Karim Oumghar
    /// </summary>


    /// <typeparam name="T">Templatized Priority Queue</typeparam>
    class PriorityQueue<T>
    {
        class Node
        {
            public T data;
            public int priority;
            public static bool operator <(Node n1, Node n2)
            {
                return (n1.priority < n2.priority); } public static bool operator >(Node n1, Node n2)
            {
                return (n1.priority > n2.priority);
            }
            public static bool operator <=(Node n1, Node n2)
            {
                return (n1.priority <= n2.priority); } public static bool operator >=(Node n1, Node n2)
            {
                return (n1.priority >= n2.priority);
            }
            public static bool operator ==(Node n1, Node n2)
            {
                return (n1.priority == n2.priority && (dynamic)n1.data == (dynamic)n2.data);
            }
            public static bool operator !=(Node n1, Node n2)
            {
                return (n1.priority != n2.priority && (dynamic)n1.data != (dynamic)n2.data);
            }
            public override bool Equals(object obj)
            {
                return base.Equals(obj);
            }
            public override int GetHashCode()
            {
                return base.GetHashCode();
            }
        }
        Node[] arr;
        private int count;
        private const int arrSize = 100;
        public PriorityQueue()
        {
            arr = new Node[arrSize];
            count = 0;
        }
        public void Enqueue(T nData, int priority)
        {
            Node nObj = new Node();
            nObj.data = nData;
            nObj.priority = priority;
            if (count == arr.Length)
            {
                throw new Exception("Priority Queue is at full capacity");
            }
            else
            {
                arr[count] = nObj;
                count++;
                siftUp(count - 1);
            }
        }
        private void siftUp(int index)
        {
            int parentIndex;
            Node temp;
            if (index != 0)
            {
                parentIndex = getParentIndex(index);
                if (arr[parentIndex] > arr[index])
                {
                    temp = arr[parentIndex];
                    arr[parentIndex] = arr[index];
                    arr[index] = temp;
                    siftUp(parentIndex);
                }
            }
        }
        private int getParentIndex(int index)
        {
            return (index - 1) / 2;
        }
        public void decrease_priority(T target, int newPriority)
        {
            //find the target first
            Node n = new Node();
            n.data = target;
            for (int i = 0; i < arr.Length; i++) { if (arr[i] == n) { if (newPriority > arr[i].priority)
                    {
                        throw new Exception("New priority assignment must be less than current priority");
                    }
                    else
                    {
                        arr[i].priority = newPriority;
                        siftUp(i);
                    }
                    break;
                }
            }
        }
        public T dequeue_min()
        {
            Node nObj;
            if (count == 0)
            {
                throw new Exception("Priority Queue is empty");
            }
            else
            {
                nObj = arr[0];
                arr[0] = arr[count - 1];
                count--;
                if (count > 0)
                {
                    siftDown(0);
                }
            }
            arr[count] = null;//set the last index to null after a dequeue min
            return nObj.data;
        }
        public void siftDown(int nodeIndex)
        {
            int leftChildIndex, rightChildIndex, minIndex;
            Node temp;
            leftChildIndex = getLeftChildIndex(nodeIndex);
            rightChildIndex = getRightChildIndex(nodeIndex);
            if (rightChildIndex >= count)
            {
                if (leftChildIndex >= count)
                {
                    return;
                }
                else
                {
                    minIndex = leftChildIndex;
                }
            }
            else
            {
                if (arr[leftChildIndex] <= arr[rightChildIndex]) { minIndex = leftChildIndex; } else { minIndex = rightChildIndex; } } if (arr[nodeIndex] > arr[minIndex])
            {
                temp = arr[minIndex];
                arr[minIndex] = arr[nodeIndex];
                arr[nodeIndex] = temp;
                siftDown(minIndex);
            }
        }
        private int getLeftChildIndex(int index)
        {
            return (2 * index) + 1;
        }
        private int getRightChildIndex(int index)
        {
            return (2 * index) + 2;
        }
        public T peek()
        {
            return arr[0].data;
        }
        public bool empty()
        {
            return (count == 0);
        }
    }
Output of Priority Queue program

Example Output of Priority Queue program

Advertisements

One thought on “Priority Queue Tutorial (C#, C++, Java)

  1. Pingback: Graphs and Dijkstra’s Algorithm (C#) | Bits and Pieces of Code

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