Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

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

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

XML Data Management Native XML And XML Enabled Database Systems

Authors: Akmal Chaudhri, Awais Rashid, Roberto Zicari, John Fuller

1st Edition

ISBN: 0201844524, 978-0201844528

More Books

Students also viewed these Databases questions