Priority Queue in Java

Introduction

In this article we are going to describe how the priority queue is developed in Java. In Java you can easily make a priority queue with the help of the Java API. Java a sprat class named PriorityQueue. The PriorityQueue class implements the Queue interface. When items are added to a PriorityQueue they are not ordered by First In, First Out. Instead, all items in a PriorityQueue must be comparable (either by implementing the Comparable interface or by a Comparator) which is used to sort the items in the list.

PriorityQueue

A priority queue is a collection of elements in which each element has been assigned a priority and depending on that order each element is deleted and processed depending on the following rules:

• An element of higher priority is processed before any element of lower priority.
• Two elements with the same priority are processed according to the order in which they were added to the queue.

A PriorityQueue is a queue where a sorted order is permanently imposed on the items it contains; in queue terms, the highest-priority element is at the head of the queue (and the lowest is at the tail of the queue) queue operations are efficient: that is, removing the highest-priority element and adding any element are both efficient operations.

Non-queue operations (such as searching for an item that isn't at the head of the queue) are not efficient.

Remember that a queue in general is essentially a structure optimized to add things to one end and remove them from the other. With a priority queue, we can envisage this queue as a permanently-sorted list, so that the highest priority element is always at one end and the lowest-priority element at the other. In this case, we don't actually add an element to the "end": each element added is automatically slotted in to the relevant place in the list depending on its priority.

Example

public class PriorityQDemo

{

// array in sorted order, from max at 0 to min at size-1

private int maxSize;

private long[] queArray;

private int nItems;

public PriorityQDemo(int s)

{

maxSize = s;

queArray = new long[maxSize];

nItems = 0;

}

public void insert(long item)

{

int i;

if (nItems == 0)

// insert at 0

queArray[nItems++] = item;

else

{

// start at end,

for (i = nItems - 1; i >= 0; i--)

{

// if new item larger,

if (item > queArray[i])

// shift upward

queArray[i + 1] = queArray[i];

else

// if smaller,

break;

// done shifting

}

queArray[i + 1] = item;

// insert it

nItems++;

} // end else (nItems > 0)

}

public long remove()

{

return queArray[--nItems];

}

public long peekMin()

{

return queArray[nItems - 1];

}

public boolean isEmpty()

{

return (nItems == 0);

}

public boolean isFull()

{

return (nItems == maxSize);

}

public static void main(String[] args)

{

PriorityQDemo thePQ = new PriorityQDemo(5);

thePQ.insert(30);

thePQ.insert(50);

thePQ.insert(10);

thePQ.insert(40);

thePQ.insert(20);

while (!thePQ.isEmpty())

{

long item = thePQ.remove();

// 10, 20, 30, 40, 50

System.out.print(item + " ");

}

System.out.println("");

}

}

Output

You can see that the insertion order is different and displays in a different order.

Resources

Working With Threads in Java
Stack and Queue in C#
Adding message in a Windows Azure Queue
Microsoft Message Queue(MSMQ)
Use of ByteStreams and CharacterStreams in JAVA