Requirements
● Fill in MyPriorityQueue.hpp

                                               

○ Your implementation must fit the interface given
○ Your implementation must be templated as provided.
○ Your implementation must be a binary min heap. If you don’t know why I used the

                                               

modifier “binary” here, don’t worry. It’s the min heap from class.

                                               

○ You do not need to write a copy constructor or an assignment operator, but knowing how to do so is generally a good thing.

                                               

○ All functions that need to be implemented have been started in the provided .hpp
○ For comparing keys, use the “natural” comparison offered by <. Any test cases provided

                                               

will have something for the key that has this defined.
○ If you want to define your own < for use in the second part, the Edge.hpp class will show

                                               

you how. If it isn’t clear, please ask!

                                               

○ Do not hard code for assumptions for how the tree will be used in the second part of the program.

                                               

● Write the function to compute the MST in proj5.cpp
○ You must use your PriorityQueue from the first part as appropriate.
○ Your implementation must be based on Prim’s algorithm, as shown in class.
○ You may assume the graph is complete: for all pairs of vertices i,j with i != j, there is a

                                               

positive edge weight.
○ You may assume the graph is simple: there are no parallel edges, and no self-loops. The

                                               

“edge” weight from i to i is set as 0 for all test cases.

                                               

○ Your implementation does not have to be the most efficient thing ever, but it cannot be “too slow.” In general, any test case that takes over two minutes on the grader’s computer may be deemed a wrong answer, even if it will later return a correct one.

                                               

You may not use parts of the C++ standard template library in this assignment except for std::vector. You may use parts of the standard that solve a problem that you can trivially make if

                                               

you needed to, such as std::max or std::swap. If you aren’t sure if something would be trivial, please ask. I am still working on exactly how to phrase this requirement -- I want you to be able to use std::max or std::swap but not std::priority_queue. Suggestions on wording welcome!