Basic Operations of the Priority Queue in C

Representation of Priority Queue in C

Priority queues can typically implemented using the data structures that can efficiently support the required operations – most commonly binary heaps. The binary heap is the complete binary tree where the each node is smaller than its children (min-heap) or larger than its children (max-heap). It can ensuring the retrieval of the node with the highest or the lowest value....

Basic Operations of the Priority Queue in C

1. Enqueue Operation...

C Program to Implement Priority Queue

C #include #include // Define maximum size of the priority queue #define MAX 100 // Define PriorityQueue structure typedef struct { int items[MAX]; int size; } PriorityQueue; // Define swap function to swap two integers void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } // Define heapifyUp function to maintain heap property // during insertion void heapifyUp(PriorityQueue* pq, int index) { if (index && pq->items[(index - 1) / 2] > pq->items[index]) { swap(&pq->items[(index - 1) / 2], &pq->items[index]); heapifyUp(pq, (index - 1) / 2); } } // Define enqueue function to add an item to the queue void enqueue(PriorityQueue* pq, int value) { if (pq->size == MAX) { printf("Priority queue is full\n"); return; } pq->items[pq->size++] = value; heapifyUp(pq, pq->size - 1); } // Define heapifyDown function to maintain heap property // during deletion int heapifyDown(PriorityQueue* pq, int index) { int smallest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < pq->size && pq->items[left] < pq->items[smallest]) smallest = left; if (right < pq->size && pq->items[right] < pq->items[smallest]) smallest = right; if (smallest != index) { swap(&pq->items[index], &pq->items[smallest]); heapifyDown(pq, smallest); } } // Define dequeue function to remove an item from the queue int dequeue(PriorityQueue* pq) { if (!pq->size) { printf("Priority queue is empty\n"); return -1; } int item = pq->items[0]; pq->items[0] = pq->items[--pq->size]; heapifyDown(pq, 0); return item; } // Define peek function to get the top item from the queue int peek(PriorityQueue* pq) { if (!pq->size) { printf("Priority queue is empty\n"); return -1; } return pq->items[0]; } // Define main function int main() { // Initialize priority queue PriorityQueue pq = { { 0 }, 0 }; // Add items to the queue enqueue(&pq, 3); enqueue(&pq, 2); enqueue(&pq, 15); enqueue(&pq, 5); enqueue(&pq, 4); enqueue(&pq, 45); // Dequeue an item and print it printf("%d dequeued from queue\n", dequeue(&pq)); // Print the top item of the queue printf("Top element is %d\n", peek(&pq)); return 0; }...

Time and Space Complexity

Time complexity: O(log n), where n is the number of nodes.Space complexity: O(n), where n is the number of elements in the priority queue....

Applications of the Priority Queue in C

It can applies on the Dijkstra’s and prim’s algorithms is used for the finding the shortest path and minimum spanning tree in graph theory.It can used in CPU Scheduling in the operating systems use the priority queues to the manage process scheduling.It can applies on the Bandwidth Management used in network routers to manage the packet transmission priority.It can applies on Event Simulation for the manages events in the simulations based on their scheduled time....

Conclusion

Priority queues are the versatile and essential the data structures in the computer science. It can useful for any scenario where the elements must be processed according to their importance rather than just their order of the arrival. Efficient implementation of the priority queues particularly using heaps and allowing for the high performance handling of the dynamic priority based data. Make them the indispensable in the fields ranging from the systems design to algorithm optimization....