CSE 247: Priority Queues

Module 2: Priority Queues

Lab

Abstract: We have studied the Binary Heap data structure in class. Now it is your turn to implement one. In support of both sorting and the next programming assignment, we will implement a minimum priority queue, so that elements are extracted from smallest to largest.

Goals of this lab:

Understand how a binary tree is implemented in an array.
Understand the details of implementing a binary heap.

Introduction

Update your repository to make sure you have the most recent software checked out.
In your repositories you will find a heaps package in the labs source folder.

Your work for this lab

Implement the methods in the MinHeap class as described in the comments. Pay special attention to FIXME comments.
Run the JUnit test TestMinHeap as you work to make sure you are on track.
When you have everything working, run the HeapTimer experiment, which will produce CSV data in the outputs folder. Note: run this at the end it may take 5 or more minutes to run.
Remember to refresh your workspace to see the results of running timing experiments, if you have not set the automatic refresh with native hooks or polling option.
Plot the time taken for your implementation. It should look like an n log n plot.
Save the plot in your outputs folder.
- The plot won't save in a csv file
- So instead, right (control) click on the plot and save it as a picture named heap (.jpg or whatever) in the outputs folder.

Having trouble?

Post problems on piazza, but do not post code publicly there!

How to submit your work

Make sure all of your work is commited in your repository.
Note that we will run your heap solution against the JUnit test as it was given to you. If you modify that test in some way, the results you see may not correspond with the testing necessary to receive credit.
You can always revert any changes you make to the testing code back to what we gave you in the repository using Team…Revert, but be sure not to do that to your source code as it will wipe away work you may not have yet committed.
Your work will be graded as of the due date for this assignment.

Submitting your work (read carefully)

You must commit all of your work to your repository and push it. It's best to do this from the top-most level of your repository, which bears your wustl key.

Last modified 09:46:23 CDT 22 August 2016