Priority Queues | DSA in C++ - Software Development PDF Download

Introduction

Priority queues are an essential data structure in computer science that allow us to efficiently manage elements based on their priorities. In this article, we will explore the concept of priority queues in C++ and understand their implementation using the Standard Template Library (STL). We will cover the basics, provide multiple examples, and explain their applications through code snippets and sample problems.

What is a Priority Queue?

A priority queue is a data structure that allows efficient insertion and removal of elements based on their priority. Elements with higher priority are dequeued first. It follows the First-In-First-Out (FIFO) principle within each priority level.

Implementation of Priority Queues in C++ STL

C++ provides a priority_queue class in the <queue> header, which implements a priority queue using a max-heap by default. Elements in the priority queue are sorted based on their values.

Basic Operations on Priority Queues

The key operations supported by a priority queue are:

• Insertion: Adding an element to the priority queue.
• Deletion: Removing the highest priority element from the queue.
• Peek: Accessing the highest priority element without removing it.

Examples and Code Snippets

Example 1: Creating a Priority Queue

#include <queue>

int main() {

    std::priority_queue<int> pq; // Creates an empty priority queue of integers    

    return 0;

}

Example 2: Inserting Elements into a Priority Queue

#include <iostream>

#include <queue>

int main() {

    std::priority_queue<int> pq;

    pq.push(10); // Inserts 10 into the priority queue

    pq.push(20); // Inserts 20 into the priority queue

    pq.push(5);  // Inserts 5 into the priority queue

    return 0;

}

Example 3: Removing the Highest Priority Element

#include <iostream>

#include <queue>

int main() {

    std::priority_queue<int> pq;

    pq.push(10); // Inserts 10 into the priority queue

    pq.push(20); // Inserts 20 into the priority queue

    pq.push(5);  // Inserts 5 into the priority queue

    return 0;

}

Sample Problems

Problem 1: Find the kth smallest element in an array.

#include <iostream>

#include <queue>

int kthSmallest(int arr[], int n, int k) {

    std::priority_queue<int> pq;

    for (int i = 0; i < n; i++) {

        pq.push(arr[i]);

        if (pq.size() > k)

            pq.pop();

    }

    return pq.top();

}

int main() {

    int arr[] = {7, 10, 4, 3, 20, 15};

    int k = 3;

    int kthSmallestElement = kthSmallest(arr, sizeof(arr) / sizeof(arr[0]), k);

    std::cout << "The kth smallest element is: " << kthSmallestElement << std::endl;

    return 0;

}

Problem 2: Merge K sorted arrays into a single sorted array.

#include <iostream>

#include <queue>

#include <vector>

struct Element {

    int value;

    int arrayIndex;

    int elementIndex;

    Element(int v, int ai, int ei) : value(v), arrayIndex(ai), elementIndex(ei) {}

};

struct Compare {

    bool operator()(const Element& e1, const Element& e2) {

        return e1.value > e2.value;

    }

};

std::vector<int> mergeKArrays(const std::vector<std::vector<int>>& arrays) {

    std::priority_queue<Element, std::vector<Element>, Compare> pq;

    std::vector<int> result;

    for (int i = 0; i < arrays.size(); i++) {

        if (!arrays[i].empty())

            pq.push(Element(arrays[i][0], i, 0));

    }

    while (!pq.empty()) {

        Element current = pq.top();

        pq.pop();

        result.push_back(current.value);

        if (current.elementIndex + 1 < arrays[current.arrayIndex].size()) {

            pq.push(Element(arrays[current.arrayIndex][current.elementIndex + 1],

                            current.arrayIndex, current.elementIndex + 1));

        }

    }

    return result;

}

int main() {

    std::vector<std::vector<int>> arrays = {{1, 4, 7},

                                            {2, 5, 8},

                                            {3, 6, 9}};

    std::vector<int> mergedArray = mergeKArrays(arrays);

    std::cout << "Merged sorted array: ";

    for (int num : mergedArray) {

        std::cout << num << " ";

    }

    std::cout << std::endl;

    return 0;

}

Conclusion

In this article, we explored the concept of priority queues in C++ and learned how to implement them using the STL. We covered the basic operations of priority queues, provided examples with code snippets, and discussed their applications through sample problems. With this knowledge, you can leverage priority queues to efficiently manage elements based on their priorities in your C++ programs.