Write a Java program to implement priority queue using min-heap as we discussed
ID: 3845146 • 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);
}
}
Explanation / Answer
Hello ,
Below is the code :
import java.util.*;
public class HeapT {
public int size;
private int[] myArray;
public int howMany;
private static final int FRONT = 1;
Integer random1 = generator.nextInt(100);
MinHeap heap = new minHeap();
for(int i = 0; i < 30; i++)
{
mh.add((Comparable) random1);
}
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;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public String toString() {
return Arrays.toString(myArray);
}
}
private void heapifyUp(int childInd)
{
int tmp = heap[childIndex];
while (childIndex > 0 && tmp < heap[parent(childIndex)])
{
heap[childIndex] = heap[ parent(childIndex) ];
childIndex = parent(childIndex);
}
heap[childIndex] = tmp;
}
public void add(int x)
{
heap[heapSize++] = x;
heapifyUp(heapSize - 1);
for (int i = 1; i <= size / 2; i++ ){
System.out.println(heap[i]);
}
System.out.println("The size:"+size);
}
public int remove(int del)
{
for (int i = 1; i <= size / 2; i++ ){
if(del==heap[i]){
int ind= i;
break;
}
}
int keyItem = heap[ind];
heap[ind] = heap[heapSize - 1];
heapSize--;
heapifyDown(ind);
return keyItem;
for (int i = 1; i <= size / 2; i++ ){
System.out.println(heap[i]);
}
System.out.println("The size:"+size);
}
private void heapifyDown(int ind)
{
int child;
int tmp = heap[ ind ];
while (kthChild(ind, 1) < heapSize)
{
child = minChild(ind);
if (heap[child] < tmp)
heap[ind] = heap[child];
else
break;
ind = child;
}
heap[ind] = tmp;
}
public static void main(String...arg)
{
heap.add(3);
heap.remove(3);
}
}
Thanks
PS: Ignore minor syntax errors. Understand the flow and if you have any doubts comment back i will revert ASAP.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.