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. Note this is different from the example program where we did not have this auxiliary structure and we did not have 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.

PQ.C IMPLEMENTATION FILE

/*

* This file contains the implementation of a priority queue.

*

* You must complete the implementations of these functions:

* pq_insert()

* pq_first()

* pq_remove_first()

*/

#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.

*/

}