Last Updated on December 14, 2022 by Prepbytes
What is the priority queue?
Priority queues are abstract data structures where each element in the queue has a priority value. For example, in any airline, baggage under the “First-Class” or “Business” arrives before other baggage.
A priority Queue is a type of queue that follows the given below properties:
- An item with higher priority will be dequeued before the item with lower priority.
- If two elements present in the priority queue are having the same priority, then they will be served according to the order in which they are present in the queue.
The priority queue is widely used in many applications like job scheduling algorithms, CPU and Disk scheduling, and managing various resources shared between different processes, etc.
How is the Priority Value assigned in the Priority Queue?
Usually, an element’s value is considered for assigning the priority. For example, the element with bigger value will have a higher priority than the element with lower value.
We can also set priorities according to our demand.
The main difference between a queue and a priority queue:
- In the queue, the element inserted first will be dequeued first. But in the case of a priority queue, the element which is having highest priority will be dequeued first.
- When an element is popped out of the priority queue, the result will be in the sorted order, it can be either increasing or decreasing. While in queue elements are popped out in the order of FIFO (First in First out).
What is Binary Heap?
Binary heap is a complete tree i.e. All the levels of the tree are completely filled except the leaf nodes or last level and have all keys on the left. Due to this property, Binary heaps are suitable to be stored in an array.
A binary heap is either a min-heap or a max heap.
In the min-heap, the value at the root node is smaller than all the nodes present in the binary heap, and in the max heap, the value at the root node is greater than all the nodes present in the binary heap.
Implementation of Priority Queue
We can implement priority queues by using different data structures like an array, a linked list, a heap data structure, or a binary search tree. But Heap data structure provides an efficient implementation of priority queues.
Hence, we will use a heap data structure for implementing the priority queue in this article. We will use max-heap to implement the operations of the priority queue.
A time analysis of different implementations of priority queue is given below.
| Operations | peek | insert | delete |
|---|---|---|---|
| Linked List | O(1) | O(n) | O(1) |
| Binary Heap | O(1) | O(log n) | O(log n) |
| Binary Search Tree | O(1) | O(log n) | O(log n) |
Operations of Priority Queue:
-
Insert
It is done by the following steps:- Insert the new item at the end of the tree.
- Perform the Heapify function on the tree.
-
Delete
It is done by the following steps:- Select the item which is to be deleted from the tree.
- Swap the value with the last item from the tree.
- Remove the last item.
- Perform the Heapify function on the tree.
-
Peek
This operation will return the maximum item from the Heap without deleting the node.
#include <stdio.h>
int size = 0;
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
// Function to heapify the tree
void heapify(int array[], int size, int i) {
if (size == 1) {
printf("Single element in the heap");
} else {
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && array[l] > array[largest])
largest = l;
if (r < size && array[r] > array[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&array[i], &array[largest]);
heapify(array, size, largest);
}
}
}
// Function to insert an element into the tree
void insert(int array[], int newNum) {
if (size == 0) {
array[0] = newNum;
size += 1;
} else {
array[size] = newNum;
size += 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
}
}
// Function to delete an element from the tree
void deleteRoot(int array[], int num) {
int i;
for (i = 0; i < size; i++) {
if (num == array[i])
break;
}
swap(&array[i], &array[size - 1]);
size -= 1;
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(array, size, i);
}
}
// Print the array
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i)
printf("%d ", array[i]);
printf("\n");
}
// Driver code
int main() {
int array[10];
insert(array, 3);
insert(array, 4);
insert(array, 9);
insert(array, 5);
insert(array, 2);
printf("Max-Heap array: ");
printArray(array, size);
deleteRoot(array, 4);
printf("After deleting an element: ");
printArray(array, size);
}
// Priority Queue implementation in C++
#include <iostream>
#include <vector>
using namespace std;
// Function to swap position of two elements
void swap(int *a, int *b) {
int temp = *b;
*b = *a;
*a = temp;
}
// Function to heapify the tree
void heapify(vector<int> &hT, int i) {
int size = hT.size();
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT[l] > hT[largest])
largest = l;
if (r < size && hT[r] > hT[largest])
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
swap(&hT[i], &hT[largest]);
heapify(hT, largest);
}
}
// Function to insert an element into the tree
void insert(vector<int> &hT, int newNum) {
int size = hT.size();
if (size == 0) {
hT.push_back(newNum);
} else {
hT.push_back(newNum);
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}
}
}
// Function to delete an element from the tree
void deleteNode(vector<int> &hT, int num) {
int size = hT.size();
int i;
for (i = 0; i < size; i++) {
if (num == hT[i])
break;
}
swap(&hT[i], &hT[size - 1]);
hT.pop_back();
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}
}
// Print the tree
void printArray(vector<int> &hT) {
for (int i = 0; i < hT.size(); ++i)
cout << hT[i] << " ";
cout << "\n";
}
// Driver code
int main() {
vector<int> heapTree;
insert(heapTree, 3);
insert(heapTree, 4);
insert(heapTree, 9);
insert(heapTree, 5);
insert(heapTree, 2);
cout << "Max-Heap array: ";
printArray(heapTree);
deleteNode(heapTree, 4);
cout << "After deleting an element: ";
printArray(heapTree);
}
import java.util.ArrayList;
class Heap {
// Function to heapify the tree
void heapify(ArrayList<Integer> hT, int i) {
int size = hT.size();
// Find the largest among root, left child and right child
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < size && hT.get(l) > hT.get(largest))
largest = l;
if (r < size && hT.get(r) > hT.get(largest))
largest = r;
// Swap and continue heapifying if root is not largest
if (largest != i) {
int temp = hT.get(largest);
hT.set(largest, hT.get(i));
hT.set(i, temp);
heapify(hT, largest);
}
}
// Function to insert an element into the tree
void insert(ArrayList<Integer> hT, int newNum) {
int size = hT.size();
if (size == 0) {
hT.add(newNum);
} else {
hT.add(newNum);
for (int i = size / 2 - 1; i >= 0; i--) {
heapify(hT, i);
}
}
}
// Function to delete an element from the tree
void deleteNode(ArrayList<Integer> hT, int num) {
int size = hT.size();
int i;
for (i = 0; i < size; i++) {
if (num == hT.get(i))
break;
}
int temp = hT.get(i);
hT.set(i, hT.get(size - 1));
hT.set(size - 1, temp);
hT.remove(size - 1);
for (int j = size / 2 - 1; j >= 0; j--) {
heapify(hT, j);
}
}
// Print the tree
void printArray(ArrayList<Integer> array, int size) {
for (Integer i : array) {
System.out.print(i + " ");
}
System.out.println();
}
// Driver code
public static void main(String args[]) {
ArrayList<Integer> array = new ArrayList<Integer>();
int size = array.size();
Heap h = new Heap();
h.insert(array, 3);
h.insert(array, 4);
h.insert(array, 9);
h.insert(array, 5);
h.insert(array, 2);
System.out.println("Max-Heap array: ");
h.printArray(array, size);
h.deleteNode(array, 4);
System.out.println("After deleting an element: ");
h.printArray(array, size);
}
}
# Priority Queue implementation in Python
# Function to heapify the tree
def heapify(arr, n, i):
# Find the largest among root, left child and right child
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
# Swap and continue heapifying if root is not largest
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
# Function to insert an element into the tree
def insert(array, newNum):
size = len(array)
if size == 0:
array.append(newNum)
else:
array.append(newNum)
for i in range((size // 2) - 1, -1, -1):
heapify(array, size, i)
# Function to delete an element from the tree
def deleteNode(array, num):
size = len(array)
i = 0
for i in range(0, size):
if num == array[i]:
break
array[i], array[size - 1] = array[size - 1], array[i]
array.remove(size - 1)
for i in range((len(array) // 2) - 1, -1, -1):
heapify(array, len(array), i)
arr = []
insert(arr, 3)
insert(arr, 4)
insert(arr, 9)
insert(arr, 5)
insert(arr, 2)
print ("Max-Heap array: " + str(arr))
deleteNode(arr, 4)
print("After deleting an element: " + str(arr))
This article tried to discuss the concept of Priority Queue using Binary Heap. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes