Priority Queue: Array Based Example

Priority Queue is more specialized data structure than a stack or a queue. This article provides an overview about priority queue and array based implementation.

Priority Queues Introduction:

Priority queue is like an ordinary queue which has a front and a rear and Items are removed from the front. However in this type of queue, items are ordered by key value and the item with the lowest key is always at the front. So the items are inserted in the proper position to maintain the order.

In priority queue, in many instance you access to the element with the lowest key value. So element with smallest key has the highest priority.

Besides providing quick access to the element with smallest key, you also wanted fairly quick insertion. That’s why priority queues are often implemented using data structure called “heap”.

For small numbers of items, or situations in which speed isn’t critical, implementing a priority queue with an array is satisfactory. For larger numbers of items, or when speed is critical, the heap is a better choice.

Now we will learn how to implement priority queue using simple array and later you can learn using heap.

Priority Queue Example:

package com.sneppets.dsalgo;

class MyPriorityQueue 
{
	//max priority queue array size 
	private int maxPQueueArraySize;
	
	//priority queue array
	private long[] myPQueueArray;
	
	//number of elements
	private int nElements;
	
	public MyPriorityQueue(int size)
	{
		maxPQueueArraySize = size;
		myPQueueArray = new long[maxPQueueArraySize];
		nElements = 0;
	}
	
	//insert element
	public void insert(long element)
	{
		int i;
		
		//if there are no elements in the priority queue array
		if (nElements == 0)
		{
			//insert at position 0 
			myPQueueArray[nElements++] = element;
		}
		else 
		{   
			//start at the end
			for (i=nElements-1; i>=0; i--)
			{
				//if the element to be inserted is larger than the element in the queue, 
				//then shift the existing elements upward until you insert the new element at the right place.
				if(element > myPQueueArray[i])
				{
					//shift existing element up
					myPQueueArray[i+1] = myPQueueArray[i];
				}
				else //if smaller then shifting is done
				{
					break;
				}
			}
			//insert
			myPQueueArray[i+1] = element;
			nElements++;
		}
	}
	
	//remove smallest key element
	public long remove()
	{
		return myPQueueArray[--nElements];
	}
	
	//peek at smallest key element
	public long peekSmall()
	{
		return myPQueueArray[nElements-1];
	}
	
	//return true if priority queue is empty
	public boolean isEmpty()
	{
		return (nElements==0);
	}
	
	//return true is priority queue is full
	public boolean isFull()
	{
		return (nElements == maxPQueueArraySize);
	}	
	
}

public class PriorityQueueArrayBasedExample {
	
	public static void main(String[] args)
	{
		MyPriorityQueue myPQ = new MyPriorityQueue(4);
		
		//insert 4 elements random in order
		myPQ.insert(5);
		myPQ.insert(7);
		myPQ.insert(3);
		myPQ.insert(6);
		
		while (!myPQ.isEmpty())
		{
			//removing element from priority queue will always remove the smallest element first.
			long element = myPQ.remove();
			System.out.println(element + " ");
		}
		
	}

}

Output

The insert() method checks whether there are any items; if not, it inserts one at index 0. Otherwise, it starts at the top of the array and shifts existing items upward until it finds the place where the new item should go. Then it inserts the item and increments nItems.

Note that if there’s any chance the priority queue is full, you should check for this possibility with isFull() before using insert(). The front and rear fields are not necessary in priority queue.

Efficiency of priority queues

Insertion runs in O(n) time. Deletion takes O(1) time. You can improve insertion time with heaps.

Priority Queue: Array Based Example

Priority Queues Introduction:

Priority Queue Example:

Efficiency of priority queues

Recommended Posts

References