Min Priority Queue Algorithm
The Min Priority Queue Algorithm is a data structure that is used to store and manage a collection of elements, where each element has an associated priority value. This algorithm is designed to efficiently find and extract the element with the lowest priority in the collection. It is a fundamental component of various computer algorithms, such as graph traversal, shortest path finding, and event-driven simulations. The priority queue can be implemented using various data structures, such as arrays, linked lists, or binary heaps, with the latter being the most popular choice due to its efficiency in both time and space complexity.
In a min priority queue, the elements are organized in such a way that the element with the lowest priority is always at the root of the tree or the front of the queue. The two primary operations that can be performed on a min priority queue are insertion and extraction. When an element is inserted into the priority queue, it is placed in the appropriate position based on its priority value, ensuring that the min priority element remains at the root. When the element with the lowest priority is extracted, it is removed from the queue, and the remaining elements are reorganized to maintain the min priority queue property. This reorganization process, known as heapify or sift-down, efficiently restores the priority queue's structure in logarithmic time. Overall, the min priority queue algorithm provides an efficient way to manage and process elements based on their priority, making it a crucial tool in many computer algorithms and applications.
package DataStructures.Heaps;
/**
* Minimum Priority Queue
* It is a part of heap data structure
* A heap is a specific tree based data structure
* in which all the nodes of tree are in a specific order.
* that is the children are arranged in some
* respect of their parents, can either be greater
* or less than the parent. This makes it a min priority queue
* or max priority queue.
* <p>
* <p>
* Functions: insert, delete, peek, isEmpty, print, heapSort, sink
*/
public class MinPriorityQueue {
private int[] heap;
private int capacity;
private int size;
// calss the constructor and initializes the capacity
MinPriorityQueue(int c) {
this.capacity = c;
this.size = 0;
this.heap = new int[c + 1];
}
// inserts the key at the end and rearranges it
// so that the binary heap is in appropriate order
public void insert(int key) {
if (this.isFull())
return;
this.heap[this.size + 1] = key;
int k = this.size + 1;
while (k > 1) {
if (this.heap[k] < this.heap[k / 2]) {
int temp = this.heap[k];
this.heap[k] = this.heap[k / 2];
this.heap[k / 2] = temp;
}
k = k / 2;
}
this.size++;
}
// returns the highest priority value
public int peek() {
return this.heap[1];
}
// returns boolean value whether the heap is empty or not
public boolean isEmpty() {
if (0 == this.size)
return true;
return false;
}
// returns boolean value whether the heap is full or not
public boolean isFull() {
if (this.size == this.capacity)
return true;
return false;
}
// prints the heap
public void print() {
for (int i = 1; i <= this.capacity; i++)
System.out.print(this.heap[i] + " ");
System.out.println();
}
// heap sorting can be done by performing
// delete function to the number of times of the size of the heap
// it returns reverse sort because it is a min priority queue
public void heapSort() {
for (int i = 1; i < this.capacity; i++)
this.delete();
}
// this function reorders the heap after every delete function
private void sink() {
int k = 1;
while (2 * k <= this.size || 2 * k + 1 <= this.size) {
int minIndex;
if (this.heap[2 * k] >= this.heap[k]) {
if (2 * k + 1 <= this.size && this.heap[2 * k + 1] >= this.heap[k]) {
break;
} else if (2 * k + 1 > this.size) {
break;
}
}
if (2 * k + 1 > this.size) {
minIndex = this.heap[2 * k] < this.heap[k] ? 2 * k : k;
} else {
if (this.heap[k] > this.heap[2 * k] || this.heap[k] > this.heap[2 * k + 1]) {
minIndex = this.heap[2 * k] < this.heap[2 * k + 1] ? 2 * k : 2 * k + 1;
} else {
minIndex = k;
}
}
int temp = this.heap[k];
this.heap[k] = this.heap[minIndex];
this.heap[minIndex] = temp;
k = minIndex;
}
}
// deletes the highest priority value from the heap
public int delete() {
int min = this.heap[1];
this.heap[1] = this.heap[this.size];
this.heap[this.size] = min;
this.size--;
this.sink();
return min;
}
public static void main(String[] args) {
// testing
MinPriorityQueue q = new MinPriorityQueue(8);
q.insert(5);
q.insert(2);
q.insert(4);
q.insert(1);
q.insert(7);
q.insert(6);
q.insert(3);
q.insert(8);
q.print(); // [ 1, 2, 3, 5, 7, 6, 4, 8 ]
q.heapSort();
q.print(); // [ 8, 7, 6, 5, 4, 3, 2, 1 ]
}
}
