Data Structures
and
Algorithms(INSY
8321)
Faculty of Information Technology
Academic Year: 2024-2025
Lecturer: Mr. BYIRINGIRO Eric
GROUP PRESENTATION
TOPIC: PRIORITY QUEUE IMPLEMENTATION
IN C
GROUP 2
• 25702 Nduwayezu Sophonie
GROUP MEMBERS:
• 25718 Mahamat Adji Zezerti Abdramane
• 25612 Nze Ndong Andre Pierre Junior
• 25726 Bazumutima Emmanuel
• 25613 Sheman JR. Albert D
• 25734 Niyonkuru Lionel
• 25680 Niyonshuti Blaise
• 25693 Ukobizaba Gerchome
Implementing a Priority
Queue in C
INTRODUCTION
A priority queue is an abstract data structure where each
element is associated with a priority, and elements with
higher priority are dequeued before those with lower priority.
In this detailed guide, we'll implement a priority queue in C
using a max-heap (where higher priority means larger
values) as the underlying structure. We'll cover insertion,
deletion, and priority-based element management, with at
least two examples for each part to illustrate the concepts.
Understanding the Priority Queue
Key Operations Heap Structure
• Insertion: Adding an element with a specified The heap will be represented as an array, where
priority for any node at index i:
• Deletion: Removing the element with the • Left child is at 2*i + 1
highest priority
• Right child is at 2*i + 2
• Priority-based management: Ensuring elements
• Parent is at (i-1)/2
are processed according to their priority
We'll use a max-heap to implement the priority
queue because it efficiently maintains the highest-
priority element at the root.
Data Structure Definition
We define a priority queue with:
• An array to store elements (each element has a value and priority).
• A capacity to limit the size.
• A size counter to track the number of elements.
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int value;
int priority;
} Element;
typedef struct {
Element heap[MAX_SIZE];
int size;
} PriorityQueue;
void initPriorityQueue(PriorityQueue *pq) {
pq->size = 0;
}
void printQueue(PriorityQueue *pq) {
if (pq->size == 0) {
printf("Priority queue is empty!\n");
return;
}
printf("Priority Queue (value, priority):\n");
for (int i = 0; i < pq->size; i++) {
printf("Element %d: (%d, %d)\n", i, pq->heap[i].value, pq->heap[i].priority);
}
}
int main() {
PriorityQueue pq;
// Initialize the priority queue
initPriorityQueue(&pq);
EXPLANATION OF THE DATA STRUCTURE DEFINITION
This code defines the basic structure of the priority queue and demonstrates its initialization and manual element addition.
1. Structure Definitions:
• Element struct: Contains value (e.g., task ID) and priority (e.g., urgency).
• PriorityQueue struct: Contains an array heap of Elements (max size 100) and size to track the number of elements.
• MAX_SIZE is set to 100, limiting the queue capacity.
2. Initialization:
• initPriorityQueue(&pq) sets pq->size = 0, creating an empty queue.
3. Test Case 1: Empty Queue:
• Call printQueue(&pq) when size is 0.
• Since pq->size == 0, it prints "Priority queue is empty!".
4. Test Case 2: Adding Elements:
• Manually add an element at index 0: pq.heap[0].value = 1, pq.heap[0].priority = 5, increment size to 1.
• Add another at index 1: pq.heap[1].value = 2, pq.heap[1].priority = 3, increment size to 2.
• Call printQueue(&pq):
• Loop from i = 0 to size - 1 (1).
• Print Element 0: (1, 5) and Element 1: (2, 3).
5. Capacity Check:
• Print size (2) and MAX_SIZE (100) to show current usage vs. capacity.
THE OUTPUT OF THE DATA STRUCUTRE
DEFINITION
Test Case 1: Empty Queue Priority queue is empty!
Test Case 2: Adding Elements Priority Queue (value, priority): Element 0: (1, 5) Element 1: (2, 3)
Current size: 2, Max capacity: 100
Insertion Process
Add to end
Place the new element at the end of the heap (array)
Heapify up
Compare the element with its parent and swap if the parent's priority is lower
Repeat
Continue until the heap property is restored (parent has higher priority than children)
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int value;
int priority;
} Element;
typedef struct {
Element heap[MAX_SIZE];
int size;
} PriorityQueue;
void initPriorityQueue(PriorityQueue *pq) {
pq->size = 0;
}
void swap(Element *a, Element *b) {
Element temp = *a;
*a = *b;
*b = temp;
}
The explanation of the Insertion queue
This code implements the insert function for a max-heap-based priority queue, maintaining the heap property (parent priority ≥ child priority).
1. Initialization:
• initPriorityQueue(&pq) sets pq->size = 0.
2. Example 1: Task Scheduling:
• Insert Task A (1, 5):
• size = 0, so index = 0.
• Set heap[0].value = 1, heap[0].priority = 5, size = 1.
• Since index = 0 (root), no parent to compare, so no swaps.
• Insert Task B (2, 3):
• size = 1, so index = 1.
• Set heap[1].value = 2, heap[1].priority = 3, size = 2.
• Parent index = (1-1)/2 = 0 (Task A, priority 5).
• Compare: 5 ≥ 3, so no swap.
• Print Queue:
• size = 2, print heap[0] = (1, 5) and heap[1] = (2, 3).
3. Reset Queue:
• initPriorityQueue(&pq) sets size = 0.
4. Example 2: Network Packet Processing:
• Insert Packet X (101, 10):
• size = 0, index = 0.
• Set heap[0].value = 101, heap[0].priority = 10, size = 1.
• Root node, no swaps.
• Insert Packet Y (102, 15):
• size = 1, index = 1.
• Set heap[1].value = 102, heap[1].priority = 15, size = 2.
• Parent index = (1-1)/2 = 0 (Packet X, priority 10).
• Compare: 10 < 15, swap heap[0] and heap[1].
• New index = 0, no further parent, stop.
• Print Queue:
• size = 2, print heap[0] = (102, 15) and heap[1] = (101, 10).
The output of the Insertion queue
Task Scheduling Example: After inserting Task A (1,5) and Task B (2,3): Priority Queue (value, priority):
Element 0: (1, 5) Element 1: (2, 3)
Network Packet Example: After inserting Packet X (101,10) and Packet Y (102,15): Priority Queue (value,
priority): Element 0: (102, 15) Element 1: (101, 10)
Insertion Examples
Task Scheduling Example 1
Suppose we're scheduling tasks where priority represents urgency
(higher is more urgent):
•
2 Network Packet Processing Example
Insert Task A: value = 1 (task ID), priority = 5. Added at index 0
(root, since queue is empty) For network packets, priority indicates importance:
• Insert Task B: value = 2, priority = 3. Added at index 1, compared • Insert Packet X: value = 101 (packet ID), priority = 10. Added at
with parent (Task A, priority 5 > 3), no swap needed index 0
• Result: Heap = [(1,5), (2,3)] • Insert Packet Y: value = 102, priority = 15. Added at index 1,
compared with parent (Packet X, 10 < 15), swap. Packet Y
becomes root
• Result: Heap = [(102,15), (101,10)]
Deletion Process
Heapify down
Replace with last element
Compare the new root with its children and swap with the larger child if
Remove root
Move the last element to the root necessary, repeating until the heap property is restored
Save the root element to return its value
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int value;
int priority;
} Element;
typedef struct {
Element heap[MAX_SIZE];
int size;
} PriorityQueue;
void initPriorityQueue(PriorityQueue *pq) {
pq->size = 0;
}
void swap(Element *a, Element *b) {
Element temp = *a;
*a = *b;
*b = temp;
}
void manualInsert(PriorityQueue *pq, int value, int priority) {
if (pq->size >= MAX_SIZE) {
printf("Priority queue is full!\n");
return;
}
Explanation of the Deletion Process
This code implements the deleteMax function to remove and return the highest-priority element from a max-heap. Since insert is not included, manualInsert sets up the heap manually.
1. Initialization:
• initPriorityQueue(&pq) sets pq->size = 0.
2. Example 1: Task Scheduling:
• Setup:
• manualInsert(&pq, 1, 5): heap[0] = (1, 5), size = 1.
• manualInsert(&pq, 2, 3): heap[1] = (2, 3), size = 2.
• Heap is [(1, 5), (2, 3)] (assume max-heap order for simplicity).
• First Delete:
• size = 2, not empty.
• Save max = heap[0] = (1, 5).
• Decrement size = 1.
• Move heap[1] = (2, 3) to heap[0].
• Heapify down from index = 0:
• Left child: 2*0+1 = 1, out of bounds (1 ≥ size).
• Right child: 2*0+2 = 2, out of bounds.
• No swaps needed.
• Return (1, 5), print "Deleted: Task 1, Priority 5".
• Second Delete:
• size = 1, not empty.
• Save max = heap[0] = (2, 3).
• Decrement size = 0.
• No heapify needed (empty heap).
• Return (2, 3), print "Deleted: Task 2, Priority 3".
3. Reset Queue:
• initPriorityQueue(&pq) sets size = 0.
4. Example 2: Network Packet Processing:
• Setup:
• manualInsert(&pq, 101, 10): heap[0] = (101, 10), size = 1.
• manualInsert(&pq, 102, 15): heap[1] = (102, 15), size = 2.
Output of the Deletion Process
Task Scheduling Example: Deleted: Task 1, Priority 5 Deleted: Task 2, Priority 3
Network Packet Example: Deleted: Packet 102, Priority 15 Deleted: Packet 101, Priority 10
Priority-Based Element Management
Peek Update Priority
View the highest-priority element without removing it Modify an element's priority and adjust the heap
k#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int value;
int priority;
} Element;
typedef struct {
Element heap[MAX_SIZE];
int size;
} PriorityQueue;
void initPriorityQueue(PriorityQueue *pq) {
pq->size = 0;
}
void swap(Element *a, Element *b) {
Element temp = *a;
*a = *b;
*b = temp;
}
void insert(PriorityQueue *pq, int value, int priority) {
if (pq->size >= MAX_SIZE) {
printf("Priority queue is full!\n");
return;
}
int index = pq->size;
pq->heap[index].value = value;
pq->heap[index].priority = priority;
pq->size++;
while (index > 0) {
int parent = (index - 1) / 2;
if (pq->heap[parent].priority < pq->heap[index].priority) {
swap(&pq->heap[parent], &pq->heap[index]);
index = parent;
} else {
break;
}
Explanation on Peek
This code implements the peek function to view the highest-priority element without removing it.
1. Initialization:
• initPriorityQueue(&pq) sets pq->size = 0.
2. Example 1: Task Scheduling:
• Setup:
• manualInsert(&pq, 1, 5): heap[0] = (1, 5), size = 1.
• manualInsert(&pq, 2, 3): heap[1] = (2, 3), size = 2.
• Heap is [(1, 5), (2, 3)] (assume max-heap order).
• Peek:
• size = 2, not empty.
• Return heap[0] = (1, 5).
• Print "Peek: Task 1, Priority 5".
3. Reset Queue:
• initPriorityQueue(&pq) sets size = 0.
4. Example 2: Network Packet Processing:
• Setup:
• manualInsert(&pq, 101, 10): heap[0] = (101, 10), size = 1.
• manualInsert(&pq, 102, 15): heap[1] = (102, 15), size = 2.
• Heap is [(102, 15), (101, 10)] (assume max-heap order).
• Peek:
• size = 2, not empty.
• Return heap[0] = (102, 15).
• Print "Peek: Packet 102, Priority 15".
Output (Peek)
Task Scheduling Example: Peek: Task 1, Priority 5
Network Packet Example: Peek: Packet 102, Priority 15
The above code is for peek and the following one is for update priority
#include <stdio.h> #include <stdlib.h>
#define MAX_SIZE 100
typedef struct { int value; int priority; } Element;
typedef struct { Element heap[MAX_SIZE]; int size; } PriorityQueue;
void initPriorityQueue(PriorityQueue *pq) { pq->size = 0; }
void swap(Element *a, Element *b) { Element temp = *a; *a = *b; *b = temp; }
void manualInsert(PriorityQueue *pq, int value, int priority) { if (pq->size >= MAX_SIZE) { printf("Priority queue is full!\n"); return; } pq->heap[pq->size].value = value; pq->heap[pq->size].priority = priority; pq->size++; }
void updatePriority(PriorityQueue *pq, int value, int newPriority) { int index = -1; for (int i = 0; i < pq->size; i++) { if (pq->heap[i].value == value) { index = i; break; } }
if (index == -1) {
printf("Element not found!\n");
return;
}
int oldPriority = pq->heap[index].priority;
pq->heap[index].priority = newPriority;
if (newPriority > oldPriority) {
while (index > 0) {
int parent = (index - 1) / 2;
if (pq->heap[parent].priority < pq->heap[index].priority) {
swap(&pq->heap[parent], &pq->heap[index]);
index = parent;
} else {
break;
}
}
} else {
while (index < pq->size) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
if (left < pq->size && pq->heap[left].priority > pq->heap[largest].priority) {
largest = left;
}
if (right < pq->size && pq->heap[right].priority > pq->heap[largest].priority) {
largest = right;
}
Explanation on update Priority function
This code implements the updatePriority function to change an element’s priority and restore the max-heap property.
1. Initialization:
• initPriorityQueue(&pq) sets pq->size = 0.
2. Example 1: Task Scheduling:
• Setup:
• manualInsert(&pq, 1, 5): heap[0] = (1, 5), size = 1.
• manualInsert(&pq, 2, 3): heap[1] = (2, 3), size = 2.
• Heap is [(1, 5), (2, 3)].
• Before Update:
• Print queue: Element 0: (1, 5), Element 1: (2, 3).
• Update Priority (Task B, value 2, newPriority 7):
• Search for value = 2: Found at index = 1.
• oldPriority = 3, set heap[1].priority = 7.
• Since 7 > 3, heapify up:
• Parent index = (1-1)/2 = 0 (Task A, priority 5).
• Compare: 5 < 7, swap heap[0] = (2, 7) and heap[1] = (1, 5).
• New index = 0, no parent, stop.
• Heap becomes [(2, 7), (1, 5)].
• After Update:
• Print queue: Element 0: (2, 7), Element 1: (1, 5).
3. Reset Queue:
• initPriorityQueue(&pq) sets size = 0.
4. Example 2: Network Packet Processing:
• Setup:
• manualInsert(&pq, 101, 10): heap[0] = (101, 10), size = 1.
• manualInsert(&pq, 102, 15): heap[1] = (102, 15), size = 2.
• Heap is [(102, 15), (101, 10)].
• Before Update:
• Print queue: Element 0: (102, 15), Element 1: (101, 10).
• Update Priority (Packet X, value 101, newPriority 5):
Output (Update priority)
Task Scheduling Example: Before update: Priority Queue (value, priority): Element 0: (1, 5) Element 1: (2,
3) After updating Task B to priority 7: Priority Queue (value, priority): Element 0: (2, 7) Element 1: (1, 5)
Network Packet Example: Before update: Priority Queue (value, priority): Element 0: (102, 15) Element 1:
(101, 10) After updating Packet X to priority 5: Priority Queue (value, priority): Element 0: (102, 15)
Element 1: (101, 5)
Time Complexity and Conclusion
O(log n)
Insertion
Due to heapify up operation
O(log n)
Deletion
Due to heapify down operation
O(1)
Peek
As it accesses the root
O(n)
Update Priority
O(n) to find the element, O(log n) to heapify
This implementation demonstrates a priority queue in C using a max-heap, covering insertion, deletion, and priority-based management. The examples (task
scheduling and network packet processing) show practical applications, such as prioritizing urgent tasks or important packets. The code is robust, handling
edge cases like full or empty queues, and provides a foundation for further optimization (e.g., using a hash table for O(log n) priority updates).
