• Macquarie Home »
• Faculty of Science »
• Computing »
• Undergraduate »
• Unit List

Exercises

1. Compile and run the programs pq.cpp and pq1.cpp provided in week 7 lectures and make sure that you understand how they work.

2. (*) Since priority queue and heap operations are analgous, we can write a simple-minded heapsort by :
   1. Inserting all array values into a priority queue (corresponds to step 1 make a heap)
   2. One by one remove largest from priority queue and put into array (corresponds to step 2)
   Let us implement this version using the program simpleheapsort.cpp as a template for you to complete.

   Submit simpleheapsort.cpp to web-CT

   .

3. If you haven't used exceptions before you may wish to first read exceptions in c++ .

4. (*) Now we will be more object-oriented and generalised. We will use Carranos files
   1. Heap.h
   2. Heap.cpp
   3. HeapException.h
   4. KeyedItem.h
   Note that if using dev-cpp all files must be ADD'ed to the same project. If using unix then put in same directory(folder) and use g++ *.cpp (it is clever enough to work out which files include which and compile and link them appropriately as long as there is only one main).

   Write a main program which implements heapsort according to the algorithm discussed in lectures( and/or Carrano). Complete the program template heapsort.cpp .

   Submit heapsort.cpp via web-CT

   .

5. (*) Experimentally compare your implementation with another sorting function, for example quicksort for an array. (Run your algorithm for a number of sizes of array. Do a similar test for another sorting algorithm. Plot the two graphs and add it to your portfolio; include a short explanation comparing the two graphs.)