A Priority Queue is a data structure that allows you to insert elements with a priority, and retrieve the element with the highest priority.
You can implement a priority queue using either an array or a heap. Both array and heap-based implementations of priority queues have their own advantages and disadvantages. Arrays are generally easier to implement, but they can be slower because inserting and deleting elements requires shifting the elements in the array. Heaps are more efficient, but they can be more complex to implement. You can also refer to the Difference between Heaps and Sorted Array for a general comparison between the two.
Heap-based implementation of a priority queue
It involves creating a binary heap data structure and maintaining the heap property as elements are inserted and removed. In a binary heap, the element with the highest priority is always the root of the heap. To insert an element, you would add it to the end of the heap and then perform the necessary heap operations (such as swapping the element with its parent) to restore the heap property. To retrieve the highest priority element, you would simply return the root of the heap.
To implement a priority queue using a heap, we can use the following steps:
- Create a heap data structure (either a max heap or a min-heap)
- To insert an element into the priority queue, add the element to the heap using the heap’s insert function. The heap will automatically rearrange the elements to maintain the heap property.
- To remove the highest priority element (in a max heap) or the lowest priority element (in a min-heap), use the heap’s remove function. This will remove the root of the tree and rearrange the remaining elements to maintain the heap property.
Example 1:
C++
//Implement a priority queue in C++ using a heap#include <iostream>#include <vector>#include <string>class PriorityQueue {public: struct Node { std::string task; int priority; Node(std::string task, int priority) : task(task), priority(priority) {} }; std::vector<Node> heap; void insert(std::string task, int priority) { heap.push_back(Node(task, priority)); int idx = heap.size() - 1; while (idx != 0) { int parentIdx = (idx - 1) / 2; if (heap[parentIdx].priority < heap[idx].priority) { std::swap(heap[parentIdx], heap[idx]); idx = parentIdx; } else { break; } } } Node extractMax() { Node maxNode = heap[0]; heap[0] = heap.back(); heap.pop_back(); int idx = 0; while (idx < heap.size()) { int leftChildIdx = idx * 2 + 1; int rightChildIdx = idx * 2 + 2; int largerChildIdx = leftChildIdx; if (rightChildIdx < heap.size() && heap[rightChildIdx].priority > heap[leftChildIdx].priority) { largerChildIdx = rightChildIdx; } if (largerChildIdx < heap.size() && heap[largerChildIdx].priority > heap[idx].priority) { std::swap(heap[largerChildIdx], heap[idx]); idx = largerChildIdx; } else { break; } } return maxNode; }};int main() { PriorityQueue pq; pq.insert("Task 1", 1); pq.insert("Task 2", 2); pq.insert("Task 3", 3); pq.insert("Task 4", 4); while (!pq.heap.empty()) { PriorityQueue::Node max = pq.extractMax(); std::cout << max.task << std::endl; } return 0;}//Code is contributed by Kushal Pareek |
Java
import java.util.ArrayList;import java.util.List;class PriorityQueue {static class Node {String task;int priority;Node(String task, int priority) {this.task = task;this.priority = priority;}}List<Node> heap = new ArrayList<>();// Adds a task to the priority queuepublic void insert(String task, int priority) { heap.add(new Node(task, priority)); int idx = heap.size() - 1; while (idx != 0) { int parentIdx = (idx - 1) / 2; if (heap.get(parentIdx).priority < heap.get(idx).priority) { swap(parentIdx, idx); idx = parentIdx; } else { break; } }}// Extracts the task with the highest prioritypublic Node extractMax() { Node maxNode = heap.get(0); heap.set(0, heap.get(heap.size() - 1)); heap.remove(heap.size() - 1); int idx = 0; while (idx < heap.size()) { int leftChildIdx = idx * 2 + 1; int rightChildIdx = idx * 2 + 2; int largerChildIdx = leftChildIdx; if (rightChildIdx < heap.size() && heap.get(rightChildIdx).priority > heap.get(leftChildIdx).priority) { largerChildIdx = rightChildIdx; } if (largerChildIdx < heap.size() && heap.get(largerChildIdx).priority > heap.get(idx).priority) { swap(largerChildIdx, idx); idx = largerChildIdx; } else { break; } } return maxNode;}private void swap(int i, int j) { Node temp = heap.get(i); heap.set(i, heap.get(j)); heap.set(j, temp);}}public class Main {public static void main(String[] args) {PriorityQueue pq = new PriorityQueue();pq.insert("Task 1", 1);pq.insert("Task 2", 2);pq.insert("Task 3", 3);pq.insert("Task 4", 4); while (!pq.heap.isEmpty()) { PriorityQueue.Node max = pq.extractMax(); System.out.println(max.task); }}}// This code is contributed by Edula Vinay Kumar Reddy |
Python3
class MaxHeap: def __init__(self): self.heap = [] def insert(self, val): self.heap.append(val) self.heapify_up() def remove(self): if len(self.heap) == 0: return None if len(self.heap) == 1: return self.heap.pop() val = self.heap[0] self.heap[0] = self.heap.pop() self.heapify_down() return val def heapify_up(self): idx = len(self.heap) - 1 while idx > 0: parent_idx = (idx - 1) // 2 if self.heap[idx] > self.heap[parent_idx]: self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx] idx = parent_idx else: break def heapify_down(self): idx = 0 while idx * 2 + 1 < len(self.heap): left_child_idx = idx * 2 + 1 right_child_idx = idx * 2 + 2 if right_child_idx < len(self.heap) and self.heap[right_child_idx] > self.heap[left_child_idx]: largest_child_idx = right_child_idx else: largest_child_idx = left_child_idx if self.heap[idx] < self.heap[largest_child_idx]: self.heap[idx], self.heap[largest_child_idx] = self.heap[largest_child_idx], self.heap[idx] idx = largest_child_idx else: breakclass PriorityQueue: def __init__(self): self.heap = MaxHeap() def insert(self, val, priority): self.heap.insert((priority, val)) def remove(self): return self.heap.remove()[1]# Example usagepq = PriorityQueue()pq.insert('Task 1', 1)pq.insert('Task 2', 2)pq.insert('Task 3', 3)pq.insert('Task 4', 4)print(pq.remove()) # Output: Task 4print(pq.remove()) # Output: Task 3print(pq.remove()) # Output: Task 2print(pq.remove()) # Output: Task 1 |
Javascript
// JavaScript implementation:class MaxHeap { constructor() { this.heap = []; } insert(val) { this.heap.push(val); this.heapifyUp(); } remove() { if (this.heap.length === 0) { return null; } if (this.heap.length === 1) { return this.heap.pop(); } const val = this.heap[0]; this.heap[0] = this.heap.pop(); this.heapifyDown(); return val; } heapifyUp() { let idx = this.heap.length - 1; while (idx > 0) { const parentIdx = Math.floor((idx - 1) / 2); if (this.heap[idx] > this.heap[parentIdx]) { [this.heap[idx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[idx]]; idx = parentIdx; } else { break; } } } heapifyDown() { let idx = 0; while (idx * 2 + 1 < this.heap.length) { const leftChildIdx = idx * 2 + 1; const rightChildIdx = idx * 2 + 2; let largestChildIdx; if (rightChildIdx < this.heap.length && this.heap[rightChildIdx] > this.heap[leftChildIdx]) { largestChildIdx = rightChildIdx; } else { largestChildIdx = leftChildIdx; } if (this.heap[idx] < this.heap[largestChildIdx]) { [this.heap[idx], this.heap[largestChildIdx]] = [this.heap[largestChildIdx], this.heap[idx]]; idx = largestChildIdx; } else { break; } } }}class PriorityQueue { constructor() { this.heap = new MaxHeap(); } insert(val, priority) { this.heap.insert([priority, val]); } remove() { return this.heap.remove()[1]; }}// Example usageconst pq = new PriorityQueue();pq.insert("Task 1", 1);pq.insert("Task 2", 2);pq.insert("Task 3", 3);pq.insert("Task 4", 4);console.log(pq.remove() + "<br>"); // Output: Task 4console.log(pq.remove() + "<br>"); // Output: Task 3console.log(pq.remove() + "<br>"); // Output: Task 2console.log(pq.remove() + "<br>"); // Output: Task 1// This code is contributed by lokesh. |
C#
//Implement a priority queue in C# using a heapusing System;using System.Collections.Generic;public class MaxHeap{ private List<int> heap; public MaxHeap() { heap = new List<int>(); } public void Insert(int val) { heap.Add(val); HeapifyUp(); } public int? Remove() { if (heap.Count == 0) { return null; } if (heap.Count == 1) { int val = heap[0]; heap.RemoveAt(0); return val; } int result = heap[0]; heap[0] = heap[heap.Count - 1]; heap.RemoveAt(heap.Count - 1); HeapifyDown(); return result; } private void HeapifyUp() { int idx = heap.Count - 1; while (idx > 0) { int parentIdx = (idx - 1) / 2; if (heap[idx] > heap[parentIdx]) { int temp = heap[idx]; heap[idx] = heap[parentIdx]; heap[parentIdx] = temp; idx = parentIdx; } else { break; } } } private void HeapifyDown() { int idx = 0; while (idx * 2 + 1 < heap.Count) { int leftChildIdx = idx * 2 + 1; int rightChildIdx = idx * 2 + 2; int largestChildIdx; if (rightChildIdx < heap.Count && heap[rightChildIdx] > heap[leftChildIdx]) { largestChildIdx = rightChildIdx; } else { largestChildIdx = leftChildIdx; } if (heap[idx] < heap[largestChildIdx]) { int temp = heap[idx]; heap[idx] = heap[largestChildIdx]; heap[largestChildIdx] = temp; idx = largestChildIdx; } else { break; } } }}public class PriorityQueue{ private MaxHeap heap; public PriorityQueue() { heap = new MaxHeap(); } public void Insert(string val, int priority) { heap.Insert(priority); } public string Remove() { return heap.Remove().ToString(); }}public class Example{ public static void Main() { PriorityQueue pq = new PriorityQueue(); pq.Insert("Task 1", 1); pq.Insert("Task 2", 2); pq.Insert("Task 3", 3); pq.Insert("Task 4", 4); Console.WriteLine(pq.Remove()); // Output: Task 4 Console.WriteLine(pq.Remove()); // Output: Task 3 Console.WriteLine(pq.Remove()); // Output: Task 2 Console.WriteLine(pq.Remove()); // Output: Task 1 }}//This code is contributed by shivamsharma215 |
Output
Task 4 Task 3 Task 2 Task 1
In the above code, we have defined two classes: MaxHeap and PriorityQueue. The MaxHeap class is used to implement the actual heap data structure, while the PriorityQueue class wraps the MaxHeap class and adds the functionality of a priority queue.
The MaxHeap class has the following functions:
- __init__: Initializes the heap as an empty list
- insert: Inserts a value into the heap and calls the heapify_up function to maintain the heap property
- remove: Removes the root of the heap (the maximum value in a max heap) and calls the heapify_down function to maintain the heap property
- heapify_up: Starting from the bottom of the heap, compares each node to its parent and swaps them if necessary to maintain the heap property
- heapify_down: Starting from the root of the heap, compares each node to its children and swaps them if necessary to maintain the heap property.
The PriorityQueue class has the following functions:
- __init__: Initializes the priority queue with an empty MaxHeap
- insert: Inserts a value into the priority queue with a given priority. The priority is stored along with the value in a tuple, and the tuple is inserted into the MaxHeap
- remove: Removes the highest priority value from the priority queue by calling the remove function on the MaxHeap, and returns only the value (not the priority)
Array-based implementation of a priority queue:
It involves creating an array of elements and sorting it in ascending or descending order of priority. To insert an element, you would need to shift the elements in the array to make room for the new element and then insert it at the appropriate position based on its priority. To retrieve the highest priority element, you would simply return the first element in the array.
To implement a priority queue using arrays, we can use the following steps:
- Create an array to store the elements of the priority queue
- To insert an element into the priority queue, add the element to the end of the array
- To remove the highest priority element (in a max heap) or the lowest priority element (in a min heap),
perform the following steps: - Find the index of the highest or lowest priority element in the array
- Swap the element at that index with the element at the end of the array
- Remove the element at the end of the array
- Repeat steps 1-3 until the element at the desired index is in the correct position
C++
//C++ code implementation of priority queue using an array#include <iostream>#include <string>const int MAX_SIZE = 100;class PriorityQueue {private: struct Task { std::string name; int priority; }; Task queue[MAX_SIZE]; int size; public: PriorityQueue() { size = 0; } void insert(std::string name, int priority) { if (size == MAX_SIZE) { std::cout << "Error: Queue is full" << std::endl; return; } int i = size; while (i > 0 && priority < queue[i - 1].priority) { queue[i] = queue[i - 1]; i--; } queue[i].name = name; queue[i].priority = priority; size++; } std::string remove() { if (size == 0) { std::cout << "Error: Queue is empty" << std::endl; return ""; } std::string removedTask = queue[size - 1].name; size--; return removedTask; }};int main() { PriorityQueue pq; pq.insert("Task 1", 1); pq.insert("Task 2", 2); pq.insert("Task 3", 3); pq.insert("Task 4", 4); std::cout << pq.remove() << std::endl; // Task 1 std::cout << pq.remove() << std::endl; // Task 2 std::cout << pq.remove() << std::endl; // Task 3 std::cout << pq.remove() << std::endl; // Task 4 return 0;}//This code is contributed by Kushal Pareek |
Java
import java.util.ArrayList;class PriorityQueue { // Declare an ArrayList to store our elements ArrayList<Pair> queue; // Initialize our priority queue public PriorityQueue() { this.queue = new ArrayList<Pair>(); } // Insert an element into the queue with a given priority public void insert(String val, int priority) { // Create a new pair object to store our element and its priority Pair pair = new Pair(val, priority); // Add the pair to the queue this.queue.add(pair); } // Remove the element with the highest priority from the queue public String remove() { int maxIdx = 0; // Iterate through the queue to find the element with the highest priority for (int i = 1; i < this.queue.size(); i++) { if (this.queue.get(i).priority > this.queue.get(maxIdx).priority) { maxIdx = i; } } String val = this.queue.get(maxIdx).val; // Shift all elements after the removed element to the left while (maxIdx < this.queue.size() - 1) { this.queue.set(maxIdx, this.queue.get(maxIdx + 1)); maxIdx++; } this.queue.remove(this.queue.size() - 1); return val; } // Inner class to store an element and its priority private class Pair { String val; int priority; public Pair(String val, int priority) { this.val = val; this.priority = priority; } } public static void main(String[] args) { PriorityQueue pq = new PriorityQueue(); pq.insert("Task 1", 1); pq.insert("Task 2", 2); pq.insert("Task 3", 3); pq.insert("Task 4", 4); System.out.println(pq.remove()); // Output: Task 4 System.out.println(pq.remove()); // Output: Task 3 System.out.println(pq.remove()); // Output: Task 2 System.out.println(pq.remove()); // Output: Task 1 }}// This code is contributed by Vikram_Shirsat |
Python3
class PriorityQueue: def __init__(self): self.queue = [] def insert(self, val, priority): self.queue.append((priority, val)) def remove(self): max_idx = 0 for i in range(1, len(self.queue)): if self.queue[i][0] > self.queue[max_idx][0]: max_idx = i val = self.queue[max_idx][1] while max_idx < len(self.queue) - 1: self.queue[max_idx] = self.queue[max_idx + 1] max_idx += 1 self.queue.pop() return val# Example usagepq = PriorityQueue()pq.insert('Task 1', 1)pq.insert('Task 2', 2)pq.insert('Task 3', 3)pq.insert('Task 4', 4)print(pq.remove()) # Output: Task 4print(pq.remove()) # Output: Task 3print(pq.remove()) # Output: Task 2print(pq.remove()) # Output: Task 1 |
C#
//C# code implementation of priority queue using an arrayusing System;using System.Collections.Generic;class PriorityQueue{// Declare a List to store our elementsprivate List<Pair> queue; // Initialize our priority queuepublic PriorityQueue(){ this.queue = new List<Pair>();}// Insert an element into the queue with a given prioritypublic void insert(string val, int priority){ // Create a new pair object to store our element and its priority Pair pair = new Pair(val, priority); // Add the pair to the queue this.queue.Add(pair);}// Remove the element with the highest priority from the queuepublic string remove(){ int maxIdx = 0; // Iterate through the queue to find the element with the highest priority for (int i = 1; i < this.queue.Count; i++) { if (this.queue[i].priority > this.queue[maxIdx].priority) { maxIdx = i; } } string val = this.queue[maxIdx].val; // Shift all elements after the removed element to the left while (maxIdx < this.queue.Count - 1) { this.queue[maxIdx] = this.queue[maxIdx + 1]; maxIdx++; } this.queue.RemoveAt(this.queue.Count - 1); return val;}// Inner class to store an element and its priorityprivate class Pair{ public string val; public int priority; public Pair(string val, int priority) { this.val = val; this.priority = priority; }}static void Main(string[] args){ PriorityQueue pq = new PriorityQueue(); pq.insert("Task 1", 1); pq.insert("Task 2", 2); pq.insert("Task 3", 3); pq.insert("Task 4", 4); Console.WriteLine(pq.remove()); // Output: Task 4 Console.WriteLine(pq.remove()); // Output: Task 3 Console.WriteLine(pq.remove()); // Output: Task 2 Console.WriteLine(pq.remove()); // Output: Task 1}}//This code is contributed by shivamsharma215 |
Javascript
//javascript equivalent of above code class PriorityQueue { constructor() { // Declare an ArrayList to store our elements this.queue = []; } // Insert an element into the queue with a given priority insert(val, priority) { // Create a new pair object to store our element and its priority const pair = new Pair(val, priority); // Add the pair to the queue this.queue.push(pair); } // Remove the element with the highest priority from the queue remove() { let maxIdx = 0; // Iterate through the queue to find the element with the highest priority for (let i = 1; i < this.queue.length; i++) { if (this.queue[i].priority > this.queue[maxIdx].priority) { maxIdx = i; } } const val = this.queue[maxIdx].val; // Shift all elements after the removed element to the left while (maxIdx < this.queue.length - 1) { this.queue[maxIdx] = this.queue[maxIdx + 1]; maxIdx++; } this.queue.pop(); return val; }}// Inner class to store an element and its priorityclass Pair { constructor(val, priority) { this.val = val; this.priority = priority; }}const pq = new PriorityQueue();pq.insert("Task 1", 1);pq.insert("Task 2", 2);pq.insert("Task 3", 3);pq.insert("Task 4", 4);console.log(pq.remove()); // Output: Task 4console.log(pq.remove()); // Output: Task 3console.log(pq.remove()); // Output: Task 2console.log(pq.remove()); // Output: Task 1 |
Output
Task 4 Task 3 Task 2 Task 1
In the above code, we have defined a class called PriorityQueue which implements a priority queue using an array. The PriorityQueue class has the following functions:
- __init__: Initializes the priority queue with an empty array
- insert: Inserts a value into the priority queue with a given priority. The priority is stored along with the value in a tuple, and the tuple is added to the end of the array
- remove: Removes the highest priority value from the priority queue by finding the index of the highest priority element in the array and swapping it with the element at the end of the array until it is in the correct position. Then, the element at the end of the array is removed and the value is returned.
Which is more efficient – Heap or Array, to implement Priority Queue?
| Data structure | Insert | Search | Find min | Delete min |
|---|---|---|---|---|
| Sorted array | O(n) | O(log n) | O(1) | O(n) |
| Min heap | O(log n) | O(n) | O(1) | O(log n) |
Both arrays and heaps can be used to implement priority queues, but heaps are generally more efficient because they offer faster insertion and retrieval times. The choice of data structure will depend on the specific requirements of your application. It is important to consider the trade-offs between the ease of implementation and the performance of the data structure when deciding which one to use.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
