Priority Queue Introduction!

A priority queue is a type of data structure in which each element has a priority associated with it and is served according to its priority. If elements with the same priority are enqueued, they are served according to their order in the queue. Priority queues are commonly implemented as binary heaps, but can also be implemented as a sorted linked list or as a self-balancing binary search tree. They are used in a wide variety of applications, such as scheduling and graph algorithms.

How Priority Queue Works?

A priority queue works by assigning a priority to each element that is added to the queue. When an element is dequeued, the element with the highest priority is removed first. In case of multiple elements having the same highest priority, they are served in the order they were added to the queue.

There are different ways to implement a priority queue, but one common method is to use a binary heap. A binary heap is a complete binary tree (meaning all levels of the tree are fully filled except possibly the last level) that satisfies the heap property, which is that the value of each parent node is greater than or equal to the values of its children for a max-heap and smaller for a min-heap. This property allows for efficient insertion and removal of elements, with the time complexity of O(log n) for both operations.

Another common way of implementing priority queue is using a sorted linked list, where each element has a priority and a pointer to the next element. When an element is added to the queue, it is inserted at the appropriate position in the list so that the list remains sorted by priority. The time complexity of insertion and removal operations is O(n)

You can also use Self-balancing binary search tree to implement priority queue, the complexity of insertion and deletion is log(n)

The performance of the priority queue can vary depending on the implementation and the specific use case.

Example of Priority Queue

C++

Python

Java

Here's an example of a custom priority queue class implemented in C++. This example uses a min-priority queue and a binary heap to store the elements

#include <iostream>
#include <vector>

class PriorityQueue {
private:
	std::vector<int> heap;
	int parent(int i) { return (i - 1) / 2; }
	int left(int i) { return (2 * i) + 1; }
	int right(int i) { return (2 * i) + 2; }
	void heapify_up(int i);
	void heapify_down(int i);

public:
	PriorityQueue() {}
	void push(int x);
	int top();
	void pop();
	bool empty();
};

void PriorityQueue::heapify_up(int i) {
	while (i > 0 && heap[parent(i)] > heap[i]) {
		std::swap(heap[parent(i)], heap[i]);
		i = parent(i);
	}
}

void PriorityQueue::heapify_down(int i) {
	int minIndex = i;
	int leftIndex = left(i);
	int rightIndex = right(i);
	if (leftIndex < heap.size() && heap[leftIndex] < heap[minIndex])
		minIndex = leftIndex;
	if (rightIndex < heap.size() && heap[rightIndex] < heap[minIndex])
		minIndex = rightIndex;
	if (i != minIndex) {
		std::swap(heap[i], heap[minIndex]);
		heapify_down(minIndex);
	}
}

void PriorityQueue::push(int x) {
	heap.push_back(x);
	heapify_up(heap.size() - 1);
}

int PriorityQueue::top() {
	if (heap.empty()) {
		throw std::out_of_range("The priority queue is empty");
	}
	return heap[0];
}

void PriorityQueue::pop() {
	if (heap.empty()) {
		throw std::out_of_range("The priority queue is empty");
	}
	heap[0] = heap.back();
	heap.pop_back();
	heapify_down(0);
}

bool PriorityQueue::empty() {
	return heap.empty();
}

int main() {
	PriorityQueue pq;
	pq.push(3);
	pq.push(1);
	pq.push(2);
	while (!pq.empty()) {
		std::cout << pq.top() << std::endl;
		pq.pop();
	}
	return 0;
}

The above example creates a PriorityQueue class which has basic functionalities like push(), pop(), top() and empty(). The class uses a vector to store the elements, and the heapify_up() and heapify_down() methods are used to maintain the heap property. The push() function adds an element to the priority queue and calls the heapify_up() function to ensure the heap property

Types of Priority Queue

There are two main types of priority queues: max-priority queues and min-priority queues.

A max-priority queue is a priority queue in which the element with the highest priority is at the front of the queue. For example, in a max-priority queue used for scheduling, a task with the highest priority would be at the front of the queue and would be executed first.

A min-priority queue is a priority queue in which the element with the lowest priority is at the front of the queue. For example, in a min-priority queue used for finding the shortest path in a graph, the vertex with the smallest distance from the starting vertex would be at the front of the queue.

There are other variations of priority queues too like Double Ended Priority Queue (depends on use case and implementation), where elements can be removed from both ends.

A priority queue can also be implemented as a stable priority queue, which preserves the order of elements with the same priority. This means that if two elements with the same priority are enqueued, the one that was enqueued first will be dequeued first.

Applications of Priority Queue

Priority queues are used in a wide variety of applications, such as:

Scheduling: In computer systems, tasks are often scheduled based on their priority. A priority queue can be used to keep track of the tasks and their priorities, with the highest priority task at the front of the queue.
Graph algorithms: Many graph algorithms, such as Dijkstra's shortest path algorithm and the A* algorithm for pathfinding, use a priority queue to keep track of the vertices that still need to be visited and the current distance from the starting vertex.
Huffman coding: Huffman coding is a technique for compressing data that uses a priority queue to build a binary tree of the characters in the data and their frequencies.
Medical treatment: In hospitals, patients with critical conditions are often given priority over others. A priority queue can be used to manage the order in which patients are treated.
Network Routing: Priority queue can be used in network routing to assign priority to certain data packets to ensure that they are delivered in a timely manner.
Operating systems: Operating systems use priority queue to schedule the execution of processes and allocate resources.
Game AI: In games, priority queue can be used to schedule the AI actions of the NPCs (non-player characters) based on their priority.

These are just a few examples, but priority queues are a versatile data structure that can be used in many different types of algorithms and applications.

Time and Space Complexity of Priority Queue

The time and space complexity of a priority queue depends on the specific implementation.

In a binary heap-based priority queue, the time complexity of the insert and remove operations is O(log n), where n is the number of elements in the heap. This is because these operations involve adjusting the position of elements in the heap to maintain the heap property, which is a logarithmic operation. The space complexity of a binary heap-based priority queue is O(n)

In a sorted linked list-based priority queue, the time complexity of the insert operation is O(n) because it requires traversing the list to find the appropriate position for the new element, and the time complexity of the remove operation is also O(n) because it requires traversing the list to find the element with the highest priority. The space complexity is O(n)

In a self-balancing binary search tree-based priority queue, the time complexity of the insert and remove operations is O(log n) where n is the number of elements in the tree. This is because these operations involve adjusting the position of elements in the tree to maintain the balance property, which is a logarithmic operation. The space complexity is O(n)

Overall, the priority queue that uses binary heap has the most efficient performance in terms of both time and space complexity.

Advantages and Disadvantages of Priority Queue

Advantages of priority queue:

Efficiently implements the priority-based sorting algorithm.
Can be used to efficiently implement other data structures such as a stack or a queue.
Can be used to solve various computational problems such as Dijkstra's shortest path algorithm, Huffman coding, etc.
It allows the elements to be inserted or deleted in O(log n) time complexity.

Disadvantages of priority queue:

It requires extra memory to store the priority of each element.
It does not perform well with a large number of elements.
It can be difficult to implement a stable priority queue, in which elements with the same priority are served in the order they were added.
Priority queues are not well-suited for scenarios where the priority of elements changes frequently.

Priority Queue can be implemented using different data structure such as array, linked list and heap. Each implementation has different advantages and disadvantages. For example, using an array to implement a priority queue results in poor performance when elements are frequently removed from the middle of the queue. Heaps are more efficient in this case, but they require more memory than an array.

It's important to choose the right data structure based on the specific use case and requirements.