A min-heap is a Heap in which each node is less than or equal to any of its children. Implement add and remove methods for the min-heap (MinHeap) class. Min-heaps are often used to implement priority queues. NOTE: - You need to implement the add and remove methods in the MinHeap class. - The Driver class will call your add and remove method to construct the heap. //First input line is the test method case (1 to add elements to the heap, 2 to remove one element from the heap and 3 to remove all the elements) //Second input line is the number of elements (1 or more) //Third input line is the list of elements Sample input1 (Test add method):
- Write in Java.
*************************************************
A min-heap is a Heap in which each node is less than or equal to any of its children. Implement add and remove methods for the min-heap (MinHeap) class. Min-heaps are often used to implement priority queues.
NOTE:
- You need to implement the add and remove methods in the MinHeap class.
- The Driver class will call your add and remove method to construct the heap.
//First input line is the test method case (1 to add elements to the heap, 2 to remove one element from the heap and 3 to remove all the elements)
//Second input line is the number of elements (1 or more)
//Third input line is the list of elements
Sample input1 (Test add method):
1
4
7 3 8 1
Sample output1
1 3 8 7
Sample input2 (Test remove method):
2
4
7 3 8 1
Sample output2
1
Sample input3 (Test min heap sort):
3
4
7 3 8 1
Sample output3
1 3 7 8
- MinHeap.java:
import java.io.*;
class MinHeap<E extends Comparable<E>> {
private java.util.ArrayList<E> list = new java.util.ArrayList<>();
/** Create a default heap */
public MinHeap() {
}
/** Create a heap from any 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 code here---
}
/** Remove the root from the heap */
public E remove() {
//---Write code here---
}
/** Get the number of nodes in the tree */
public int getSize() {
return list.size();
}
public void print() {
for(int i = 0; i < list.size(); i++)
System.out.print(list.get(i) + " ");
}
}
- MinHeapDriver.java:
import java.util.*;
public class MinHeapDriver {
public static void main(String[] args) {
MinHeap<Integer> minHeap = new MinHeap<Integer>();
Scanner input = new Scanner(System.in);
int which = input.nextInt();
int quantity = input.nextInt();
//Add elements to the min heap
for(int i = 0; i < quantity; i++)
minHeap.add(input.nextInt());
switch (which) {
case 1 : //test add method
minHeap.print();
break;
case 2 : //test remove method
System.out.print(minHeap.remove());
break;
case 3 : //test heap sport
//Remove elements from the min heap
for(int i = 0; i < quantity; i++)
System.out.print(minHeap.remove() + " ");
break;
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
