Priority Queue Data Structure with Practical Examples

• Priority Queue
  • Min Priority Queue
  • Max Priority Queue
• Heap
  • Max Heap
  • Min Heap
• Priority Queue Implementation Using Max Heap in C
  • maxHeapify()
  • insertNode()
  • deleteNode()
• Priority Queue in C++ STL
  • Functions in C++ STL Priority Queue
• Applications of Priority Queue
• Run C Programming Online Compiler

Often, there is a need to store and access data while considering their assigned priorities. However, traditional data structures may require costly rearrangements when new elements are added or deleted, impacting performance. Priority Queues offer a solution by efficiently arranging data according to their individual priorities, allowing access with low complexity.

¶Priority Queue

In a priority queue, each element comes with a priority value when it’s added. We can only access one element at a time, and it’s always the one with the highest priority. The queue arranges elements so that those with higher priorities are at the front, and lower-priority ones are at the back.With re-balancing it ensures that elements are stored in a manner that maintains this order, allowing for efficient retrieval based on priority.

Priority queues can be implemented using arrays, linked lists, heaps, or binary search trees. Each method has its pros and cons, suited for different needs and performance considerations. Based on how the priority queue arranges its elements with respect to priority, it can be classified into two types:

¶Min Priority Queue

In a min priority queue, elements with lower priority values are given higher priority. Therefore, the element with the minimum priority value is always at the front of the queue. This type of priority queue is often used when you need to retrieve the element with the lowest priority first.

¶Max Priority Queue

In a max priority queue, elements with higher priority values are given higher priority. Consequently, the element with the maximum priority value is placed at the front of the queue. Max priority queues are useful when you need to access the element with the highest priority first.

¶Heap

A heap is a complete binary tree, meaning except possibly for the last level all levels of the tree are fully filled, which is filled from left to right. Heaps find extensive applications in algorithms such as sorting, graph algorithms, and priority queue implementations due to their efficient operations. Depending on whether it is a max heap or min heap, each node must satisfy the heap property.

¶Max Heap

In a max heap, the value of every parent node must be greater than or equal to the value of both its children. This means the largest value always sits at the root, making it easy to retrieve the “maximum” element efficiently.

¶Min Heap

Conversely, in a min heap, the value of every parent node must be less than or equal to the value of both its children. This ensures the smallest value resides at the root, facilitating the retrieval of the “minimum” element quickly.

¶Priority Queue Implementation Using Max Heap in C

#include <stdio.h>

#define MAX_SIZE 100

// Function to swap two elements in the array
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify a subtree rooted at index 'rootIndex' in max heap
void maxHeapify(int arr[], int size, int rootIndex) {
    int largest = rootIndex; // Initialize largest as root
    int leftChild = 2 * rootIndex; // left = 2*i
    int rightChild = 2 * rootIndex + 1; // right = 2*i + 1

    // If left child is larger than root
    if (leftChild <= size && arr[leftChild] > arr[largest])
        largest = leftChild;

    // If right child is larger than largest so far
    if (rightChild <= size && arr[rightChild] > arr[largest])
        largest = rightChild;

    // If largest is not root
    if (largest != rootIndex) {
        swap(&arr[rootIndex], &arr[largest]);
        // Recursively heapify the affected sub-tree
        maxHeapify(arr, size, largest);
    }
}

// Function to insertNode an element into the priority queue
void insertNode(int arr[], int *size, int value) {
    if (*size == MAX_SIZE) {
        printf("Queue is full. Cannot insertNode element.\n");
        return;
    }

    // InsertNode the new element at the end of the heap
    *size += 1;
    arr[*size] = value;

    // Heapify the tree from bottom to top
    int currentIndex = *size;
    while (currentIndex > 1 && arr[currentIndex / 2] < arr[currentIndex]) {
        swap(&arr[currentIndex], &arr[currentIndex / 2]);
        currentIndex = currentIndex / 2;
    }
}

// Function to extract the maximum element from the priority queue
int extractMax(int arr[], int *size) {
    if (*size <= 0) {
        printf("Queue is empty. Cannot extract element.\n");
        return -1;
    }

    // Store the root value which is the maximum element
    int maxElement = arr[1];

    // Replace the root with the last element
    arr[1] = arr[*size];
    *size -= 1;

    // Heapify the new root
    maxHeapify(arr, *size, 1);

    return maxElement;
}

// Function to delete an element at a given index from the priority queue
void deleteNode(int arr[], int *size, int index) {
    if (index <= 0 || index > *size) {
        printf("Invalid index. Cannot delete element.\n");
        return;
    }

    // Replace the element at the given index with the last element
    arr[index] = arr[*size];
    *size -= 1;

    // Heapify the tree from bottom to top
    while (index > 1 && arr[index / 2] < arr[index]) {
        swap(&arr[index], &arr[index / 2]);
        index = index / 2;
    }

    // Heapify the subtree rooted at the index
    maxHeapify(arr, *size, index);
}

int main() {

    int priorityQueue[MAX_SIZE] = {0};
    int size = 0;

    // InsertNode elements into the priority queue

    insertNode(priorityQueue, &size, 55);
    insertNode(priorityQueue, &size, 35);
    insertNode(priorityQueue, &size, 65);
    insertNode(priorityQueue, &size, 90);
    insertNode(priorityQueue, &size, 50);
    insertNode(priorityQueue, &size, 65);

    // Extract and print the maximum element
    printf("Maximum element in the priority queue: %d\n", extractMax(priorityQueue, &size));

    // Delete an element at index 2
    deleteNode(priorityQueue, &size, 2);

    // Extract and print the maximum element after deletion
    printf("Maximum element in the priority queue after deletion: %d\n", extractMax(priorityQueue, &size));

    insertNode(priorityQueue, &size, 80);

     // Extract and print the maximum element after deletion
    printf("Maximum element in the priority queue: %d\n", extractMax(priorityQueue, &size));
    
    // Delete an element at index 2
    deleteNode(priorityQueue, &size, 2);

    // Extract and print the maximum element after deletion
    printf("Maximum element in the priority queue after deletion: %d\n", extractMax(priorityQueue, &size));

    return 0;
}

¶maxHeapify()

The maxHeapify function is responsible for maintaining the heap property in a max heap, specifically at a given root index. It ensures that the subtree rooted at the specified index follows the max heap property, where each node is greater than or equal to its children. It identifies the largest element among the root and its children. If the largest element is not the root itself, it swaps the root with the largest child.This ensures that the largest element is moved up to the root position, maintaining the max heap property locally.
The time complexity of maxHeapify is O(log n), where n is the number of elements in the subtree rooted at the specified index. This is because the function descends down the tree height, which is logarithmic with respect to the number of elements in the subtree.

¶insertNode()

The insertNode function adds a new element to the max heap, ensuring that the heap property is maintained. It inserts the element at the end of the heap and then adjusts the heap upwards if needed. This ensures that each parent node is greater than or equal to its children. It adjusts the heap upwards by comparing the new element with its parent and swapping if necessary. This process repeats recursively until the heap property is satisfied.
The time complexity of insertNode is O(log n), where n is the number of elements in the heap. This is due to the upward heapification process, which involves traversing the height of the heap. Since the height of a binary heap is logarithmic, insertion takes logarithmic time.

¶deleteNode()

The deleteNode function removes an element from the max heap while maintaining the heap property. It replaces the element to be deleted with the last element in the heap and adjusts the heap structure upwards, if necessary, to ensure that the max heap property is preserved.
The time complexity of deleteNode() is O(log n), where n is the number of elements in the heap. Since the height of a binary heap is logarithmic, deletion takes logarithmic time.

¶Priority Queue in C++ STL

In C++, the Standard Template Library provides a priority queue implementation as part of the <queue> header. The priority queue STL uses a max-heap by default, meaning that the maximum element is always at the top. To use priority queue as min-heap, we can use,

std::priority_queue<int, std::vector<int>, std::greater<int>>

¶Functions in C++ STL Priority Queue

#include <iostream>
#include <queue>

int main() {
    // Creating a priority queue of integers
    std::priority_queue<int> pq;

    // Inserting elements into the priority queue
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // Accessing the top (maximum) element of the priority queue
    std::cout << "Top element: " << pq.top() << std::endl;

    // Removing the top element from the priority queue
    pq.pop();

    // Accessing the top element after removal
    std::cout << "Top element after pop: " << pq.top() << std::endl;

    // Checking if the priority queue is empty
    std::cout << "Priority queue is empty: " << (pq.empty() ? "true" : "false") << std::endl;

    // Getting the size of the priority queue
    std::cout << "Size of priority queue: " << pq.size() << std::endl;

    return 0;
}

• push() Inserts an element into the priority queue. Time Complexity O(log n), where n is the number of elements in the priority queue.

• top() Returns the current maximum (top) element in the priority queue. Time Complexity O(1).

• pop() Removes the current maximum (top) element from the priority queue. Time Complexity O(log n), where n is the number of elements in the priority queue.

• empty() Checks if the priority queue is empty. Time Complexity O(1).

• size() Returns the current number of elements in the priority queue. Time Complexity O(1).

¶Applications of Priority Queue

Priority queues have various applications in computer science and real-world scenarios due to their ability to efficiently manage elements based on their priority.

• Job Scheduling: Priority queues are used in job scheduling algorithms, where tasks or jobs are assigned priorities based on their urgency or importance. Jobs with higher priority are executed before those with lower priority.

• Dijkstra’s Shortest Path Algorithm: Priority queues are used in Dijkstra’s algorithm to find the shortest paths between nodes in a graph. Nodes are processed based on their distance from the source node, with shorter paths given higher priority.

• Huffman Coding: Priority queues are utilized in Huffman coding, a data compression algorithm. The algorithm constructs a binary tree of characters based on their frequencies, with characters having lower frequencies assigned higher priority in the priority queue.

• Event-driven Simulation: Priority queues are employed in event-driven simulation systems to manage events based on their occurrence time. Events are scheduled and processed in chronological order, with events occurring earlier given higher priority.

• Operating System Tasks: Priority queues are used in operating systems to manage tasks and processes based on their priority levels. Higher-priority processes are executed before lower-priority ones, allowing the system to respond promptly to critical tasks.

• Network Routing: Priority queues are utilized in network routing protocols to prioritize packets based on their importance or type of service. Packets with higher priority are forwarded with minimal delay, ensuring timely delivery of critical data.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.