CS230 Lab

Lab

Heap sorting and Priority Queues

 

Task 1: Heap Sorting

In this task we will implement one more method for sorting: Heap Sort

Download the lab12 folder from the download directory.

You will complete the class HeapSort.java, located in the javafoundations package.

Since you will want to be able to sort different types of objects and compare them, the class is defined as follows:

    public class HeapSort<T extends Comparable<T>>

Notice that there is an instance variable maxHeap, of type MaxHeap<T> .
Since MaxHeap is an Interface, it cannot be instantiated (obviously). So, you will need to choose a specific implementation of this Interface in order to initialize that instance variable. We suggest you use the LinkedMaxHeap implementation of the MaxHeap Interface.

Step 1

Define a method with the following header:

    public Vector<T> sortInDescending(Vector<T> toSort)

Step 2

Write a driver class to test the sorting method. Where should you save this class? Should it be part of the javafoundations package, or not?

Step 3

Test it with a couple of different kinds of objects, such as Integers and Strings.

What if you wanted to sort in increasing order? Do so by using a MaxHeap again, not a MinHeap.

 

Task 2: Using a Priority Queue: A Very Simple Scheduler

In this task, you will write a simplified scheduler. The idea is that tasks arrive, one after the other, to be executed by a machine. Each task has a priority, which determines the order in which tasks will be scheduled and executed. Each task will occupy the machine for a number of cycles, and when it is done the next task will start. What kind of Data Structure would you use to hold the tasks? hmmm...

The Task class

We will create a class to represent a Task object. The Task objects should contain the following data:

  • String name: The name of the task.
  • int timeNeeded: The amount of time the task will need to run on the CPU to complete.
  • int timeIn: The time when the task arrived and was added to the scheduler.
  • int priority: The priority of the task, an int in the range [1 .. 5], where larger numbers mean higher priority

    Think about what methods you need to add to this class, and add them. Here is some sample (by no means complete) testing of the Task code:

    t1:
      Houseparty --10 cycles priority 3
    t2:
      Netflix --7 cycles priority 1
    t3:
      BlueJ --5 cycles priority 3

    t1.compareTo(t2): 2
    t1.compareTo(t1): 0
    t2.compareTo(t1): -2
    t3.compareTo(t1): 0

The Scheduler class

Write a Scheduler class to represent the Scheduler itself. You must keep track of the number of cycles (time that has passed) as you run scheduled tasks. You will also need a PriorityQueue to store the tasks.

In addition to a constructor, you must also include these two methods:

  • add(task): to add the input task to the scheduler, and
  • runTask(): to simulate the scheduler running the next task

The Driver class

Finally, write a simple driver that adds some tasks to a scheduler and runs them. Your driver will create a Scheduler, and then add new tasks to it and run them. Note that your Driver should emulate interspersed running tasks and adding tasks.
The table below lists a possible to-do list for a Scheduler. Below the table, sample (yet not exhaustive) testing of the SchedulerDriver appears. Note that in this case, the program is scheduling the life of a CS230 student.

**Scheduler to do** **Task** **Duration** **Priority**
add task Work on cs230 final project 400 4
add task Go to bathroom 10 5
add task Eat dinner 30 2
run task
add task Do other homework 100 1
run task
add task Procrastinate online 200 3
run task
run task
run task
run task

Here is sample transcript:

Task Queue Contents:   
 Priority: 4. Work on cs230 final project: needs 400 cycles  
 Priority: 5. Go to bathroom : needs 10 cycles  
 Priority: 2. Eat dinner: needs 30 cycles

---- EXECUTING HIGHEST PRIORITY TASK ------   
 ...Running Go to bathroom for 10 cycles.  
 ...Go to bathroom was in the system for 10 cycles.  
 ...Clock is now 10 cycles.  
 ---- TASK COMPLETED ------

Task Queue Contents:   
 Priority: 2. Eat dinner: needs 30 cycles  
 Priority: 4. Work on cs230 final project: needs 400 cycles  
 Priority: 1. Do other homework: needs 100 cycles

---- EXECUTING HIGHEST PRIORITY TASK ------   
 ...Running Work on cs230 final project for 400 cycles.  
 ...Work on cs230 final project was in the system for 410 cycles.  
 ...Clock is now 410 cycles.  
 ---- TASK COMPLETED ------

Task Queue Contents:   
 Priority: 1. Do other homework: needs 100 cycles  
 Priority: 3. Procrastinate online: needs 200 cycles  
 Priority: 2. Eat dinner: needs 30 cycles

---- EXECUTING HIGHEST PRIORITY TASK ------   
 ...Running Procrastinate online for 200 cycles.  
 ...Procrastinate online was in the system for 200 cycles.  
 ...Clock is now 610 cycles.  
 ---- TASK COMPLETED ------

Task Queue Contents:   
 Priority: 1. Do other homework: needs 100 cycles  
 Priority: 2. Eat dinner: needs 30 cycles

---- EXECUTING HIGHEST PRIORITY TASK ------   
 ...Running Eat dinner for 30 cycles.  
 ...Eat dinner was in the system for 640 cycles.  
 ...Clock is now 640 cycles.  
 ---- TASK COMPLETED ------

Task Queue Contents:   
 Priority: 1. Do other homework: needs 100 cycles

---- EXECUTING HIGHEST PRIORITY TASK ------   
 ...Running Do other homework for 100 cycles.  
 ...Do other homework was in the system for 740 cycles
 ...Clock is now 740 cycles.  
 ---- TASK COMPLETED ------

Task Queue Contents:

---- EXECUTING HIGHEST PRIORITY TASK ------   
 javafoundations.exceptions.EmptyCollectionException: No more tasks left to run.