Write the following functions in C. With the structure struct pq { struct dynarr
ID: 3831570 • Letter: W
Question
Write the following functions in C. With the structure
struct pq {
struct dynarray* heap;
};
struct pq_elem{
int priority;
void* item;
};
void pq_insert(struct pq* pq, void* item, int priority)
This function inserts a given piece of data (item) into the priority queue with the specified priority (priority). Importantly, lower values of priority correspond to items with higher priority relative to other items. For example, an item with priority 0 should be returned from the priority queue before an item with priority 5.
Implementing this function entails finding the correct location in the heap array in which to insert the new element, inserting it there, and then making sure the minimizing heap property (that every element's value is less than the values of its children) is maintained.
To implement this function, you will be introduced to the new concept of a void pointer (void*). This is simply a generic pointer that can point to a memory address of any type. The dynamic array implementation stores void pointers. We will use these to hold pointers to an auxiliary structure (struct pq_elem) representing a single element in the priority queue, including its priority value and its associated data.
void* pq_first(struct pq* pq)
This function simply returns the data represented by the highest-priority element in the priority queue. To do this, you will have to figure out the location in the heap array corresponding to the highest-priority element in the priority queue and return the data represented by that element (i.e. the item field of the struct pq_elem stored at that location in the priority queue).
void* pq_remove_first(struct pq* pq)
This function removes the highest-priority element from the priority queue and returns the data it represents. To implement this, you will have to find the same element in the heap array you found when implementing pq_first(). Here, however, you will also have to find the appropriate element to replace that element in the heap array, perform the replacement, and ensure that the minimizing heap property (that every element's value is less than the values of its children) is maintained.
Explanation / Answer
main.c
#include <stdio.h>
#include <assert.h>
#include "pq.h"
int main(int argc, char** argv) {
struct pq* pq = pq_create();
int nums[16] = { 16, 8, 24, 64, 12, 4, 32, 2, 48, 80, 88, 20, 40, 6, 72, 96 };
int min_so_far = 1000000;
int prev = 0;
for (int i = 0; i < 16; i++) {
printf("== Inserting %d...", nums[i]);
fflush(stdout);
pq_insert(pq, &nums[i], nums[i]);
if (nums[i] < min_so_far) {
min_so_far = nums[i];
}
int* first = pq_first(pq);
assert(*first == min_so_far);
printf(" SUCCEEDED! ");
}
for (int i = 0; i < 16; i++) {
int* first = pq_first(pq);
int* removed_first = pq_remove_first(pq);
printf("== Removing %d...", *removed_first);
fflush(stdout);
assert(*first == *removed_first);
assert(*first > prev);
prev = *first;
printf(" SUCCEEDED! ");
}
printf("== All tests passed! ");
}
pq.c
#include <stdlib.h>
#include <assert.h>
#include "dynarray.h"
#include "pq.h"
// This is the initial capacity that will be allocated for the heap.
#define INITIAL_HEAP_CAPACITY 16
/*
* This is the definition of the structure we will use to represent the
* priority queue. It contains only a dynamic array, which will be used to
* store the heap underlying the priority queue.
*/
struct pq {
struct dynarray* heap;
};
/*
* This is an auxiliary structure that we'll use to represent a single element
* in the priority queue. It contains two fields:
*
* priority - the priority value assigned to the item
* item - the pointer to the data item represented by this element
*
* Both of these will come directly from the corresponding values passed to
* pq_insert().
*/
struct pq_elem {
int priority;
void* item;
};
/*
* This function allocates and initializes a new priority queue.
*
* You should not modify this function.
*/
struct pq* pq_create() {
struct pq* pq = malloc(sizeof(struct pq));
assert(pq);
pq->heap = dynarray_create(INITIAL_HEAP_CAPACITY);
return pq;
}
/*
* This function frees the memory associated with a priority queue.
*
* You should not modify this function.
*/
void pq_free(struct pq* pq) {
assert(pq);
while(!pq_isempty(pq)){
pq_remove_first(pq);
}
dynarray_free(pq->heap);
free(pq);
}
/*
* This function returns 1 if the given priority queue is empty or 0
* otherwise.
*
* You should not mofidy this function.
*/
int pq_isempty(struct pq* pq) {
assert(pq);
return dynarray_size(pq->heap) == 0;
}
/*
* This function inserts a new item with a specified priority into a priority
* queue.
*
* You should complete the implementation of this function. The first part
* is done for, where a new element is created to be placed into the dynamic
* array underlying the priority queue.
*/
void pq_insert(struct pq* pq, void* item, int priority) {
assert(pq);
/*
* Allocate space for the new element to be placed into the priority queue
* and initialize it with the provided values.
*/
struct pq_elem* new_elem = malloc(sizeof(struct pq_elem));
new_elem->item = item;
new_elem->priority = priority;
/*
* Figure out where in the heap array to insert the new element represented
* by new_elem and insert it.
*/
dynarray_insert(pq->heap, -1, new_elem);
/*
* Restore the heap so that it has the property that every node's priority
* value is less than the priority values of its children. This can be
* done by "percolating" the newly added element up in the heap array. To
* perform the percolation, you will have to compare the priority values of
* the struct pq_elems in the heap array (i.e. by comparing the
* elem->priority values).
*/
int elem_index = dynarray_size(pq->heap)-1;
int parent_index = 0;
struct pq_elem *temp;
while(parent_index >= 0)
{
parent_index = (elem_index-1)/2;
temp = (struct pq_elem*)dynarray_get(pq->heap, parent_index);
if(temp->priority > new_elem->priority)
{
dynarray_set(pq->heap, parent_index, new_elem);
dynarray_set(pq->heap, elem_index, temp);
elem_index = parent_index;
}
else
{
break;
}
}
temp = NULL;
return;
}
/*
* This function returns the first (highest-priority) item from a priority
* queue without removing it.
*
* You should complete the implementation of this function.
*/
void* pq_first(struct pq* pq) {
assert(pq);
assert(dynarray_size(pq->heap) > 0);
struct pq_elem* first_elem = NULL;
/*
* Determine what index in the heap array corresponds to the highest-priority
* element (i.e. the one with the lowest priority value), and store the
* value there in first_elem.
*/
first_elem = (struct pq_elem*)dynarray_get(pq->heap, 0);
/*
* Return the extracted item, if the element taken out of the priority
* queue is not NULL.
*/
if (first_elem != NULL) {
return first_elem->item;
} else {
return NULL;
}
}
/*
* This function removes the first (highest-priority) element from a priority
* queue and returns its value.
*
* You should complete this function.
*/
void* pq_remove_first(struct pq* pq) {
assert(pq);
assert(dynarray_size(pq->heap) > 0);
struct pq_elem* first_elem = NULL;
struct pq_elem* last_elem = NULL;
/*
* Determine what index in the heap array corresponds to the highest-priority
* element (i.e. the one with the lowest priority value), and store the
* value there in first_elem.
*/
first_elem = (struct pq_elem*)dynarray_get(pq->heap, 0);
/*
* Replace the highest-priority element with the appropriate one from within
* the heap array. Remove that replacement element from the array after
* copying its value to the location of the old highest-priority element..
*/
last_elem = (struct pq_elem*)dynarray_get(pq->heap, -1);
dynarray_set(pq->heap, 0, last_elem);
dynarray_remove(pq->heap, -1);
last_elem = NULL;
/*
* Restore the heap so that it has the property that every node's priority
* value is less than the priority values of its children. This can be
* done by "percolating" the element that replaced the highest-priority
* element down in the heap array. To perform the percolation, you will
* have to compare the priority values of the struct pq_elems in the heap
* array (i.e. by comparing the elem->priority values). It may be helpful
* to write a helper function to accomplish this percolation down.
*/
int elem = 0;
int leftChild = 0;
int rightChild = 0;
int minChild = 0;
struct pq_elem* temp;
struct pq_elem* temp2;
while(1)
{
leftChild = (2 * elem) + 1;
rightChild = (2 * elem) + 2;
if(leftChild > dynarray_size(pq->heap)-1)
break;
else if(leftChild == dynarray_size(pq->heap)-1)
minChild = leftChild;
else
{
if(((struct pq_elem*)dynarray_get(pq->heap, leftChild))->priority > ((struct pq_elem*)dynarray_get(pq->heap, rightChild))->priority)
minChild = rightChild;
else
minChild = leftChild;
}
if((((struct pq_elem*)dynarray_get(pq->heap, elem))->priority) > (((struct pq_elem*)dynarray_get(pq->heap, minChild))->priority))
{
temp = (struct pq_elem*)dynarray_get(pq->heap, minChild);
temp2 = (struct pq_elem*)dynarray_get(pq->heap, elem);
dynarray_set(pq->heap, minChild, temp2);
dynarray_set(pq->heap, elem, temp);
elem = minChild;
}
else
break;
}
/*
* Return the extracted item, if the element taken out of the priority
* queue is not NULL.
*/
if (first_elem != NULL)
{
void *item = first_elem->item;
free(first_elem);
return item;
}
else
{
return NULL;
}
}
pq.h
/*
* This file contains the declarations of the structure and functions for a
* priority queue.
*/
#ifndef __PQ_H
#define __PQ_H
/*
* Structure used to represent a priority queue.
*/
struct pq;
/*
* Creates a new priority queue.
*/
struct pq* pq_create();
/*
* Frees the memory associated with a priority queue.
*/
void pq_free(struct pq* pq);
/*
* Returns 1 if the given priority queue is empty or 0 otherwise.
*/
int pq_isempty(struct pq* pq);
void pq_insert(struct pq* pq, void* item, int priority);
/*
* Returns the first (i.e. highest-priority) item in a priority queue without
* removing it from the queue.
*/
void* pq_first(struct pq* pq);
/*
* Removes the first (i.e. highest-priority) item in a priority queue and
* returns it.
*/
void* pq_remove_first(struct pq* pq);
#endif
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.