Objectives:

Understanding the implementation and use of Minimum- and Maximum-BinaryHeaps.
Testing whether a given array is a min-heap or not.
Implementing heap-sort.

1. Downloadables:

Download the file lab07.zip and unzip it in the ics202 main folder.

After unzipping, the following files will be added to the ics202 package:

PriorityQueue.java

PriorityQueue2.java

BinaryHeap.java

The following files will be placed in a package ics202.lab07:

BinaryHeapTest.java

BinaryHeap2Test.java

2. Task1

Study each of the files: PriorityQueue.java, PriorityQueue2.java, BinaryHeap.java, and make sure you understand each of them.

3. Task2

· Complete the test program BinaryHeapTest.java as indicated in the comments in the file.

· Note: Verify the correctness of your program by drawing:

(a) The heap tree that results in building a min-heap, top-down , using the following 8 element sequence:

7, 1, 2, -3, 5, 0, 5, 2

(b) The heap tree that results in dequeing one element from the tree in (a)

20, 5, 4, 3, 2, 2, 5, 6, 8, 1, 10

4. Task3

(a) Copy BinaryHeap.java as BinaryHeap2.java in the ics202 package. Let BinaryHeap2 implement the PriorityQueue2 interface and then make other modifications such that BinaryHeap2.java becomes a class for creating Maximum-Heap objects.

(b) Complete the test program BinaryHeap2Test.java as indicated in the comments in the file.

Note: Verify the correctness of your programs by drawing:

(i) The heap tree that results in building a max-heap, top-down , using the following 8 element sequence:

5, 1, 2, -3, 7, 0, 10, 2

(ii) The heap tree that results in dequeing one element from the tree in (i)

(iii) The heap tree that results in building a max-heap, bottom-up ,using the following 11 element array:

5, 8, 4, 3, 2, 2, 9, 6, 20, 1, 10