An Overview of the Priority Queue
Let's take a closer look at the priority queue and a sample Java implementation.
Join the DZone community and get the full member experience.
Join For FreeThe priority queue is a somewhat similar data structure to the queue. The difference lies in how the elements are being processed:
 A standard queue strictly follows the FIFO (FirstInLastOut) principle.
 A priority queue does not follow the FIFO principle.
In a priority queue, the elements are being removed from the queue based on their priority. This translates to the requirement that:
Every element in a priority queue must have a priority associated with it.
As you might have guessed, the element with the highest priority is removed from the queue (dequeued).
But how do should you define the priority of the elements in the queue?
Defining Priorities to Elements
Basically, you have two alternatives for defining priorities to the elements in the queue. You can either
 Order elements based on their natural ordering.
 Order elements with a custom Comparator.
In this article, we'll focus on how to implement a priority queue. So for simplicity's sake, we'll order the elements based on their natural ordering.
In our example, the priority queue will be limited to int
, so natural ordering is perfectly fine. However, keep in mind that this is for demonstration purposes only.
If you were to implement a priority queue in real life, you probably want to make use of generics — or just do like any other developer and use the builtin java.util.PriorityQueue.
To keep our example implementation compliant with the Java specification, the least element is defined as the element with the highest priority.
Priority Queue Operations
The most basic set of operations for any implementation of a queue is:

enqueue
— Inserting an element into the queue. 
dequeue
— Removing an element from the queue. 
isEmpty
— Returning true if the queue is empty. 
size
— Returning the size/number of elements in the queue. 
contains
— Returning true if the queue contains the given element. 
peek
— Returning the front element of the queue, without removing it.
Please note that the Java implementation of the priority queue uses different names for the methods. In a production environment, I highly suggest that you use the default implementation of the priority queue, instead of "homegrowing" it.
Implementation of the Priority Queue
Now, let's implement a nongenericpriority queue in Java. We'll implement one operation at a time, but first, we have to decide which inner data structure we want to use.
An array is perfectly fine, so we'll roll with that.
For those of you that are familiar with arrays, you probably know that arrays have a fixedsize in Java. Our solution to this problem is that we'll provide a private method double()
, which "increases" the capacity of the array.
The code skeleton for the priority queue is presented below.
package priorityqueue;
public class PriorityQueue {
private int[] innerArray;
private int size;
public PriorityQueue() {
this.innerArray = new int[10];
size = 0;
}
public void enqueue(int x) {
}
public int dequeue() {
return 0;
}
public int peek() {
return 0;
}
public boolean contains(int x) {
return false;
}
public boolean isEmpty() {
return false;
}
public int size() {
return 0;
}
private void doubleArray() {
}
}
As you can see, we use an int
array as the inner data structure, and initials it's default size to 10 in the constructor. We also provide a private variable size
to keep track of the number of elements.
Implementing Size, isEmpty, and Peek
The implementation of the size
and isEmpty
methods are as easy as it gets. One thing to keep in mind: The size
variable is used so we can avoid having to loop through the array and count "valid" integers. In the constructor, all indexes have been assigned an int
with the value of 0.
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
What about peek
? It is, in fact, quite simple as well: If the size is more than 0, we return the first element. If it is less than zero, we throw a NoSuchElementException
.
public int peek() {
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
return innerArray[0];
}
Implementing Contains
It's time to implement contains
, which should return true if the queue contains the provided parameter.
How should we implement this? One naive way would be to simply loop through the array, and return true if we encounter the provided int
in the array.
However, this will not work! What if the user provides us with 0? As previously mentioned, the array is initially assigned int
s with the default value — which is zero.
In other words: We'll get a false positive.
The solution? Only loop through the indexes which we know contains inserted values.
public boolean contains(int x) {
// Check for empty.
if(isEmpty())
return false;
// Looping through the positions which contains inserted values,
// ignoring trailing default 0 values.
for(int i = 0; i < size; i++) {
// Comparing
if(innerArray[i] == x)
return true;
}
// None found
return false;
}
Implementing Enqueue and Dequeue
First, let's think about what we want to happen if we insert/enqueue an element. Note that we ignore the doubleArray
method for now. We want inserted elements to be placed in the queue, in the correct position, according to its priority.
This visualization of the enqueue
operation tells us that we'll have to shift all elements of lower priority one position up in the array.
public void enqueue(int x) {
// If it is empty, insert in front
if (size == 0) {
size++;
innerArray[0] = x;
return;
}
// If full, we'll have to double the array
if (size() == innerArray.length)
doubleArray();
// Looping through
int temp = x;
for (int i = 0; i < size; i++) {
// If priority is higher, ie. values is lower, we shift.
if (x <= innerArray[i]) {
int next;
temp = innerArray[i];
innerArray[i] = x;
// Shifting
while (i < size  1) {
next = innerArray[i + 1];
innerArray[i + 1] = temp;
temp = next;
i++;
}
break;
}
}
// Placing, increasing size.
innerArray[size] = temp;
size++;
}
Dequeue
works very much in the same way.
public int dequeue() {
// NoSuchElement
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
// Storing first int for return
int retValue = innerArray[0];
// Shifting all values downwards
for (int i = 1; i < size; i++) {
innerArray[i  1] = innerArray[i];
}
innerArray[size  1] = 0;
size;
return retValue;
}
Implementing doubleArray
All that's left now is to implement the method that doubles the array if we exceed the initial size. We simply copy the array's content over to a new array, which is twice the size.
private void doubleArray() {
int[] newArr = new int[innerArray.length * 2];
for(int i = 0; i < innerArray.length; i++) {
newArr[i] = innerArray[i];
}
innerArray = newArr;
}
Complete Implementation
The complete implementation can be found below. Happy coding!
package priorityqueue;
import java.util.NoSuchElementException;
public class PriorityQueue {
private int[] innerArray;
private int size;
public PriorityQueue() {
this.innerArray = new int[10];
size = 0;
}
public void enqueue(int x) {
// If it is empty, insert in front
if (size == 0) {
size++;
innerArray[0] = x;
return;
}
// If full, we'll have to double the array
if (size() == innerArray.length)
doubleArray();
// Looping through
int temp = x;
for (int i = 0; i < size; i++) {
// If priority is higher, ie. values is lower, we shift.
if (x <= innerArray[i]) {
int next;
temp = innerArray[i];
innerArray[i] = x;
// Shifting
while (i < size  1) {
next = innerArray[i + 1];
innerArray[i + 1] = temp;
temp = next;
i++;
}
break;
}
}
// Placing, increasing size.
innerArray[size] = temp;
size++;
}
public int dequeue() {
// NoSuchElement
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
// Storing first int for return
int retValue = innerArray[0];
// Shifting all values downwards
for (int i = 1; i < size; i++) {
innerArray[i  1] = innerArray[i];
}
innerArray[size  1] = 0;
size;
return retValue;
}
public int peek() {
if (isEmpty())
throw new NoSuchElementException("The queue is empty");
return innerArray[0];
}
public boolean contains(int x) {
// Check for empty.
if (isEmpty())
return false;
// Looping through the positions which contains inserted values,
// ignoring trailing default 0 values.
for (int i = 0; i < size; i++) {
// Comparing
if (innerArray[i] == x)
return true;
}
// None found
return false;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private void doubleArray() {
int[] newArr = new int[innerArray.length * 2];
for(int i = 0; i < innerArray.length; i++) {
newArr[i] = innerArray[i];
}
innerArray = newArr;
}
}
Published at DZone with permission of Anders Olsen. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments