Assignment

Objectives


  1. Understand the structure of a binary heap.
    2. Be able to analyze the complexities of an algorithm through experiments.

Overview
Develop an interactive software of max-heap creation.

Project Description
The software can build a max-heap from at least100 numbers. Users can test the software by usingtwo different sets of 100 numbers.
Functional Requirements
1. The software can build a max-heap in two ways:
a. use sequential insertions (Lecture 6 slide 23)
b. use the optimal method (Lecture 6 slide 24).
2. The software must be able to allow users to test the software by the following 2 choices:
a. Test 1: Use 20 sets of 100 randomly generated integers to build 20 max-heaps. Inthis test, the software should inform the user the average swaps needed for buildingthese max-heaps.
b. Test 2: use 100 fixed values from 1, 2, 3, …, and 100.
3. The software must print on screen and in the output.txt the following results:
a. Test 1:
i. The average number of swaps needed to build the max-heaps, for the bothmethods mentioned in 1.
b. Test 2: for each method mentioned in 1,
i. The first 10 integers in your array;
ii. The number of swaps for both methods mentioned in 1.
iii. Then perform 10 removals on the heap and output the first 10 integers.

Engineering Requirements
1. The software must be implemented in Java language.
2. The software must be written from scratch and use minimum Java library. Use excessive
Java library will impact the points of this project you will get.
3. Use an array to implement the max-heap.
4. All numbers used to build max-heap are positive integers with proper range.
5. For Test 1, the software will generate 20 sets of randomly generated numbers.

Non-Functional Requirements
None.

Scope
1. No duplicate numbers are allowed in the binary search tree.
2. Use the command line for user to provide information the software required.

Expected Results
Below is the content and the format expected for both output file and screen display.
=====================================================================
Please select how to test the program:
(1) 20 sets of 100 randomly generated integers
(2) Fixed integer values 1-100
Enter choice: 1
Average swaps for series of insertions: 107
Average swaps for optimal method: 87
=====================================================================
Please select how to test the program:
(1) 20 sets of 100 randomly generated integers
(2) Fixed integer values 1-100
Enter choice: 2
Heap built using series of insertions: 100,94,99,77,93,98,61,68,76,84,…
Number of swaps: 480
Heap after 10 removals: 90,89,62,77,88,53,61,68,76,84,…
Heap built using optimal method: 100,95,99,79,94,98,63,71,78,87,…
Number of swaps: 96
Heap after 10 removals: 90,89,63,79,88,55,62,71,78,87,… 

Solution 

Heap.java 

// Represents a heap

public class Heap {

privateint[] heap; //array to store heao

privateint count; // number of elements in heap

privateint swaps; // number of swaps to build heap

// build heap using repeated additions

public void buildHeapRepeatAdd(int[] data) {

swaps = 0;

count = 0;

// create heap

heap = new int[data.length + 1];

// add repeatedly

for (int i = 0; i <data.length; i++) {

addToHeap(data[i]);

}

}

// build heap using optimal method

public void buildOptimal(int[] data) {

swaps = 0;

count = 0;

//create heap

heap = new int[data.length + 1];

//add element as it is

for (int i = 0; i <data.length; i++) {

heap[++count] = data[i];

}

// reaheap non leaf nodes

for (int i = count / 2; i > 0; i–) {

reheap(i);

}

}

// add an element to heap

private void addToHeap(int key) {

heap[++count] = key; //add to end of heap

siftUp(count); // shift up

}

// removes the root node of heap

publicintremoveMax(){

// if no elements

if(count == 0)

return -1;

// remove

int removed = heap[1];

// copy last element to root

heap[1] = heap[count];

count–;

reheap(1); //reheap

return removed;

}

// method to reheapigy a node

private void reheap(int i) {

int left = 2 * i;

int right = 2 * i + 1;

int largest = i;

if(left <= count && heap[left] > heap[largest]) {

largest = left;

}

if(right <= count && heap[right] > heap[largest]) {

largest = right;

}

if(largest != i) {

swap(i, largest);

reheap(largest);

}

}

// method to move the element at i to correct position in heap

private void siftUp(int i) {

int parent = i / 2;

while (parent > 0 && heap[parent] < heap[i]) {

swap(parent, i);

i = parent;

parent = parent / 2;

}

}

// swap two elements in heap

private void swap(int i, int j) {

int temp = heap[i];

heap[i] = heap[j];

heap[j] = temp;

swaps++;

}

// returns total numbers of swaps

publicintgetSwaps() {

returnthis.swaps;

}

// returns first len element in the heap

public String toString(intlen) {

String out = “”;

for (int i = 1; i <= len; i++) {

out += heap[i] + “,”;

}

return out+”…”;

}

} 

Project1.java

importjava.io.FileNotFoundException;

importjava.io.PrintWriter;

importjava.util.Random;

importjava.util.Scanner;

public class Project1 {

public static void main(String[] args) throws FileNotFoundException {

PrintWriter pw = new PrintWriter(“output.txt”); // to write to file

// to read from user

Scanner scanner = new Scanner(System.in);

boolean exit = false;

while (!exit) {

// print menu      System.out.println(“=====================================================================”);

System.out.println(“Please select how to test the program:”);

System.out.println(“(1) 20 sets of 100 randomly generated integers”);

System.out.println(“(2) Fixed integer values 1-100”);

System.out.println(“(3) Exit”);

System.out.print(“Enter choice: “);

int choice = scanner.nextInt();

if (choice == 1) {

// create 20 data sets

int[][] data = new int[20][];

for (int i = 0; i <data.length; i++) {

data[i] = generateData(100, true);

}

// build heaps and counts

intswapsSeries = 0, swapsOptimal = 0;

Heap heap = new Heap();

for (int i = 0; i <data.length; i++) {

heap.buildHeapRepeatAdd(data[i]);

swapsSeries += heap.getSwaps();

heap.buildOptimal(data[i]);

swapsOptimal += heap.getSwaps();

}

// print average

println(pw, “\nAverage swaps for series of insertions: ” + swapsSeries / 20);

println(pw, “Average swaps for optimal method: ” + swapsOptimal / 20);

}

else if (choice == 2) {

// generate data unshuffled

int[] data = generateData(100, false);

Heap heap = new Heap();

// build using repeated additions

heap.buildHeapRepeatAdd(data);

println(pw, “\nHeap built using series of insertions: ” + heap.toString(10));

println(pw, “Number of swaps: ” + heap.getSwaps());

// remove root 10 times

for (int i = 0; i < 10; i++) {

heap.removeMax();

}

println(pw, “Heap after 10 removals: “+heap.toString(10));

// repeat same using optimal method

heap.buildOptimal(data);

println(pw, “\nHeap built using optimal method: ” + heap.toString(10));

println(pw, “Number of swaps: ” + heap.getSwaps());

for (int i = 0; i < 10; i++) {

heap.removeMax();

}

println(pw,”Heap after 10 removals: “+heap.toString(10));

}

else if (choice == 3) { //exit

exit = true;

pw.close();

scanner.close();

System.out.println(“Thank you!”);

}

}

}

//generates data

// shuffle if indicator is true

public static int[] generateData(int size, boolean shuffle) {

// generate data 1 to size

int[] data = new int[size];

for (int i = 0; i <data.length; i++) {

data[i] = i + 1;

}

// shuffle

if (shuffle) {

Random random = new Random();

for (int i = 0; i <data.length; i++) {

int j = random.nextInt(size);

if (i != j) {

int temp = data[i];

data[i] = data[j];

data[j] = temp;

}

}

}

return data;

}

// print to output oisole and file

public static void println(PrintWriter pw, String out) {

pw.println(out);

System.out.println(out);

}

}