INFORMATION & COMPUTER SCIENCE
DEPARTMENT, KFUPM
ICS 202:
DATA STRUCTURES
LAB#07 Binary Heaps
Understanding the implementation and use of Minimum- and Maximum-BinaryHeaps.
Testing whether a given array is a min-heap or not.
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
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)
(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
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