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;
}
Copy

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!

• 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.

• findMin() - Returns the min attribute of the root node, which is the overall min of the heap. O(1) time.
• findMax() - Returns the max attribute of the root node, which is the overall max of the heap. O(1) time.
• insert(value) - Inserts a new value into the heap, updating min/max attributes along the path to root. O(log n) time.
• extractMin() - Removes and returns the node with the minimum value. Updates min/max attributes on path to root. O(log n) time.
• extractMax() - Removes and returns the node with the maximum value. Updates min/max attributes on path to root. O(log n) time.

Min-max heaps provide efficient access to both the minimum and maximum elements in a dataset. This is useful for applications like finding extreme values or implementing priority queues with dual priorities.

we can use 2 approaches the first one is to use pointers and make each node have left and right child node. the second approach which is better IMO is to use arrays, we can make an array length n and for the parent node in cell number n store each child node in the cells and

we cannot search it in a really good and efficient way like we did we binary search tree so in order to find a given number we have to look through the whole tree.

it is possible to do it in by sorting it but we can accomplish this in

import heapq

def build_min_heap(arr):
  n = len(arr)

  # Create the heap in bottom up manner
  for i in range(n//2, -1, -1):
    heapify(arr, n, i)

def heapify(arr, n, i):
  smallest = i 
  l = 2 * i + 1
  r = 2 * i + 2
  
  if l < n and arr[l] < arr[smallest]:
    smallest = l
  
  if r < n and arr[r] < arr[smallest]:
    smallest = r

  if smallest != i:
    arr[i], arr[smallest] = arr[smallest], arr[i]
    heapify(arr, n, smallest)

# Test the build heap function
nums = [5, 3, 8, 4, 1, 2]
build_min_heap(nums)
print(nums)
# [1, 2, 3, 4, 5, 8]
Copy

session 13