Priority Queue


A priority queue is a data structure that stores a collection of elements, each associated with a priority. The fundamental characteristic of a priority queue is that elements with higher priorities are served before elements with lower priorities.

In a priority queue, the main operations typically include:
Insertion (enqueue): Adding an element with a specified priority to the queue.
Deletion (dequeue): Removing the element with the highest priority from the queue.
Peek (front): Observing the element with the highest priority without removing it.

The priority queue can be implemented using various data structures, such as heaps, binary search trees, or arrays. The choice of implementation depends on the specific requirements and the efficiency of the operations needed.

Priority queues are widely used in various applications, including task scheduling, Dijkstra's algorithm for finding the shortest path in a graph, Huffman coding for data compression, and many more. They provide a way to efficiently manage and process elements based on their priorities, making them an essential tool in computer science and algorithm design.

The array implementation of a priority queue is straightforward and is often based on maintaining a partially ordered array, where the element at each position represents a priority. 

Heap sort is often associated with priority queues because it relies on the same underlying data structure: the heap. A binary heap is a complete binary tree that can be implemented efficiently using an array. In the context of priority queues, a max heap is typically used, where the priority of a parent is greater than or equal to the priorities of its children.

Here's a brief overview of how you can use a max heap to implement a priority queue and, if needed, use heap sort for sorting:


Heap-based implementation of a priority queue

It involves creating a binary heap data structure and maintaining the heap property as elements are inserted and removed. In a binary heap, the element with the highest priority is always the root of the heap(max heap). To insert an element, you would add it to the end of the heap and then perform the necessary heap operations (such as swapping the element with its parent) to restore the heap property. To retrieve the highest priority element, you would simply return the root of the heap.

To implement a priority queue using a heap, we can use the following steps:
  • Create a heap data structure (either a max heap or a min-heap)
  • To insert an element into the priority queue, add the element to the heap using the heap’s insert function. The heap will automatically rearrange the elements to maintain the heap property.
  • To remove the highest priority element (in a max heap) or the lowest priority element (in a min-heap), use the heap’s remove function. This will remove the root of the tree and rearrange the remaining elements to maintain the heap property.

C Implementation-Priority Queue using heap
/*******************************************************************************/
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

int heap[MAX_SIZE];
int size = 0;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insert(int value) {
    if (size >= MAX_SIZE) {
        printf("Heap overflow\n");
        return;
    }
    heap[size] = value;
    int current = size;
    int parent = (current - 1) / 2;
    while (current > 0 && heap[current] > heap[parent]) {
        swap(&heap[current], &heap[parent]);
        current = parent;
        parent = (current - 1) / 2;
    }
    size++;
}

int delete() {
    if (size <= 0) {
        printf("Heap underflow\n");
        return -1;
    }
    int value = heap[0];
    size--;
    heap[0] = heap[size];
    int current = 0;
    int left_child = current * 2 + 1;
    int right_child = current * 2 + 2;
    int max_child = (heap[left_child] > heap[right_child]) ? left_child : right_child;
    while (max_child < size && heap[current] < heap[max_child]) {
        swap(&heap[current], &heap[max_child]);
        current = max_child;
        left_child = current * 2 + 1;
        right_child = current * 2 + 2;
        max_child = (heap[left_child] > heap[right_child]) ? left_child : right_child;
    }
    return value;
}
void display()
{
 int i; 
 printf("The Priority Queue is..........\n");
 for(i=0;i<size;i++)
  printf("%d--",heap[i]);
}
 
void main()
{
    int n, ch;
 
    printf("\n1 - Insert an element into queue");
    printf("\n2 - Delete an element from queue");
    printf("\n3 - Display queue elements");
    printf("\n4 - Exit");
 
    
    while (1)
    {
        printf("\nEnter your choice : ");    
        scanf("%d", &ch);
 
        switch (ch)
        {
        case 1: 
            printf("\nEnter value to be inserted : ");
            scanf("%d",&n);
            insert(n);
            break;
        case 2:
            
            n=delete();
            if(n!=-1)
                printf("The highest priority elemnt is %d",n);
            break;
        case 3: 
            display();
            break;
        case 4: 
            exit(0);
        default: 
            printf("\nChoice is incorrect, Enter a correct choice");
        }
    }
}


Priority Queue using Linked List
/****************************************************************************/
#include <stdio.h>
#include <stdlib.h>

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

struct node* head = NULL;

void insert(int data, int priority) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->priority = priority;
    if (head == NULL || priority < head->priority) {
        temp->next = head;
        head = temp;
    }
    else {
        struct node* current = head;
        while (current->next != NULL && current->next->priority <= priority) {
            current = current->next;
        }
        temp->next = current->next;
        current->next = temp;
    }
}

void delete() {
    if (head == NULL) {
        printf("Queue is empty\n");
    }
    else {
        struct node* temp = head;
        printf("Deleted item: %d\n", temp->data);
        head = head->next;
        free(temp);
    }
}

void display() {
    if (head == NULL) {
        printf("Queue is empty\n");
    }
    else {
        struct node* current = head;
        printf("Queue elements:\n");
        while (current != NULL) {
            printf("%d ", current->data);
            current = current->next;
        }
        printf("\n");
    }
}

int main() {
    
    insert(4, 2);
    insert(2, 3);
    insert(5, 4);
    insert(3, 1);
    insert(1, 5);
    display();
    delete();
    display();
    return 0;
}
/* note: you can implement a menu driven program for various operations */

Comments

Post a Comment

Popular posts from this blog

Data Structures CST 201 KTU Third Semester Syllabus Notes and Solved Questions- Dr Binu V P 984739060

Dr BinuV P -About Me About The Course Syllabus Data Structures Lab CSL 201 ( Do the Programs to Understand the Concept Well) Model Question Paper CST 201 Data Structures University Question Papers CST 201 Data Structures Module-1 Basic Concepts of Data Structures 1.1 System Life Cycle 1.2 Algorithms , Performance Analysis  1.3 Space Complexity, Time Complexity  1.4 Asymptotic Analysis and Notations  1.5 Complexity Calculation of Simple Algorithms Module-2 Arrays and Searching  2.1 Polynomial representation using Arrays  2.2 Sparse matrix  2.3 Stacks  2.4 Queues 2.5 Circular Queues  2.6 Priority Queues 2.7 Double Ended Queues 2.8 Infix to  Postfix Conversion  2.9  Evaluation of Postfix Expression 2.10 Linear Search  2.11 Binary Search Module-3 Linked List and Memory Management 3.1 Linked List -Self Referential Structures  3.2 Dynamic Memory Allocation  3.3 Singly Linked List-Operations on Linked List 3.4 Doubly Linked List 3.5 Circular Linked List  3.6 Stack using Linked List  3.7 Queue
Read more

Depth First Search DFS

Image
Depth-First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It's often used to explore and analyze the connectivity of graphs, find paths, and solve problems related to connected components. Algorithm: The DFS algorithm operates on a graph, starting from an initial vertex. It maintains a stack (or uses recursion) to keep track of the vertices to visit. Initialization: Create a boolean array to mark visited vertices. Initialize all vertices as not visited. DFS Function: Choose a starting vertex (if the graph is disconnected, this process is repeated for unvisited vertices). Mark the chosen vertex as visited. Explore the chosen vertex's neighbours: If a neighbour is not visited, recursively call the DFS function on that neighbour. Repeat until all reachable vertices are visited. Here's a simplified recursive implementation in pseudocode: procedure DFS(vertex): mark vertex as visited for ea
Read more

Binary Search Tree ( BST) and operations

Image
A binary search tree (BST) is a data structure that organizes elements in a hierarchical structure, allowing for efficient search, insertion, and deletion operations. Here are the key properties and operations associated with a binary search tree: Properties of a Binary Search Tree: Binary Tree Structure:      Each node in the tree has at most two children: a left child and a right child.      The left subtree of a node contains only nodes with values less than the node's value.      The right subtree of a node contains only nodes with values greater than the node's value. Ordering Property:      For any node n , all nodes in its left subtree have values less than n, and all nodes in its right subtree           have values greater than n . No Duplicates:     A binary search tree does not allow duplicate values. Example: Figure  shows a binary search tree. Notice that this tree is obtained by inserting the values 13, 3, 4, 12, 14, 10, 5, 1, 8, 2, 7, 9, 11, 6, 18 in that order,
Read more