Write a Java program to implement priority queue using min-heap as we discussed
ID: 3845426 • Letter: W
Question
Write a Java program to implement priority queue using min-heap as we discussed in class.
Heap size: 30 nodes with random-generated number between 1`100.
Show the state of the min-heap tree using an array after adding each node.
Show the state of the min-heap tree after removing each node.
Sample Log:
Add 30: [30]
Add 81: [30, 81]
Add 28: [28, 81, 30]
Add 25: [25, 28, 30, 81]
Add 86: [25, 28, 30, 81, 86]
Add 97: [25, 28, 30, 81, 86, 97]
Add 29: [25, 28, 29, 81, 86, 97, 30]
.
.Add 3: [2, 8, 3, 25, 12, 18, 15, 29, 41, 28, 25, 29, 72, 76, 21, 81, 95, 55, 44, 86, 41, 39, 92, 97, 55, 96, 84, 88, 80, 30]
Remove 2: [3, 8, 15, 25, 12, 18, 21, 29, 41, 28, 25, 29, 72, 76, 30, 81, 95, 55, 44, 86, 41, 39, 92, 97, 55, 96, 84, 88, 80] size: 29
Remove 3: [8, 12, 15, 25, 25, 18, 21, 29, 41, 28, 39, 29, 72, 76, 30, 81, 95, 55, 44, 86, 41, 80, 92, 97, 55, 96, 84, 88] size: 28
Remove 8: [12, 25, 15, 29, 25, 18, 21, 81, 41, 28, 39, 29, 72, 76, 30, 88, 95, 55, 44, 86, 41, 80, 92, 97, 55, 96, 84] size: 27
.
.
Remove 88: [92, 95, 97, 96] size: 4
Remove 92: [95, 96, 97] size: 3
Remove 95: [96, 97] size: 2
Remove 96: [97] size: 1
Remove 97: [] size: 0
BASE CODE:
import java.util.*;
public class HeapT {
public int size;
private int[] myArray;
public int howMany;
private int parent(int index) {
return index / 2;
}
private int leftChild(int index) {
return index * 2;
}
private int rightChild(int index) {
return index * 2 + 1;
}
private boolean hasParent(int index) {
return index > 1;
}
private boolean hasLeftchild(int index) {
return leftChild(index) <= size;
}
private boolean hasRightChild(int index) {
return rightChild(index) <= size;
}
private void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
public int size() {
return size;
}
public void add(int value) {
}
public int remove() {
}
public boolean isEmpty() {
return size == 0;
}
public String toString() {
return Arrays.toString(myArray);
}
}
Main Class:
import java.util.*;
public class HeapMain {
public static void main(String[] args) {
HeapT h = new HeapT();
Random r = new Random();
int i = h.size;
while (i < h.howMany - 1) {
int num = r.nextInt(100 + 1);
h.add(num);
System.out.print("Add " + num + ": ");
System.out.println(h);
i++;
}
System.out.println();
while (!h.isEmpty()) {
System.out.println("Min: " + h.remove());
System.out.println(h + "size: " + h.size);
}
}
}
Explanation / Answer
Main Class:
import java.util.*;
public class HeapMain {
public static void main(String[] args) {
HeapT h = new HeapT();
Random r = new Random();
int i = h.size;
while (i < h.howMany) {
int num = r.nextInt(100 + 1);
h.add(num);
System.out.print("Add " + num + ": ");
System.out.println(h);
i++;
}
System.out.println();
while (!h.isEmpty()) {
System.out.println("Min: " + h.remove());
System.out.println(h + "size: " + h.size);
}
}
}
Heap Class:
import java.util.*;
public class HeapT {
public int size;
private int[] myArray;
public int howMany;
private int parent(int index) {
return index / 2;
}
private int leftChild(int index) {
return index * 2;
}
private int rightChild(int index) {
return index * 2 + 1;
}
private boolean hasParent(int index) {
return index > 1;
}
private boolean hasLeftchild(int index) {
return leftChild(index) <= size;
}
private boolean hasRightChild(int index) {
return rightChild(index) <= size;
}
private void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
public int size() {
return size;
}
public void add(int value) {
myArray[++size] = value;
int temp_index = size;
while(hasParent(temp_index) && value<myArray[parent(temp_index)]){
swap(myArray,temp_index,parent(temp_index));
temp_index = parent(temp_index);
}
}
public int remove() {
if(isEmpty()){
return -1;
}
int return_value = myArray[1];
swap(myArray,1,size);
size--;
int last_value = myArray[1];
int temp_index = 1;
while(true){
if(hasLeftchild(temp_index) && last_value>myArray[leftChild(temp_index)]){
swap(myArray,temp_index,leftChild(temp_index));
temp_index = leftChild(temp_index);
continue;
}
if(hasRightChild(temp_index) && last_value>myArray[rightChild(temp_index)]){
swap(myArray,temp_index,rightChild(temp_index));
temp_index = rightChild(temp_index);
continue;
}
break;
}
return return_value;
}
public boolean isEmpty() {
return size == 0;
}
public String toString() {
if(size==0){
return "[]";
}
String ret = "[";
for (int i=1;i<=size-1 ;i++) {
ret = ret + Integer.toString(myArray[i]) + ", ";
}
ret = ret + Integer.toString(myArray[size])+"]";
return ret;
}
public HeapT(){
howMany = 30;
size = 0;
myArray = new int[howMany+1];
}
}
Running the Code:
1)Create file HeapMain.java and put Main Class code in it
2) Create file HeapT.java and put Heap Class code in it
3) To compile, enter 'javac HeapMain.java' command in current directory where files are stored
4) To execute, enter 'java HeapMain' command in current directory where files are stored
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.