Question

the assignment folder for this assignment contains a file called values.txt. The first line in the file contains the total number of integers which comes after it. The length of this file will be the first line plus one lines long.

Implement a MinHeap. Your program should read in input from a file, add each value to the MinHeap, then after all items are added, those values are removed from the MinHeap. Create a java class called MinHeap with the package name csci3250.heap. Some parts of this classes is written for you. You need to complete it. Create a java main class (contains the main method) called HeapTest.java to test the min heap. This class also is in the package csci3250.heap

Your program must contain adequate comments including your name in both java classes.

package csci3250.heap;

import java.util.Vector;

public class MinHeap {

    private Vector mVector;

    /**

     * heapifies one subtree (It ensures that a parent is smaller than its

     * children and will be recursively called on the smallest child if

     * necessary.)

     *

     * @param index

     */

    private int heapifyNode(int nodeIndex) {       

    }

    // swaps two positions in mVector

    private void swap(int firstNodeIndex, int secondNodeIndex) {              

    }

    // Empty default constructor

    public MinHeap() {       

    }

    // Inserts, always maintaining a heap

    public void insert(int value) {    

    }

    // Removes the top element

    public int remove() {

    }

    // Returns true if heap is empty

    public boolean isEmpty() {

    }

    // Returns the top element at 0

    public int peek() {

    }

}

The vector is used to store the heap. In the main method of HeapTest.java you may need to use the following code to read the file. Complete the code (Keep in mind this piece of code must be in the method main)

File file = new File("src/main/java/csci3250/heap/nums.txt");

            try {

                Scanner inputStream = new Scanner(file);

             //complete the code

            } catch (FileNotFoundException ex) {

                System.out.println("File not found");

                System.exit(0);

            }

Your program should take the following steps.

1. Prompt for read from file or read numbers from input.
2. If the user chooses to read from the file read from the file nums.txt and go to step 4
3. If the user chooses to enter numbers, prompt for a number of elements and go to step 4
4. Read all of the elements into the heap using the insert call.
5. Print the heap elements by removing each element one at a time.

Output

A sample output of the program is shown here.

How do you wish to insert into the heap? [R]ead from the nums.txt file or [I]nsert numbers? I

How many values do you wish to insert? 5

1: 3

2: 2

3: 6

4: 1

5: 9

Printing Heap

1

2

3

6

9

100000
49269
7139
6037
58922
32000
5234
2969
80843
24300
68862
75009
94960
90811
93247
77301
17633
89072
54112
98223
50535
62235
49773
64606
11393
40067
14873

This is the code that I have but I dont know how to translate it java and to the fix the mistakes please

#pragma once

#include
#include

using namespace std;

struct PriorityQueue

{

private:

vector A;

int PARENT(int i)

{

return (i - 1) / 2;

}

int LEFT(int i)
{
return (2 * i + 1);
}

int RIGHT(int i)
{
return (2 * i + 2);
}

void heapify_down(int i)
{

int left = LEFT(i);
int right = RIGHT(i);

int smallest = i;

if (left < size() && A[left] < A[i])
smallest = left;

if (right < size() && A[right] < A[smallest])
smallest = right;

if (smallest != i)
{
swap(A[i], A[smallest]);
heapify_down(smallest);
}
}

void heapify_up(int i)
{
// check if node at index i and its parent violates
// the heap property
if (i && A[PARENT(i)] > A[i])
{
// swap the two if heap property is violated
swap(A[i], A[PARENT(i)]);

// call Heapify-up on the parent
heapify_up(PARENT(i));
}
}

public:

unsigned int size()
{
return A.size();
}

bool empty()
{
return size() == 0;
}

void push(int key)
{
// insert the new element to the end of the vector
A.push_back(key);

// get element index and call heapify-up procedure
int index = size() - 1;
heapify_up(index);
}

// function to remove element with lowest priority (present at root)
void pop()
{
try
{

if (size() == 0)
throw out_of_range("Vector::at() : "
"index is out of range(Heap underflow)");

// replace the root of the heap with the last element
// of the vector
A[0] = A.back();
A.pop_back();

// call heapify-down on root node
heapify_down(0);
}
// catch and print the exception
catch (const out_of_range & oor)
{
cout << "\n" << oor.what();
}
}

int top()
{
try {

if (size() == 0)
throw out_of_range("Vector::at() : "
"index is out of range(Heap underflow)");

return A.at(0); // or return A[0];
}

catch (const out_of_range & oor) {
cout << "\n" << oor.what();
}
}
};

#include
#include

#include "Minheap.h"

int main()
{
PriorityQueue pq;
int arr[10] = { 10,20,30,40,50,60,70,80,90};
  
for (int i = 0; i < 15; i++)//.#i is from the text file values.txt
pq.push(90);

cout << "Size is " << pq.size() << endl;

cout << pq.top() << " "< pq.pop();

cout << pq.top() << " " << endl;
pq.pop();

cout << endl << "Size is " << pq.size() << endl;

cout << pq.top() << " " << endl;
pq.pop();

cout << pq.top() << " " << endl;
pq.pop();

cout << pq.top() << " "< pq.pop();

cout << pq.top() << " "< pq.pop();

cout << endl << std::boolalpha << pq.empty();

pq.top(); // top op empty heap
pq.pop(); // pop op empty heap

return 0;
}

Answer 1

The code is written as it was mentioned in the problem statement, please note that I have written both the classes in a single file and made the main function public, you can make both class public and save it in different files with the same package. For running this snippet of code you need to save a file named "HeapTest.java". I was confused a little regarding the format of file input so for reading from a file, it is assumed that the file consists of only two-line, the first line of the file contains a single number n denoting the size of the min-heap and the second line contains n separated integers. If you need it in any other format you can just mention it in the comment box. A sample of the output of the same has been added.

CODE:

//package csci3250.heap;

import java.util.Vector;
import java.util.*;
import java.io.*;

class MinHeap {    

    private Vector<Integer> mVector;

    /**

     * heapifies one subtree (It ensures that a parent is smaller than its

     * children and will be recursively called on the smallest child if

     * necessary.)

     *

     * @param index

     */


    // swaps two positions in mVector

    private void swap(int firstNodeIndex, int secondNodeIndex) {          
        
        
        Integer temp = mVector.get(firstNodeIndex);            // store the first value in a temp variable
        mVector.setElementAt(mVector.get(secondNodeIndex), firstNodeIndex);   // store the second value at firstNodeIndex and temp value at secondNodeIndex
        mVector.setElementAt(temp, secondNodeIndex);         
 
    }

    // Empty default constructor

    public MinHeap() {  
        mVector = new Vector();

    }
    
    // Empty parametrized constructor
    public MinHeap(int capacity) {  
        mVector = new Vector(capacity);

    }
    
    
    private int PARENT(int i)               // function which returns parent node of given node i
    {
        if (i == 0)                           // if  i is root then there is no parent
            return 0;
 
        return (i - 1) / 2;                   // else return (i-1)/2
    }
 
    private int LEFT(int i)                // function which returns left node of given node i
    {
        return (2 * i + 1);
    }
 
    private int RIGHT(int i)                            // function which returns right  node of given node i
    {
        return (2 * i + 2);
    }
    
    private void heapify_down(int i)           // function for heapify down for min heap
    {
        // get left and right child of node at index i
        int left = LEFT(i);        
        int right = RIGHT(i);
 
        int smallest = i;                  // set the smallest to current node
 
        if (left < size() && mVector.get(left) < mVector.get(i)) {       // get the smallest of left and right node of current node
            smallest = left;
        }
 
        if (right < size() && mVector.get(right) < mVector.get(smallest)) {
            smallest = right;
        }
 
        if (smallest != i)                                      // and if the smallest node changes from before
        {
            
            swap(i, smallest);                                    // then swap the smallest one with the current and recursively call the same function until smallest keep changes
 
            heapify_down(smallest);
        }
    }
 
    private void heapify_up(int i)           // function for heapify up for minheap
    {
     
        if (i > 0 && mVector.get(PARENT(i)) > mVector.get(i))          // if the parent node is greater that current node then swap and recursively call for the same
        {
            
            swap(i, PARENT(i));
 
            heapify_up(PARENT(i));
        }
    }
    
    public int size()           // returns size
    {
        return mVector.size();
    }
 

    // Inserts, always maintaining a heap

    public void insert(int value) {    // function for inserting into min heap
        
        mVector.addElement(value);     // add the element and heapify from the leaf node
         
        int index = size() - 1;
        heapify_up(index);

    }

    // Removes the top element

    public int remove() {      
        
        try {
            // if heap is empty, throw an exception
            if (size() == 0) {
                throw new Exception("Index is out of range (Heap underflow)");
            }
 
            int root = mVector.firstElement();     // get the root element
 
            
            mVector.setElementAt(mVector.lastElement(), 0);   // set the root element by the leaf node 
            mVector.remove(size()-1);                     // decrease the size 
 
            
            heapify_down(0);                // heapify down from the root node

            return root;
        }
        catch (Exception ex) {
            System.out.println(ex);
            return -1;
            
        }

    }

    // Returns true if heap is empty

    public boolean isEmpty() {          
        
        return size()==0;

    }

    // Returns the top element at 0

    public int peek() {
        
        try {

            if (size() == 0) {
                throw new Exception("Index out of range (Heap underflow)");
            }

            return mVector.firstElement();    
        }
        // catch the exception and print it, and return null
        catch (Exception ex) {
            System.out.println(ex);
            return -1;
           
        }

    }

}


public class HeapTest{
        
        public static void main(String[] args) {               // in main function read the values and insert it one by one.
                
                Scanner sc = new Scanner(System.in);
                
                System.out.println("How do you wish to insert into the heap? [R]ead from the nums.txt file or [I]nsert numbers?");
                String choice = sc.nextLine();
                
                if (choice.contentEquals("R")||choice.contentEquals("I")) {
                        
                        
                        if (choice.contentEquals("R")) {
                                File file = new File("src/main/java/csci3250/heap/nums.txt");
                                
                    try {

                        Scanner inputStream = new Scanner(file);

                        int n = Integer.parseInt(inputStream.nextLine());           // for reading from file it is assumed that the file consists only two line, first line of file contains a single number n denoting size of min heap and second line contains n separated integers 
                        int[] arr = new int[n];
                        String[] strArr = inputStream.nextLine().split(" ");
                        for (int i = 0; i < strArr.length; i++) {
                            String num = strArr[i];
                            arr[i] = Integer.parseInt(num);
                         }
                        
                        MinHeap pq = new MinHeap(n);
                                        for(int i =0;i<n;i++) {
                                                pq.insert(arr[i]);
                                        }
                                        
                                        System.out.println("Printing Heap:");
                                        while (pq.size()!=0) {
                                                System.out.println(pq.remove());
                                        }
                        
                        
                        

                    } catch (FileNotFoundException ex) {

                        System.out.println("File not found");

                        System.exit(0);

                    }
                    
                    
                        }
                        
                        
                        else{
                                
                                System.out.println("How many values do you wish to insert? ");
                                int n = sc.nextInt();
                                int[] arr = new int[n];
                                for(int i=0;i<n;i++) {
                                        System.out.print((i+1)+":");
                                        arr[i] = sc.nextInt();
                                        
                                }
                                        
                        
                                
                                MinHeap pq = new MinHeap(n);
                                for(int i =0;i<n;i++) {
                                        pq.insert(arr[i]);
                                }
                                
                                System.out.println("Printing Heap:");
                                while (pq.size()!=0) {
                                        System.out.println(pq.remove());
                                }
                        
                        }
                        
                        
                        
                }
                
                else {
                        System.out.println("Invalid choice");
                }
                
                
                
                
        }
        /*
        */
}

OUTPUT:

How do you wish to insert into the heap? [R]ead from the nums.txt file or [I]nsert numbers?I
How many values do you wish to insert? 5
1:3
2:2
3:6
4:1
5:9
Printing Heap:
1
2
3
6
9

NOTE: In case of any query you can mention it in the comment box. HAPPY LEARNING!!