Introduction
A Priority Queue is an abstract data structure that is open on both ends. This is a special type of Queue where data elements are arranged in order of their Priority. The Priority Queue Data Structure doesn’t conform to the standard Queue pattern of FIFO (First in First Out) because it serves the elements on the basis of their priority. Each Element in the Priority Queue has a state called Priority that is used to manage the Queue in order of this feature. One end is used to insert or enqueue an element while the other is used to remove or dequeue the element. The Priority Queue elements are served on the basis of their Priority in the order of higher or lower priority based on the requirements of the application. Queue is a famous Linear Data Structure that is used in a variety of applications. It is mainly used to manage Data Flow and Tasks within an application. It is also used in Event-Driven simulations, priority tasks, and route scheduling. It is also used in Load Balancing and interrupt handling routines.
Implementation
There are various techniques to implement a Queue such as Linked List-based, array-based, heap-based, and BinarySearchTree-based queue implementation. In either implementation, the element must have a priority associated with it so that the queue can arranged or the order of the elements according to their priority. The array-based and heap-based queue implementation can be done using fixed or dynamic arrays that can grow their size if more memory is required by the application. The LinkedList-based and BinarySearchTree-based implementation of Priority Queue always uses dynamic memory allocation which is why memory size doesn’t matter as long as the Operating System allows it to grow.
Example
Create Priority Queue : Queue is Empty
Enqueue: (Task1 1)
Queue is: [(Task1 1)]
Enqueue: (Task2 5)
Queue is: []
Enqueue: (Task3 4)
Queue is: [(Task1 1), (Task3, 4), (Task2 5)]
Enqueue: (Task4 9)
Queue is: [(Task1 1), (Task3, 4), (Task2 5), (Task4 9)]
Enqueue: (Task5 2)
Queue is: [(Task1 1), (Task5 2), (Task3, 4), (Task2 5), (Task4 9)]
Dequeue:
Queue is: [(Task1 1), (Task5 2), (Task3, 4)]
Dequeue:
Queue is: [(Task1 1), (Task5 2)]
NOTE: All elements are arranged in order of their Priority - Ascending Order
and removed element from the end.
Priority Queue RunTime Complexity
- Enqueue: Array-Based O(1) Best, Average, and Worst Case as we insert at the end of the array. LinkedList-based O(N) Worst or Average Case. It is O(1) if we use a Tail reference or the list is empty. Binary Heap or Binary Search Tree the runtime is O(Log N) in the Worst and Average case. It is O(1) if the Heap or Binary Tree is empty.
- Dequeue: Array-Based Implementation is O(N) in average and worst cases. O(1) in case there is only 1 element in the queue. In Linked-List-based implementation, it is O(1) in all best, average, and worst cases. For Heap and Binary Tree Implementation, the runtime is O(Log N) for average and worst cases. It is O(1) if there is only 1 element in the queue.
- Peek: In Array, LinkedList, and Heap Implementations it is O(1) in all cases. In Binary Search Tree it has the complexity of O(log N) in average and worst case. It is O(1) if there is only 1 element in the Binary Search Tree.
- Space complexity is O(N) where N is the number of elements stored in the Queue. The memory is dynamically allocated in the Linked list, Heap, and Binary Search Tree Implementations. The Array-based implementation can use fixed or dynamic arrays.
Code
Task.java
* The <code>Task</code> class that will encapsulates Task information:
* Name and Priority.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class Task {
// name of task
private String taskName;
// Priority
private int priority; // 0, 1, 2, 3, 4, 5 etc
/**
* Default Constructor to initialize the Objects of Task class with
* default values.
*
* @param taskName of the task
* @param priority of the task
*/
public Task(String taskName, int priority) {
this.taskName = taskName;
this.priority = priority;
}
public String getTaskName() {
return taskName;
}
public void setTaskName(String taskName) {
this.taskName = taskName;
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
@Override
public String toString() {
return String.format("(Name: %s, Priority: %d)", taskName, priority);
}
}
PriorityQueue.java
* The <code>PriorityQueue</code> class implements Array-based Priority Queue
* Data Structure that will maintain the order of elements based on their
* priority.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class PriorityQueue {
// array size
private final int SIZE = 100;
// Array to store data
private Task data [];
// count the elements
private int count;
/**
* Default Constructor to initialize the Objects of PriorityQueue class with
* default values.
*/
public PriorityQueue() {
this.data = new Task[SIZE];
this.count = 0;
}
/**
* Function to add new element into the Priority Queue.
*
* // Stored into Array as Ascending order
* // list of tasks with order of priorities: 0, 1, 2, ,3 Ascending order
* // Complexity:
* O(N) or O(1) if array is empty
*
* @param task
*/
public void enqueue(Task task) {
// if queue is full
if(this.isFull()) {
grow();
}
// Insertion
// empty priority - store it on first index
// otherwise find the correct location
int idx = 0;
// shift elements have more priority towards 1 step right
for(idx = count-1; idx >= 0 && data[idx].getPriority() > task.getPriority(); idx--) {
data[idx+1] = data[idx];
}
// fill the hole to store new task
data[idx+1] = task;
count++;
}
/**
* Remove the front element and return it.
*
* NOTE: We are maintaining ascending order priority
* So we Dequeue last element form the priority quey
*
* O(1) Always
*
* @return front element
*/
public Task dequeue() {
// check if empty
if(this.isEmpty()) {
System.out.println("This Priority Queue is empty");
return null;
}
Task task = this.data[this.count-1];
count--;
return task;
}
/**
* Function to check the number of elements in Priority Queue
*
* @return number of elements.
*/
public int size() {
return count;
}
/**
* Check if the Priority Queue is Empty.
*
* @return indicate queue is empty
*/
public boolean isEmpty() {
return count == 0;
}
/**
* Check that queue is full.
*
* @return indicate queue is full.
*/
public boolean isFull() {
return count == this.data.length;
}
/**
* Increase the size of underlying array to accommodate more elements
* whenever it is full.
*/
public void grow() {
// new array with double capacity
Task tmp [] = new Task[count * 2];
// Copy elements
for(int i=0; i<count; i++) {
tmp[i] = data[i];
}
// assigne to data
data = tmp;
}
/**
* Print the Priority Queue.
*
*/
public void print() {
if(this.isEmpty()) {
System.out.println("This Priority Queue is Empty!");
return;
}
System.out.printf("[%s", this.data[0]);
for(int i=1; i<count; i++) {
System.out.printf(", %s", data[i].toString());
}
System.out.println("]");
}
}
ArrayPriorityQueueTest.java
* The <code>ArrayPriorityQueueTest</code> is a Main class that tests the
* functionality of of the Array-Based Priority Queue Data Structure.
*
* @author CodingHelpLine
* Web: https://codinghelpline.org
*/
public class ArrayPriorityQueueTest {
/**
* Main Method - Entry Point of the Program.
*
* @param args the command line arguments
*/
public static void main(String[] args) {
// Priority Queue
PriorityQueue pq = new PriorityQueue();
// Create some task objects
Task t1 = new Task("Task7", 7);
Task t2 = new Task("Task2", 2);
Task t3 = new Task("Task9", 9);
Task t4 = new Task("Task5", 5);
Task t5 = new Task("Task13", 13);
Task t6 = new Task("Task3", 3);
// order or Priorities = 2, 3, 5, 7, 9, 13
pq.enqueue(t1);
pq.print();
pq.enqueue(t2);
pq.print();
pq.enqueue(t3);
pq.print();
pq.enqueue(t4);
pq.print();
pq.enqueue(t5);
pq.print();
pq.enqueue(t6);
pq.print();
// removal
while(!pq.isEmpty()) {
System.out.printf("Task Removed: %s%n", pq.dequeue());
}
}
}