Question: ***********IN JAVA***************** The given Heap class in this problem ( MaxHeap ) is also known as a max-heap, in which each node is greater than
***********IN JAVA*****************
The given Heap class in this problem (MaxHeap) is also known as a max-heap, in which each node is greater than or equal to any of its children. A min-heap is a Heap in which each node is less than or equal to any of its children. Revise the following Heap class to implement a min-heap (MinHeap). Min-heaps are often used to implement priority queues.
**************************************
The main and MaxHeap are given and need no change.
**************************************
import java.util.*;
import java.lang.*;
import java.io.*;
class MaxHeap
private java.util.ArrayList
/** Create a default heap */
public MaxHeap() {
}
/** Create a heap from an array of objects */
public MaxHeap(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
/** Add a new object into the heap */
public void add(E newObject) {
list.add(newObject); // Append to the heap
int currentIndex = list.size() - 1; // The index of the last node
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2;
// Swap if the current object is greater than its parent
if (list.get(currentIndex).compareTo(
list.get(parentIndex)) > 0) {
E temp = list.get(currentIndex);
list.set(currentIndex, list.get(parentIndex));
list.set(parentIndex, temp);
}
else
break; // the tree is a heap now
currentIndex = parentIndex;
}
}
/** Remove the root from the heap */
public E remove() {
if (list.size() == 0) return null;
E removedObject = list.get(0);
list.set(0, list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while (currentIndex < list.size()) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
// Find the maximum between two children
if (leftChildIndex >= list.size()) break; // The tree is a heap
int maxIndex = leftChildIndex;
if (rightChildIndex < list.size()) {
if (list.get(maxIndex).compareTo(
list.get(rightChildIndex)) < 0) {
maxIndex = rightChildIndex;
}
}
// Swap if the current node is less than the maximum
if (list.get(currentIndex).compareTo(
list.get(maxIndex)) < 0) {
E temp = list.get(maxIndex);
list.set(maxIndex, list.get(currentIndex));
list.set(currentIndex, temp);
currentIndex = maxIndex;
}
else
break; // The tree is a heap
}
return removedObject;
}
/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
}
class DriverMain{
public static void main(String args[]){
MinHeap minHeap = new MinHeap();
Scanner input = new Scanner(System.in);
String str = input.nextLine();
input.close();
int[] list = Arrays.stream(str.substring(0, str.length()).split("\\s"))
.map(String::trim).mapToInt(Integer::parseInt).toArray();
// Add elements to the min heap
for (int i = 0; i < list.length; i++)
minHeap.add(list[i]);
// Remove elements from the min heap
for (int i = 0; i < list.length; i++)
System.out.print(minHeap.remove() +" ");
}
}
******************************************************
Here's where to edit the code.
*****************************************************
public class MinHeap
private java.util.ArrayList
/** Create a default heap */
public MinHeap() {
}
/** Create a heap from an array of objects */
public MinHeap(E[] objects) {
for (int i = 0; i < objects.length; i++)
add(objects[i]);
}
/** Add a new object into the heap */
public void add(E newObject) {
//write your code here
}
/** Remove the root from the heap */
public E remove() {
//write your code here
}
/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
************************************
Any help is appreciated along with comments!
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help