Question

Write a Java program, In this project, you are going to build a max-heap using array representation. In particular, your program should:

• Implement two methods of building a max-heap.

o Using sequential insertions (its time complexity: ?(?????), by successively applying the regular add method).
o Using the optimal method (its time complexity: ?(?), the “smart” way we learned in class).
For both methods, your implementations need to keep track of how many swaps (swapping parent and child) are required to build a heap.

• Implement the remove method of a max-heap.
• Read a sequence of integers from an input file.
o “data.txt”: This file contains 100 integers (no duplicates, and positive numbers). Each line is an integer.
• Perform heap operations and Write the results into an output file.
o Create a max-heap using the sequential insertions, for those 100 integers.
o Output the first 10 integers of your array, into the output file
o Output the number of swaps performed, into the output file
o Perform 10 removals on the heap
o Output the first 10 integers of the resulting array, into the output file
o Create a max-heap using the optimal method, for those 100 integers
o Output the first 10 integers of your array, into the output file
o Output the number of swaps performed, into the output file
o Perform 10 removals on the heap
o Output the first 10 integers in the resulting array, into the output file
The output file should use the format as shown below:

=====================================================================
Heap built using sequential insertions: 100,94,99,77,93,98,61,68,76,84,...
Number of swaps in the heap creation: 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 in the heap creation: 96
Heap after 10 removals: 90,89,63,79,88,55,62,71,78,87,...
=====================================================================
Please note that the numbers in the above format are not the actual figures. It is just an example.
This project will be graded based on the quality of your program. Java interface and generic data types are NOT required in this project, but bonus points will be considered for those who use Java interface and generic data type.

1. Source codes

2. Input file (just the given “data.txt”)

3. Output file

data.txt:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

Answer 1

Heap.java:

import java.io.File;
import java.io.FileWriter;
import java.io.IOException;

public class Heap {
    private int size;
    private int[] arr;
    public Heap(){

    }
    //buidHeap method that works in O(n) time
    public void buildHeap(int[] ar){
        this.size = ar.length;
        this.arr = new int[size];
        for(int i=0;i<ar.length;i++)
            this.arr[i] = ar[i];
        for(int i=(this.arr.length)/2;i>=0;i--){
            this.heapify(i);
        }
    }
    //max-heapify method
    public void heapify(int i){
        int largest = i;
        if(((2*i)+1)<size && this.arr[(2*i)+1]>this.arr[largest])
            largest = ((2*i)+1);
        if(((2*i)+2)<size && this.arr[(2*i)+2]>this.arr[largest])
            largest = ((2*i)+2);
        if(largest != i){
            int temp = this.arr[i];
            this.arr[i] = this.arr[largest];
            this.arr[largest] = temp;
            this.heapify(largest);
        }
    }
    public void insert(int num){

    }
    //method to remove max element from max-heap
    public int remove(){
        if(this.size<1)
            return -1;
        int temp = this.arr[0];
        this.arr[0] = this.arr[size-1];
        this.arr[size-1] = temp;
        size--;
        return this.arr[size];
    }
    //method to print elements of max heap in output file
    public void printHeap(String filename){
        try {
            File file = new File(filename);
            FileWriter writer = new FileWriter(file);
            for (int i = 0; i < this.arr.length; i++)
                writer.write(this.arr[i] + "\n");
            writer.close();
        }catch (IOException e){
            System.out.println("Error while writing");
        }
    }
}

Main.java:

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class main {
    public static void main(String[] args) {
        try {
            ArrayList<Integer> readArray = new ArrayList<Integer>();
            File file = new File("input.txt");
            Scanner reader = new Scanner(file);
            while (reader.hasNextInt()) {
                readArray.add(reader.nextInt());
            }
            int[] arr = new int[readArray.size()];
            for (int i = 0; i < readArray.size(); i++)
                arr[i] = readArray.get(i);
            Heap h = new Heap();
            h.buildHeap(arr);
            h.printHeap("output.txt");
        }catch (IOException e){
            System.out.println("Error while reading");
        }
    }
}

INPUT FILE "input.txt":

main.java X 6 output.txt x 4 input.txt X Heap.java X 1 5 2 1 3 2 4 3 5 6 6 4 7 6 8 3 9 8 9 10 11 6

OUTPUT FILE "output.txt":

& output.txt x 6 input.txt x Heap.java X 1 2 3 main.java X 9 8 6 5 6 4 4 5 6 7 2 3 8 9 3 10 1 6 11