Priority Queues Algorithm
Priority queues are a crucial data structure in computer science and programming that help manage a collection of elements with each element having an associated priority value. The Priority Queues Algorithm is a set of rules and methods for organizing these elements based on their priorities. This algorithm allows efficient access to the highest or lowest priority element, depending on the implementation. Common implementations of priority queues include binary heaps, Fibonacci heaps, and binary search trees. They are widely used in various applications such as scheduling processes in operating systems, handling requests in network routers, or even in sorting algorithms like heapsort.
The primary operations supported by the Priority Queues Algorithm are insertion, deletion, and retrieval of the highest (or lowest) priority element. When inserting an element into the priority queue, the algorithm determines its position based on its priority value, ensuring that the highest or lowest priority element remains accessible at the top of the queue. Deletion involves removing the highest or lowest priority element from the queue and reorganizing the remaining elements to maintain the priority order. Retrieval simply returns the highest or lowest priority element without removing it from the queue. The efficiency of these operations varies depending on the underlying data structure used for implementation. For instance, using a binary heap, insertion and deletion can be performed in O(log n) time complexity, while retrieval takes O(1) time.
package DataStructures.Queues;
/**
* This class implements a PriorityQueue.
* <p>
* A priority queue adds elements into positions based on their priority.
* So the most important elements are placed at the front/on the top.
* In this example I give numbers that are bigger, a higher priority.
* Queues in theory have no fixed size but when using an array
* implementation it does.
*/
class PriorityQueue {
/**
* The max size of the queue
*/
private int maxSize;
/**
* The array for the queue
*/
private int[] queueArray;
/**
* How many items are in the queue
*/
private int nItems;
/**
* Constructor
*
* @param size Size of the queue
*/
public PriorityQueue(int size) {
maxSize = size;
queueArray = new int[size];
nItems = 0;
}
/**
* Inserts an element in it's appropriate place
*
* @param value Value to be inserted
*/
public void insert(int value) {
if (isFull()) {
throw new RuntimeException("Queue is full");
} else {
int j = nItems - 1; // index of last element
while (j >= 0 && queueArray[j] > value) {
queueArray[j + 1] = queueArray[j]; // Shifts every element up to make room for insertion
j--;
}
queueArray[j + 1] = value; // Once the correct position is found the value is inserted
nItems++;
}
}
/**
* Remove the element from the front of the queue
*
* @return The element removed
*/
public int remove() {
return queueArray[--nItems];
}
/**
* Checks what's at the front of the queue
*
* @return element at the front of the queue
*/
public int peek() {
return queueArray[nItems - 1];
}
/**
* Returns true if the queue is empty
*
* @return true if the queue is empty
*/
public boolean isEmpty() {
return (nItems == 0);
}
/**
* Returns true if the queue is full
*
* @return true if the queue is full
*/
public boolean isFull() {
return (nItems == maxSize);
}
/**
* Returns the number of elements in the queue
*
* @return number of elements in the queue
*/
public int getSize() {
return nItems;
}
}
/**
* This class implements the PriorityQueue class above.
*
* @author Unknown
*/
public class PriorityQueues {
/**
* Main method
*
* @param args Command Line Arguments
*/
public static void main(String[] args) {
PriorityQueue myQueue = new PriorityQueue(4);
myQueue.insert(10);
myQueue.insert(2);
myQueue.insert(5);
myQueue.insert(3);
// [2, 3, 5, 10] Here higher numbers have higher priority, so they are on the top
for (int i = 3; i >= 0; i--)
System.out.print(myQueue.remove() + " "); // will print the queue in reverse order [10, 5, 3, 2]
// As you can see, a Priority Queue can be used as a sorting algotithm
}
}
