A simple priority queue project

This is a short project involving priority queues.  It is really nothing more than the solution of  UVa problem (10954 – Add All) using our own implementation of a heap data structure.  It is broken into phases as shown below.

Phase 1: Build a class called Heap.  In this class use a STL vector<int> to contain the heap values.  Create the proper type (either MaxHeap or MinHeap).  Create methods Size(), Insert() and Extract().  Now test your heap carefully.

Phase 2: Now create a constructor with a vector<int> as the parameter. The constructor does a BuildHeap operation on the internal vector after the parameter is copied to it.

Phase 3: Now write the main program to solve the above problem using a heap.  After reading in the data values into a vector create the heap using the above constructor.  The algorithm can then use the Heap to determine the final minimum cost result.

Combine all the files into one .cpp file and test using the debug support on the UVa site.  When you have this working submit the solution to the site.

When this is working on the site turn in the well documented source. The documentation should include your UVa login name as well as the usual method documention.  Also run this on the following data set and include your output.  Do not print the output window.  Redirect your output to a file and print that.  IE the command line parameters should be   <data.txt  >output.txt

19
79 0 94 67 20 85 65 87 33 77 42 99 87 34 62 90 3 54 3
23
95 30 40 33 2 42 77 61 60 45 44 90 37 38 21 99 5 45 27 76 72 90 31
24
32 29 65 81 70 62 87 1 59 31 65 45 61 81 64 59 39 7 45 42 80 22 82 80
0

Comments are closed.