Write a Java program to implement priority queue using min-heap as we discussed
ID: 3726876 • Letter: W
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 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());
}
}
}
Explanation / Answer
/*
Error in your is only is that you have not initilaise the value of howMany variable in your program
as I have added that line as
public minHeap(int number) {
myArray = new int[number];
//only this line is added
howMany = number;
size = 0;
}
or you can do this also as
public minHeap(int howMany) {
myArray = new int[howMany];
//add this line
this.howMany=howMany;
this.size = 0;
}
After that I change your main function as that is not in according to what is given in the question in the starting
***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;
}
I made it like that
And handled the case of removing when no element is present in queue as showing the queue empty
previous code come with the question is of adding 30 elements and then removing 30 elements;
*/
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];
this.howMany = howMany;
this.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 Point {
public static void main(String[] args) {
minHeap hp = new minHeap(31);
int i = hp.size;
Random r = new Random();
while (i < hp.howMany - 1) {
//previous code come with the question is of adding 30 elements and then removing 30 elements;
// int num =(int)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());
// }
int ch = r.nextInt(2);
//add element
if(ch==0){
int num =(int)r.nextInt(100)+1;
hp.add(num);
System.out.println((i+1)+ " Add " + num + ": ");
System.out.println(hp.toString());
}else{
//remove element
if(hp.size!=0)
System.out.println((i+1)+ " Remove : " + hp.remove());
else
System.out.println((i+1)+ " Remove : ");
System.out.println(hp.toString());
}
i++;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.