Priority Queue using heap

 

📚 What is a Priority Queue?

A Priority Queue is a special type of queue where:

• Each element has a priority associated with it.

• Elements with higher priority are served before elements with lower priority.

• If two elements have the same priority, they are served according to their order in the queue (like normal queue behavior).

🔵 Important: It is not simply First-In-First-Out (FIFO) like a normal queue — instead, priority decides the order.

---

🎯 Example

Element	Priority
A	2
B	4
C	1

If you insert A, B, and C into a priority queue:

• B will be removed first (priority 4),

• then A (priority 2),

• then C (priority 1).

---

🔥 Real Life Examples

• Operating systems scheduling processes (higher priority processes get CPU first)

• Emergency rooms (patients with severe conditions are treated first)

• Dijkstra’s algorithm for shortest path (priority by smallest distance)

---

🛠️ How to Implement Priority Queue?

There are different ways to implement a Priority Queue:

Method	Insert Time	Delete Time	Remarks
Unsorted Array/List	O(1)	O(n)	Fast insert, slow delete
Sorted Array/List	O(n)	O(1)	Slow insert, fast delete
Binary Heap (Best!)	O(log n)	O(log n)	Balanced insert and delete

✅ In most cases, Binary Heap is used for efficient performance.

📚 Priority Queue using Binary Heap — Algorithms

---

1. Insert Operation (Heapify Up)

Insert(heap, element, priority):
    1. Increase heap size by 1.
    2. Place the new element at the end of the heap.
    3. While the new element's priority > parent's priority:
          a. Swap the element with its parent.
          b. Move up to the parent's position.
    4. Stop when heap property is satisfied or root is reached.

---

2. Find (Peek Highest Priority Element)

FindMax(heap):
    1. Return the root element (heap[0]).

---

3. Delete Operation (Heapify Down)

DeleteMax(heap):
    1. Replace root element with the last element in the heap.
    2. Decrease heap size by 1.
    3. Heapify Down:
          a. Compare current node with its left and right children.
          b. If one of the children has a higher priority:
              - Swap current node with the child having higher priority.
          c. Repeat the process until heap property is restored.

---

🔥 Helper Functions

Heapify Up (for Insert)

HeapifyUp(heap, index):
    while index > 0 and heap[index].priority > heap[parent(index)].priority:
        swap(heap[index], heap[parent(index)])
        index = parent(index)

(parent(index) = (index - 1) / 2)

Example: Insert 50 into a Max-Heap

Initial Max-Heap (array):

[40, 30, 15, 10, 20]

Tree form:

        40
       /  \
     30    15
    /  \
   10   20

---

Step 1: Insert new element 50 at the end

Array = [40, 30, 15, 10, 20, 50]

Tree form:

        40
       /  \
     30    15
    /  \     \
   10   20    50

---

Step 2: Heapify Up (compare 50 with parent 15)

• 50 > 15 → swap

Array = [40, 30, 50, 10, 20, 15]

Tree:

        40
       /  \
     30    50
    /  \     \
   10   20    15

---

Step 3: Continue Heapify Up (compare 50 with parent 40)

• 50 > 40 → swap

Array = [50, 30, 40, 10, 20, 15]

Tree:

        50
       /  \
     30    40
    /  \     \
   10   20    15

---

✅ Final Max-Heap:

Array = [50, 30, 40, 10, 20, 15]

Tree:

        50
       /  \
     30    40
    /  \     \
   10   20    15

---

👉 This clearly shows Heapify Up (Bubble Up): the inserted element (50) keeps moving upward until the heap property is restored.

---

Heapify Down (for Delete)

HeapifyDown(heap, index):
    while index has at least one child:
        1. Find the child with the highest priority.
        2. If heap[index].priority < child’s priority:
              swap(heap[index], child)
              index = child's index
        3. Else, break

(left child = 2 × index + 1, right child = 2 × index + 2)

Example: Heapify Down after Deleting Root

Initial Max-Heap:

        50
       /  \
     30    40
    /  \
   10   20

Array representation: [50, 30, 40, 10, 20]

---

Step 1: Delete root (50)

• Replace root with last element (20)

• Heap = [20, 30, 40, 10]

        20
       /  \
     30    40
    /
   10

---

Step 2: Heapify Down from root (20)

• Compare 20 with children (30, 40)

• Largest child = 40

• Swap 20 ↔ 40

Heap = [40, 30, 20, 10]

        40
       /  \
     30    20
    /
   10

---

Step 3: Continue Heapify Down at node (20)

• Children of 20: none (leaf node)

• Stop

---

Final Max-Heap:

        40
       /  \
     30    20
    /
   10

Array: [40, 30, 20, 10]

---

👉 This example demonstrates Heapify Down: after removing the root, the new root is pushed down until the heap property is restored.

---

✨ Notes

• Binary Heap maintains a complete binary tree structure.

• Priority Queue with Binary Heap gives:

• Insert → O(log n)

• Delete Max → O(log n)

• Find Max → O(1)

✨ C Program Priority Queue using Max Heap

#include <stdio.h>

#define MAX 100

struct Element {

    int value;

    int priority;

};

struct Element heap[MAX];

int size = 0;

// Function to swap two elements

void swap(struct Element *a, struct Element *b) {

    struct Element temp = *a;

    *a = *b;

    *b = temp;

}

// Function to heapify up (after insertion)

void heapifyUp(int index) {

    if (index == 0) return; // Reached root

    int parent = (index - 1) / 2;

    if (heap[parent].priority < heap[index].priority) {

        swap(&heap[parent], &heap[index]);

        heapifyUp(parent);

    }

}

// Function to heapify down (after deletion)

void heapifyDown(int index) {

    int left = 2 * index + 1;

    int right = 2 * index + 2;

    int largest = index;

    if (left < size && heap[left].priority > heap[largest].priority)

        largest = left;

    if (right < size && heap[right].priority > heap[largest].priority)

        largest = right;

    if (largest != index) {

        swap(&heap[index], &heap[largest]);

        heapifyDown(largest);

    }

}

// Function to insert an element

void insert(int value, int priority) {

    if (size >= MAX) {

        printf("Priority Queue is full!\n");

        return;

    }

    heap[size].value = value;

    heap[size].priority = priority;

    heapifyUp(size);

    size++;

}

// Function to get the highest priority element

struct Element getHighestPriority() {

    if (size == 0) {

        printf("Priority Queue is empty!\n");

        struct Element dummy = {-1, -1};

        return dummy;

    }

    return heap[0];

}

// Function to remove the highest priority element

void deleteHighestPriority() {

    if (size == 0) {

        printf("Priority Queue is empty!\n");

        return;

    }

    printf("Deleted element: %d with priority %d\n", heap[0].value, heap[0].priority);

    heap[0] = heap[size - 1];

    size--;

    heapifyDown(0);

}

// Function to display all elements

void display() {

    if (size == 0) {

        printf("Priority Queue is empty!\n");

        return;

    }

    printf("Priority Queue elements (value - priority):\n");

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

        printf("%d - %d\n", heap[i].value, heap[i].priority);

    }

}

int main() {

    int choice, value, priority;

    while (1) {

        printf("\n--- Priority Queue (Heap) Menu ---\n");

        printf("1. Insert\n2. Get Highest Priority\n3. Delete Highest Priority\n4. Display\n5. Exit\n");

        printf("Enter your choice: ");

        scanf("%d", &choice);

        switch (choice) {

            case 1:

                printf("Enter value and priority: ");

                scanf("%d%d", &value, &priority);

                insert(value, priority);

                break;

            case 2: {

                struct Element highest = getHighestPriority();

                if (highest.priority != -1) {

                    printf("Highest Priority Element: %d with priority %d\n", highest.value, highest.priority);

                }

                break;

            }

            case 3:

                deleteHighestPriority();

                break;

            case 4:

                display();

                break;

            case 5:

                printf("Exiting...\n");

                return 0;

            default:

                printf("Invalid choice!\n");

        }

    }

}