Priority Queues

A priority queue is a data structure that maintains a set of elements, each with an associated priority. Elements are ordered by their priority, with the highest priority element at the front.

Some key properties of priority queues:

Elements are removed from the queue in priority order; the element with the highest priority is removed first.
New elements can be inserted at any time. They are inserted in the proper position based on priority.
Common operations are:
- enqueue(element) - Inserts an element
- dequeue() - Removes and returns highest priority element
- peek() - Gets highest priority element without removing
- isEmpty() - Checks if queue is empty
- size() - Returns number of elements

Implementation

Priority queues are commonly implemented using:

Heaps - Provide O(log n) time for enqueue and dequeue operations. Easy to implement with arrays.
Binary search trees - Operations take O(log n) time. Provides flexibility for ordering.
Arrays - Simple implementation but operations take O(n) time.

Heaps are the most common because they provide fast querying and insertion.

#include <iostream>
using namespace std;

struct Node {
    int data;
    int priority;
    Node* next;
};

class PriorityQueue {
private:
    Node* head;

public:
    PriorityQueue() : head(nullptr) {}

    void push(int data, int priority) {
        Node* newNode = createNode(data, priority);

        if (head == nullptr) {
            head = newNode;
        }
        else if (priority < head->priority) {
            newNode->next = head;
            head = newNode;
        }
        else {
            Node* current = head;
            while (current->next && priority >= current->next->priority) {
                current = current->next;
            }
            newNode->next = current->next;
            current->next = newNode;
        }
    }

    int pop() {
        if (isEmpty()) {
            cout << "Priority Queue is empty!" << endl;
            return -1;
        }

        Node* temp = head;
        int data = temp->data;
        head = head->next;
        delete temp;

        return data;
    }

    int peek() {
        if (isEmpty()) {
            cout << "Priority Queue is empty!" << endl;
            return -1;
        }

        return head->data;
    }

    bool isEmpty() {
        return head == nullptr;
    }

private:
    Node* createNode(int data, int priority) {
        Node* newNode = new Node;
        newNode->data = data;
        newNode->priority = priority;
        newNode->next = nullptr;
        return newNode;
    }
};

int main() {
    PriorityQueue pq;

    pq.push(4, 1);
    pq.push(5, 2);
    pq.push(6, 3);
    pq.push(7, 0);

    while (!pq.isEmpty()) {
        cout << pq.peek() << " ";
        pq.pop();
    }

    return 0;
}

Applications

Priority queues are used for:

Scheduling - OS uses priority queues to schedule processes based on priority.
Algorithms - Dijkstra's algorithm uses a priority queue to find shortest path.
Data compression - Huffman coding uses priority queues to build optimal prefix code.

Priority queues provide an abstract data type that can order elements by importance. This makes them very versatile for solving problems involving priority!

Complexities Of All The Operations:

Methods	Time Complexity	Auxiliary Space
priority_queue::empty()	O(1)	O(1)
priority_queue::size()	O(1)	O(1)
priority_queue::top()	O(1)	O(1)
priority_queue::push()	O(logN)	O(1)
priority_queue::pop()	O(logN)	O(1)
priority_queue::swap()	O(1)	O(N)
priority_queue::emplace()	O(logN)	O(1)
priority_queue value_type	O(1)	O(1)

Min-max heap

wiki

A min-max heap is a variant of the binary heap data structure that efficiently supports both min and max operations. It combines properties of a min-heap and a max-heap.

Some key properties of min-max heaps:

Each node has a value, min, and max attribute. The value is the actual value of the node. Min and max track the minimum and maximum values in the subtree rooted at that node.
The root node's min attribute equals the minimum value in the entire heap. Its max attribute equals the maximum value.
When inserting or removing nodes, the min and max attributes must be updated along the path from the node to the root. This maintains the min/max invariant.