Repository navigation
Expand file tree
/
Copy pathpriorityqueue.h
More file actions
145 lines (129 loc) · 4.1 KB
/
Copy pathpriorityqueue.h
File metadata and controls
145 lines (129 loc) · 4.1 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#ifndef PRIORITYQUEUE_JL
#define PRIORITYQUEUE_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define PRIORITYQUEUE_MAX_SIZE 512 // The maximum number of elements that we can store in the priority queue.
// Define how an element of the priority queue is structured.
typedef struct{
int value; // The value that we need to store.
int priority; // Its priority. The smallest number leaves first.
} PQItem;
// Define how our (non linear and static) priority queue is structured.
// It's a min-heap (like heap.h) ordered by priority, so the element with the smallest priority is always at position 0.
typedef struct{
PQItem items[PRIORITYQUEUE_MAX_SIZE]; // The internal array (heap) to store our elements.
int size; // The current number of elements in our priority queue.
} PriorityQueue;
/********************/
/* FUNCTIONS */
/********************/
// Set Up the Priority Queue. We start with size 0 to show it's empty.
void initPQ(PriorityQueue *pq){
pq->size = 0;
}
// Check if the Priority Queue is Empty. Returns 1 if it's empty or 0 if it has elements.
int isEmptyPQ(PriorityQueue *pq){
if(pq->size == 0){
return 1;
}
else{
return 0;
}
}
// Check if the Priority Queue is Full. Returns 1 if it's full or 0 if it's not full.
int isFullPQ(PriorityQueue *pq){
if(pq->size >= PRIORITYQUEUE_MAX_SIZE){
return 1;
}
else{
return 0;
}
}
// Swap Two Elements of the Priority Queue.
void swapPQ(PriorityQueue *pq, int a, int b){
PQItem temp = pq->items[a];
pq->items[a] = pq->items[b];
pq->items[b] = temp;
}
// Move an Element Up while its Priority is Smaller than its Parent's one.
void siftUpPQ(PriorityQueue *pq, int index){
while(index > 0){
int parent = (index-1) / 2;
if(pq->items[index].priority >= pq->items[parent].priority){
break;
}
swapPQ(pq, index, parent);
index = parent;
}
}
// Move an Element Down while one of its Children has a Smaller Priority.
void siftDownPQ(PriorityQueue *pq, int index){
while(1){
int left = 2*index + 1;
int right = 2*index + 2;
int smallest = index;
if(left < pq->size && pq->items[left].priority < pq->items[smallest].priority){
smallest = left;
}
if(right < pq->size && pq->items[right].priority < pq->items[smallest].priority){
smallest = right;
}
if(smallest == index){
break;
}
swapPQ(pq, index, smallest);
index = smallest;
}
}
// Add a Value with a Priority. Returns 1 if successful or 0 if the priority queue is full.
int enqueuePQ(PriorityQueue *pq, int value, int priority){
if(isFullPQ(pq)){
return 0;
}
else{
pq->items[pq->size].value = value;
pq->items[pq->size].priority = priority;
pq->size++;
siftUpPQ(pq, pq->size-1);
return 1;
}
}
// Remove the Element with the Smallest Priority. Returns 1 if successful or 0 if the priority queue is empty.
int dequeuePQ(PriorityQueue *pq, int *value, int *priority){
if(isEmptyPQ(pq)){
return 0;
}
else{
*value = pq->items[0].value;
*priority = pq->items[0].priority;
pq->size--;
pq->items[0] = pq->items[pq->size];
siftDownPQ(pq, 0);
return 1;
}
}
// Peek at the Element with the Smallest Priority without Removing It. Returns 1 if successful or 0 if it's empty.
int peekPQ(PriorityQueue *pq, int *value, int *priority){
if(isEmptyPQ(pq)){
return 0;
}
else{
*value = pq->items[0].value;
*priority = pq->items[0].priority;
return 1;
}
}
// Print all Elements of the Priority Queue as (value, priority). Displays them in the order of the internal heap.
void printPQ(PriorityQueue *pq){
printf("[");
for(int i = 0; i < pq->size; i++){
printf("(%d, %d)", pq->items[i].value, pq->items[i].priority);
if(i < pq->size-1){
printf(", ");
}
}
printf("]\n");
}
#endif //PRIORITYQUEUE_JL