Question
Write a Java program to implement priority queue using min-heap as we discussed in the class. You have to implement a tree by yourself. (Do
Write a Java program to implement priority queue using min-heap as we discussed in the class. You have to implement a tree by yourself. (Do not use any Java predefined class).
***Main method****
For (int node =1; node<=30; node++){ get a random number [0,1]; if number is 0 { Generate a Random number (1~100); add the number into your heap tree; Modify the heap tree if needed; Print out current heap tree; }
if ( number is 1 && tree != empty) { remove min from the heap tree Modify the heap tree. Print out current heap tree; }
[Sample Output]
1 Add 78: [78] 2 Add 54: [54, 78] 3 Remove 54: [78] 4 Add 39: [39, 78] 5 Remove 39: [78] 6 Remove 78: [ ] 7 Add 94: [94]
30 Add [6]: [6, 13, 8, 29, 26, 27, 24, 54, 36, 70, 39, 54, 45, 62, 31]
-----I wrote some code but it has some error ------
import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Random;
class minHeap {
public int size;
public int howMany;
public int[] myArray;
public minHeap(int howMany) {
myArray = new int[howMany];
size = 0;
}
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 index * 2 <= size;
}
private boolean hasRightChild(int index) {
return index * 2 + 1 <= 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 + 1] = value; // add as rightmost leaf
// "bubble up" as necessary to fix ordering
int index = size + 1;
boolean found = false;
while (!found && hasParent(index)) {
int parentIndex = parent(index);
if (myArray[index] < myArray[parentIndex]) {
swap(myArray, index, parentIndex);
index = parent(index);
} else {
found = true; // found proper location; stop
}
}
size++;
}
private int peek() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return myArray[1];
}
public int remove() {
int result = peek(); // last leaf -> root
myArray[1] = myArray[size];
size--;
int index = 1; // "bubble down" to fix ordering
boolean found = false;
while (!found && hasLeftChild(index)) {
int leftChild = leftChild(index);
int rightChild = rightChild(index);
int child = leftChild;
if (hasRightChild(index) && myArray[rightChild] < myArray[leftChild]) {
child = rightChild;
}
if (myArray[index] > myArray[child]) {
swap(myArray, index, child);
index = child;
} else {
found = true; // found proper location; stop
}
}
return result;
}
public boolean isEmpty() {
return size == 0;
}
public String toString() {
int[] temp = new int[size];
for (int i = 0; i < size; i++) {
temp[i] = myArray[i + 1];
}
return Arrays.toString(temp);
}
}
public class Assignment7 {
public static void main(String[] args) {
minHeap hp = new minHeap(31);
Random r = new Random();
int i = hp.size;
while (i < hp.howMany - 1) {
int num = r.nextInt(100) + 1;
hp.add(num);
System.out.println("Add " + num + ": ");
System.out.println(hp.toString());
i++;
}
System.out.println();
while (!hp.isEmpty()) {
System.out.println("Remove : " + hp.remove());
System.out.println(hp.toString());
}
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started