Priority Queues - University of North Florida



COP 3540 – Data Structures with OOP

Project 5 – Spring 2010

Due: 23 April 2010. Note: No late assignments accepted after this date and time.

Note this is a Friday.

Heaps

Using NetBeans 6.7.1, you are to write a Java program using OOP principles to accommodate the following functionality

Several of the comments in red below are merely clarifications I sent via email.

One comment (in three places) is what to print in the header – simply a text addition.

Two changes:

1. When there are no left and right children, leave those entries blank when

you print out the array. (Don’t have indices where there are no nodes.)

2. For the insertions from region 1, divide by 100 and not 1000. Your algorithm

will give you a better distribution of these insertions and exercise the algorithm

better than merely dividing by 1000 (almost all ended up at the bottom).

Thanks.

Assignment #5

Objectives:

Provide student with exercises in learning UML

Provide student with exercises in Javadoc and its various formats

Provide student with heaps, arrays, and other practical programming exercises

Task 1: Build the Heap. Using the Countries.txt file, you are to build a heap using the capital populations divided by 1000 mod 1000 from countries in region 2. You must process these in the order in which you obtain them from the input file. Do not use your array of objects from previous programming efforts. Rather, obtain the string population from an appropriate record and add it to the tree in order. You may (my preference) create an object with the String or integer value as the instance variable. Alternatively, you may simply convert the Strings to an int and insert them into your heap (array).

Task 1A. Use ArrayList(). My prefernence is for you to use an ArrayList. This will give you practice with a different facility in Java, if you have not already used it. But you may (see emails) simply use a traditional array as your implementing mechanism, if you wish. If you use the ArrayList(), Eeach node is to be an object of type . (Think: ArrayList myRam = new ArrayList(); )

Task 2: Display the Heap. Display the heap in a suitably tagged (headers, etc.) array. Each array entry should have a node number corresponding to its position in the full tree = starting with position 0 through consecutive numbers up to n-1. Be sure to include the node number and the population (the data items in the node) along with the two pointers to its children for each row in the array. When you display your array, do not display left child and right child indices if the node does not have a left or right child. Merely leave those fields empty in your display. Also, your headers might be improved if you cite something like Print Heap after Initial Build.

Task 3: Insert into the Heap. Using the populations in Countries.txt from region 1 into the heap. You are to insert the populations divided by 100 (note this is a divide by 100 not 1000. This will exercise your trickle-up routine more fully. mod 1000 as expected.

Task 4: Display the Heap. Display the heap again. Include in header, Print Heap after Insertions.

Task 5: Delete nodes from the Heap. Delete five nodes from the heap

Task 6: Display the Heap. Display the heap one more time. Include in header: Print Heap after Deletions.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download