I am writing a program that will take positive integers as inputs from the user, save it into an arrayList , insert them into a min heap and then will print the heap. I have been able to take in input from the user, save it into an arrayList, but while debugging I realized that my call to the insertion method isn't really working, i.e., it isn't really creating the heap. I do not really know what I am doing wrong. Previously I used the similar code to create a min heap in a non-object oriented java program, so I wonder I have to modify any of the methods or anything like that since I am using multiple classes now. My code for the main class:
public class LabHeapSort {
//main method will only call user interface
public static void main(String[] arg){
UserInterface userInterface = new UserInterface();
userInterface.PrintMenu();
}
}
My code for the HeapSort class:
public class HeapSort {
//UserInterface userInterface = new UserInterface();
//Java Implementation of Min Heap
public int[] MinHeap;
public int size;
private int maxSize;
private static final int HEAD = 1;
public HeapSort(int maxSize){
this.maxSize = maxSize;
this.size = 0;
MinHeap = new int[this.maxSize 1];
MinHeap[0] = Integer.MIN_VALUE;
}
//Function to return the position of the parent
//for the node currently at pos
private int parent(int pos){
return pos/2;
}
//Function to return the position of the left Child
//for the node currently at pos
private int leftChild(int pos){
return (2 * pos);
}
//Function to return the position of the right Child
//for the node currently at pos
private int rightChild(int pos){
return (2 * pos) 1;
}
//function that returns true if the passed node is a leaf node
private boolean isLeaf(int pos){
if (pos >= (size / 2) && pos <= size ){
return true;
}
return false;
}
//function to swap two nodes of the Heap
private void swap(int fpos, int spos){
int tmp;
tmp = MinHeap[fpos];
MinHeap[fpos] = MinHeap[spos];
MinHeap[spos] = tmp;
}
//funtion to heapify node at pos
private void minHeapify(int pos){
//if the leaf is a non-leaf node and greater
//than any of its child
if(!isLeaf(pos)){
if (MinHeap[pos] > MinHeap[leftChild(pos)]
|| MinHeap[pos] > MinHeap[rightChild(pos)]){
//swap with the left child and heapify
//the left child
if (MinHeap[leftChild(pos)] < MinHeap[rightChild(pos)]){
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}
//swap with the right child and heapify
//the right child
else{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
public void insert(int element){
if (size >= maxSize){
return;
}
MinHeap[ size] = element;
int current = size;
while (MinHeap[current] < MinHeap[parent(current)]){
swap(current, parent(current));
current = parent(current);
}
}
public void minHeap(){
for (int pos = (size / 2); pos >= 1; pos--){
minHeapify(pos);
}
}
//funtion to remove and return the minimum element from the heap
public int remove(){
int popped = MinHeap[HEAD];
MinHeap[HEAD] = MinHeap[size--];
minHeapify(HEAD);
return popped;
}
public int findMin(){
return MinHeap[HEAD];
}
//funtion to print the contents of the heap
public void print(){
for (int i = 1; i <= size /2 ; i ){
System.out.print(" PARENT : " MinHeap[i]
" LEFT CHILD : " MinHeap[2*i]
" RIGHT CHILD : " MinHeap[2*i 1]);
System.out.println();
}
}
}
My code for UserInterface class:
import java.util.ArrayList;
import java.util.Scanner;
public class UserInterface {
ArrayList<Integer> numbers = new ArrayList<Integer>();
HeapSort min_heap = new HeapSort((numbers.size() 1));
public UserInterface() {
}
public void PrintMenu(){
Scanner input = new Scanner (System.in);
int option = 0;
while(option != 2){
System.out.println("");
System.out.println("Menu Please enter an option given bellow: ");
System.out.println("Option Operation Completed");
System.out.println("--------------------------------");
System.out.println("1 Insert into heap and sort");
System.out.println("2 Exit");
option = input.nextInt();
switch(option){
case 1:
//add code for Insert into heap and sort
userInput();
printUserInput();
//insert all elements from the userInput arrayList into the heap
for (int i = 0; i < numbers.size(); i ){
min_heap.insert(numbers.get(i));
}
//print the min_heap
min_heap.print();
break;
case 2:
//add code for Quit
System.out.println("Thank you for using our program.");
System.exit(0);
break;
//Error message if user inputs anything other than 1-2
default:
System.out.println(option " is not a correct choice.\n"
"please enter another option. \n");
break;
}
}
}
//userInput method takes input from the user
//the input is numbers for heap-sorting
//then userInput saves all the numbers in an arraylist
public void userInput(){
Scanner input = new Scanner (System.in);
//store them in an array or array list
//let user enter -1 to end their list of values
System.out.println("Enter the integers you want to save for heap sorting.");
System.out.println("POSITIVE NUMBERS ONLY. You can not input negative numbers.");
System.out.println("Enter -1 to quit.");
while(true){
int number = input.nextInt();
if(number >= 0)
numbers.add(number);
else if (number == -1){
System.out.println("All your numbers have been saved for sorting.");
break;
}
else if (number < -1){
System.out.println("You can input positive numbers only.");
System.out.println("Please enter a positive integer: ");
number = input.nextInt();
if(number >= 0)
numbers.add(number);
else if (number == -1){
System.out.println("All your numbers have been saved for sorting.");
break;
}
}
}
}
public void printUserInput(){
System.out.println();
System.out.println("***************************");
System.out.print("Original Input: ");
for (int i = 0; i<numbers.size(); i ){
System.out.print(numbers.get(i) " ") ;
}
System.out.println("\n ");
}
}
CodePudding user response：
the constructor of a class should have the same name as the class HeapSort.
change HeapSort_Manita => HeapSort
CodePudding user response：
The problem is with the min_heap variable. It is initialised at a moment when the class is loaded and the numbers array is still empty:
HeapSort min_heap = new HeapSort((numbers.size() 1));
This means it has no capacity to insert the numbers that the user will later enter.
You should move this declaration (or at least the initialisation) to the part where the numbers array has already been loaded:
userInput();
printUserInput();
HeapSort min_heap = new HeapSort((numbers.size() 1)); // <---
for (int i = 0; i < numbers.size(); i ){
min_heap.insert(numbers.get(i));
}