priority queue c program

Guri Bee

3 min read

·

19-10-2024

1

0

Share

Unlocking Efficiency: A Deep Dive into Priority Queues in C

Priority queues are fundamental data structures in computer science, enabling efficient organization and retrieval of elements based on their importance. In this article, we'll explore the implementation of priority queues in C, delving into their core concepts and practical applications.

Understanding Priority Queues

A priority queue, as the name suggests, is a queue where elements are processed not in the order they are added (like a standard queue) but based on their priority. This priority can be determined by various criteria, such as:

• Numerical value: Items with higher values are prioritized.
• Custom comparison function: A user-defined function can define the priority logic based on specific attributes.

C Implementation: Building a Priority Queue

We can implement a priority queue in C using a binary heap, a tree-based data structure that efficiently maintains the priority order. Here's a basic implementation using an array to represent the heap:

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100 

// Structure to represent a node in the heap
typedef struct {
    int data;
    int priority;
} Node;

// Array to store the heap
Node heap[MAX_SIZE];
int heapSize = 0;

// Function to swap two nodes
void swap(Node *a, Node *b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// Function to heapify the tree, ensuring the priority property holds
void heapify(int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < heapSize && heap[left].priority < heap[smallest].priority) {
        smallest = left;
    }

    if (right < heapSize && heap[right].priority < heap[smallest].priority) {
        smallest = right;
    }

    if (smallest != index) {
        swap(&heap[index], &heap[smallest]);
        heapify(smallest);
    }
}

// Function to insert a new node into the heap
void insert(Node node) {
    heap[heapSize] = node;
    heapSize++;

    // Adjust the heap after insertion
    int current = heapSize - 1;
    while (current > 0 && heap[current].priority < heap[(current - 1) / 2].priority) {
        swap(&heap[current], &heap[(current - 1) / 2]);
        current = (current - 1) / 2;
    }
}

// Function to extract the element with the highest priority
Node extractMin() {
    Node min = heap[0];
    heap[0] = heap[heapSize - 1];
    heapSize--;
    heapify(0);
    return min;
}

// Function to print the heap
void printHeap() {
    for (int i = 0; i < heapSize; i++) {
        printf("(%d, %d) ", heap[i].data, heap[i].priority);
    }
    printf("\n");
}

int main() {
    Node n1 = {10, 5};
    Node n2 = {5, 2};
    Node n3 = {15, 8};
    
    insert(n1);
    insert(n2);
    insert(n3);
    
    printf("Heap: ");
    printHeap();

    Node extracted = extractMin();
    printf("Extracted: (%d, %d)\n", extracted.data, extracted.priority);

    printf("Heap after extraction: ");
    printHeap();
    
    return 0;
}

Key Points:

• Heapify: The heapify function ensures that the heap property is maintained after insertion or deletion. This is achieved by recursively comparing nodes and swapping them until the priority order is restored.
• Insertion: The insert function places the new node at the end of the heap and then "bubbles up" the node by swapping it with its parent until the priority property is satisfied.
• Extraction: The extractMin function extracts the highest priority node (root of the heap) and then restores the heap property by "sifting down" a replacement node from the end.

Applications of Priority Queues

Priority queues are widely used in various algorithms and applications, including:

• Event scheduling: Events with earlier deadlines are prioritized in scheduling systems.
• Shortest path algorithms: Nodes with shorter distances to the destination are prioritized in path finding algorithms like Dijkstra's algorithm.
• Task management: Tasks with higher importance levels are handled first in task scheduling systems.
• Compression algorithms: Priority queues are used in Huffman coding to assign shorter codewords to more frequent symbols.

Further Exploration

For deeper understanding and practical implementation, consider:

• Dynamic resizing: Implement a mechanism to dynamically resize the heap array if it becomes full.
• Custom priority logic: Implement priority queues that can handle user-defined comparison functions to define specific priority criteria.
• Heap sort: Explore how priority queues can be used to implement the efficient heap sort algorithm.

By understanding and mastering priority queues, you equip yourself with a powerful tool for optimizing algorithms and solving various computational problems.