Basic Operations of the Priority Queue in C
1. Enqueue Operation
This operation can be used to add the new element to the priority queue with the given priority.
Algorithm
- Add the element to end of the heap.
- Restore the heap property by the comparing the added element with its parent. If it can violates the heap property, swap them.
- Continues this process up the heap until the correct position is found or root is reached.
2. Dequeue (Extract – Min/Max)
This operation can be used to removes and return the elements with the highest max in the max-heap and min in the min-heap of the priority queue.
Algorithms
- Replace the root of heap with the last element in the heap.
- Reduce the size of the heap by the one.
- Restore the heap property by the recursively comparing the new root with its children and swapping it
- with the higher priority child in the max-heap or the lower priority child in the min heap.
- Continues this process down the heap until the correct position is found or the leaf is reached.
3. Peek
This operation can be used to returns the element with the highest priority without the removing it from the priority queue.
Algorithm
- Return the element at the root of the heap.
4. Increase/Decrease Key
This operation can be used to change the priority of the element in the priority queue.
Algorithm
- Locate the element whose the priority needs to be updated.
- Update the priority of the element.
- If the priority is increased in the max-heap or decreased in the min-heap and it can restore the heap property by the heapifying up from the element.
- If the priority is decreased in the max-heap or increased in the min-heap and restore the heap property by the heapifying down from element.
C Program to Implement Priority Queue
Priority queue is an abstract data type(ADT) in the computer science which is designed to the operate much like the regular queue except that each element has the certain priority. The priority can determines the order in which elements are dequeued – elements with the higher priority are removed from queue before those with lower priority. It can makes the priority queues an essential tool in the scenarios where the some tasks inherently take the precedence over others.
In this article, we will implement the priority queue using C program.
Contact Us