You must fill out the functions below in the priority queue implementation in pq.c. When you are implementing these functions you should not break the encapsulation of the dynamic array. That is, you should not access the internal details of the dynamic array but should instead use the functions comprising the dynamic array's public interface.

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.

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. Both the dynamic array and the heap should not worry about allocating and freeing the memory for the void pointers.

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. Example sequence of calls: Suppose the user made this sequence of insertions into an empty struct pq called pq:

pq_insert(pq, "sixteen", 16); pq_insert(pq, "eight", 8); pq_insert(pq, "twenty", 20); pq_insert(pq, "four", 4); pq_insert(pq, "twelve", 16); 

Then suppose they ran this loop:

while (!pq_isempty(pq)) { printf("%s ", pq_remove_first(pq)); } 

The following should be the output of that loop:

four eight twelve sixteen twenty 

DYNAMIC ARRAY HEADER FILE-

#ifndef __DYNARRAY_H #define __DYNARRAY_H

/* * Structure used to represent a dynamic array. */ struct dynarray;

/* * Create a new dynamic array with a specified capacity. * * @param capacity the initial capacity of the array. Must be greater than 0. */ struct dynarray* dynarray_create(int capacity);

/* * Free the memory associated with a dynamic array. */ void dynarray_free(struct dynarray* da);

/* * Returns the size (i.e. the number of elements) of a dynamic array. */ int dynarray_size(struct dynarray* da);

/* * Returns the value of an existing element a dynamic array array. * * @param idx the index of the element whose value should be returned. Must * be between 0 and the size of the array. The special value -1 may also be * passed to return the element at the end of the array. */ void* dynarray_get(struct dynarray* da, int idx);

/* * Sets an existing element in a dynamic array array to a new value. * * @param idx the index of the element whose value is to be set. Must be * between 0 and the size of the array. The special value -1 may also be * passed to set the element at the end of the array. * @param val the new value to be set. */ void dynarray_set(struct dynarray* da, int idx, void* val);

/* * Inserts a new element to a dynamic array at a specified index. All existing * elements following the specified index are moved back to make room for the * new element. * * @param idx the index in the array at which to insert the new element. The * special value -1 may be passed to insert at the end of the array. * @param val the value to be inserted. */ void dynarray_insert(struct dynarray* da, int idx, void* val);

/* * Removes an element at a specified index from a dynamic array. All existing * elements following the specified index are moved forward to fill in the * gap left by the removed element. * * @param idx the index of the element to be removed. The special value -1 may * be passed to remove the element at the end of the array. */ void dynarray_remove(struct dynarray* da, int idx);

#endif DYNAMIC ARRAY C FILE-

#include #include #include

#include "dynarray.h"

struct dynarray { void** data; int size; int capacity; };

struct dynarray* dynarray_create(int capacity) {

assert(capacity > 0); struct dynarray* da = malloc(sizeof(struct dynarray)); assert(da);

da->data = malloc(capacity * sizeof(void*)); assert(da->data); da->size = 0; da->capacity = capacity;

return da;

}

void dynarray_free(struct dynarray* da) {

assert(da); free(da->data); free(da);

}

int dynarray_size(struct dynarray* da) {

assert(da); return da->size;

}

void* dynarray_get(struct dynarray* da, int idx) {

assert(da); assert((idx < da->size && idx >= 0) || idx == -1);

// Let users specify idx = -1 to indicate the end of the array. if (idx == -1) { idx = da->size - 1; }

return da->data[idx];

}

void dynarray_set(struct dynarray* da, int idx, void* val) {

assert(da); assert((idx < da->size && idx >= 0) || idx == -1);

// Let users specify idx = -1 to indicate the end of the array. if (idx == -1) { idx = da->size - 1; }

da->data[idx] = val;

}

void _dynarray_resize(struct dynarray* da, int new_capacity) {

assert(new_capacity > da->size); void** new_data = malloc(new_capacity * sizeof(void*)); assert(new_data);

// Copy the old data to the new array. for (int i = 0; i < da->size; i++) { new_data[i] = da->data[i]; }

// Free the old data and update da with the new data. free(da->data); da->data = new_data; da->capacity = new_capacity;

}

void dynarray_insert(struct dynarray* da, int idx, void* val) {

assert(da); assert((idx <= da->size && idx >= 0) || idx == -1);

// Let users specify idx = -1 to indicate adding to the end of the array. if (idx == -1) { idx = da->size; }

// Resize if needed. if (da->size == da->capacity) { _dynarray_resize(da, 2 * da->capacity); }

/* * Make space for the new value at idx by moving all the subsequent elements * back one spot in the array. */ for (int i = da->size; i > idx; i--) { da->data[i] = da->data[i-1]; }

da->data[idx] = val; da->size++;

}

void dynarray_remove(struct dynarray* da, int idx) {

assert(da); assert((idx < da->size && idx >= 0) || idx == -1);

// Let users specify idx = -1 to indicate the end of the array. if (idx == -1) { idx = da->size - 1; }

// Move each subsequent array element after idx into the space before it. for (int i = idx; i < da->size - 1; i++) { da->data[i] = da->data[i+1]; }

da->size--;

} PRIORITY QUEUE HEADER-

#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);

/* * Inserts an item with a specified priority into a priority queue. * * @param item This is a generic pointer to any kind of item to be inserted * into the priority queue. It can point to an int (i.e. an int*), string * (a char*), or any other type of data, even a struct of some sort (e.g. * a struct foo*). * * @param priority This is the priority value to associate with the item * being inserted into the priority queue. Lower values here correspond * to higher priorities. For example an item with priority value 0 will * be returned from the priority queue before an item with priority 5. */ 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 PRIORITY QUEUE IMPLEMETATION, FILE TO BE FIXED-

#include #include

#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 modify 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); /* FIXME: Complete this function */ /* * 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). */

}

/* * 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); /* FIXME: Complete this function */ }

/* * 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);

/* FIXME: Complete this function */ /* * 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. */

/* * 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.. */

/* * 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. */

/* * Return the extracted item, if the element taken out of the priority * queue is not NULL. */ }