CS 245 Homework 6
- Due Date
- 4:00 pm Fri Nov 27
- Assignment Name
- Persistent Priority Queue
- File Names
- pq.c
The code for the priority queue implementation (as a heap) that we have discussed is below. It stores integers in the range 0 to n - 1, where n is the maximum number of entries with priorities that are doubles.
Write a program called pq that implements this priority queue stored in a file. All entries will be stored in binary format.
The program will be run like this:
pq filename command other arguments
If the command is create or c, the second argument will be the size of the queue (maximum number of entries).
If the command is add or a, the next two arguments will be an integer value and a floating point priority.
If the command is remove or r, the program will remove the highest priority item and print it to standard output.
If the command is update or u, the next two arguments will be the item to update and the new priority.
Use the following format for the file:
- max size (call it n) (4 byte integer)
- current number of items (4 byte integer)
- n entries - each one is a 4 byte integer followed by a double, so 12 bytes.
- n index entries - each one is a 4 byte integer
- A 9 byte "signature" that is your win number
You can take the code from the priority queue example and modify it to open or create the file (fopen) (depending on the command line arguments), and translate array references to moving to the correct file position (fseek) and reading or writing the data (fread and fwrite). Do not use an array in memory to create the queue. Instead, translate all array references to setting the file position and reading or writing the data in that spot.
If you don't understand how to approach this, then ask for help (me - not claude or some other AI).
typedef struct {
int value;
double priority;
} entry;
typedef struct {
entry *array;
int size;
int last;
int *index;
} pq;
pq *pq_new(int size) {
pq *q = malloc(sizeof(pq));
q->size = size;
q->last = -1;
q->array = malloc(size * sizeof(entry));
q->index = malloc(size * sizeof(int));
return q;
}
bool pq_is_empty(pq *q) {
return q->last == -1;
}
void swim(pq *q, int position) {
entry e = q->array[position];
int current = position;
while (current > 0) {
int parent = (current - 1) / 2;
if (q->array[parent].priority < e.priority) {
q->array[current] = q->array[parent];
q->index[q->array[current].value] = current;
current = parent;
}
else {
break;
}
}
q->array[current] = e;
q->index[e.value] = current;
}
void pq_add(pq *q, int value, double priority) {
assert(q->last < q->size);
q->last++;
q->array[q->last].value = value;
q->array[q->last].priority = priority;
q->index[value] = q->last;
swim(q, q->last);
}
void sink(pq *q, int position) {
entry e = q->array[position];
int current = position;
while (true) {
int left = 2 * current + 1;
int right = left + 1;
if (left <= q->last && e.priority < q->array[left].priority) {
if (right <= q->last && q->array[left].priority < q->array[right].priority) {
q->array[current] = q->array[right];
q->index[q->array[current].value] = current;
current = right;
}
else {
q->array[current] = q->array[left];
q->index[q->array[current].value] = current;
current = left;
}
}
else {
if (right <= q->last && e.priority < q->array[right].priority) {
q->array[current] = q->array[right];
q->index[q->array[current].value] = current;
current = right;
}
else {
break;
}
}
}
q->array[current] = e;
q->index[e.value] = current;
}
int pq_remove(pq *q) {
int value = q->array[0].value;
q->array[0] = q->array[q->last];
q->index[q->array[0].value] = 0;
q->last--;
sink(q, 0);
return value;
}
void pq_update_priority(pq *q, int n, double priority) {
double old_priority = q->array[q->index[n]].priority;
q->array[q->index[n]].priority = priority;
if (old_priority < priority) swim(q, q->index[n]);
else sink(q, q->index[n]);
}
void pq_print(pq *q) {
for (int i = 0; i <= q->last; i++) {
printf("%d %f %d\n", q->array[i].value, q->array[i].priority, q->index[i]);
}
}