INFORMATION & COMPUTER SCIENCE DEPARTMENT, KFUPM

ICS 202: DATA STRUCTURES

LAB#07 Binary Heaps

# Objectives:

1. Understanding the implementation and use of Minimum- and Maximum-BinaryHeaps.

2. Testing whether a given array is a min-heap or not.

3. Implementing heap-sort.

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

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

·      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)

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

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

(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