Heaps Code
![Goal: Given the following MinHeap class, implement the remove() method.
Requirements: Your code should be as efficient as possible. You may not assume any other method
in the MinHeap class is implemented. You may assume that everything from java.util is imported.
public class MinHeap<T> {
private T[] backingArray;
int size;
* Removes and returns the smallest element in the MinHeap.
*
* The order property of the heap must be maintained after removing.
@return the smallest data in the heap
@throws java.util. NoSuch Element Exception if the heap is empty
public T remove() {
// YOUR CODE HERE, USE THE NEXT PAGE IF NEEDED
Because this method is on your homework, this code cannot be provided :(
Please refer to feedback on your homework.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F37ffeb4c-90e5-4cb9-a6b6-d76475059d8f%2F7bb7c2cc-378c-4c77-a9f4-b835e9f495db%2Fiasy1db_processed.jpeg&w=3840&q=75)
Solution-
According to the question we create an program in which we perform various method like Removing minimum value from heap and printing it ,for Swapping two nodes of the heap,returning the location of the parent for the node that is presently located at position, providing/returning the location of the right and left child for the node that is presently at position,for Swapping two nodes of the heap.. by these methods you may easily understand the concept of heap.
Code-:
// Java Program to Implement Heaps by illustrate min heap
// Main class (MinHeap)
class heap {
//Members of this class's variables
private int[] Heap;
private int size;
private int maxsize;
//setting up the front as static using unity
private static final int FRONT = 1;
// Constructor of this class
public heap(int maxsize)
{
//This keyword refers to the current object.
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
// Method-: 1
// returning the location of the parent for the node that is presently located at position
private int parent(int pos) { return pos / 2; }
// Method 2
// providing/returning the node at position with the position of the left child for that node.
private int leftChild(int pos) { return (2 * pos); }
// Method-; 3
// providing/returning the location of the right child for the node that is presently at position
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
// Method-:4
// if the supplied / node is a leaf node, returning true
private boolean isLeaf(int pos)
{
if (pos > (size / 2)) {
return true;
}
return false;
}
// Method 5
// for Swapping two nodes of the heap
private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
// Method 6
// To heapify the node at that pos
private void minHeapify(int pos)
{
if(!isLeaf(pos)){
int swapPos= pos;
// To determine if the right child is present, switch with the less of the two youngsters. If not, the default value will be "0," and the parent node will be switched in its place.
if(rightChild(pos)<=size)
swapPos = Heap[leftChild(pos)]<Heap[rightChild(pos)]?leftChild(pos):rightChild(pos);
else
swapPos= Heap[leftChild(pos)];
if(Heap[pos]>Heap[leftChild(pos)] || Heap[pos]> Heap[rightChild(pos)]){
swap(pos,swapPos);
minHeapify(swapPos);
}
}
}
// Method 7
// To insert a node into the heap
public void insert(int element)
{
if (size >= maxsize) {
return;
}
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)]) {
swap(current, parent(current));
current = parent(current);
}
}
// Method 8
// To print the contents of the heap
public void print()
{
for (int i = 1; i <= size / 2; i++) {
// Printing the parent and both childrens
System.out.print(
" PARENT : " + Heap[i]
+ " LEFT CHILD : " + Heap[2 * i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
// By here new line is required
System.out.println();
}
}
// Method 9
// To remove and return the minimum
// element from the heap
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
// Method 10
// Main driver method
public static void main(String[] arg)
{
// Display message
System.out.println("The Min Heap is ");
// Creating object opf class in main() methodn
heap minHeap = new heap(15);
// Inserting element to minHeap
// using insert() method
// Custom input entries
minHeap.insert(15);
minHeap.insert(23);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(24);
minHeap.insert(19);
minHeap.insert(60);
minHeap.insert(22);
minHeap.insert(9);
// Print all elements of the heap
minHeap.print();
// Removing minimum value from above heap
// and printing it
System.out.println("The Min val is "
+ minHeap.remove());
}
}
The output of the above code is-
java -cp /tmp/ccZ7Cp641q heap
The Min Heap is
PARENT : 9 LEFT CHILD : 10 RIGHT CHILD :17
PARENT : 10 LEFT CHILD : 15 RIGHT CHILD :24
PARENT : 17 LEFT CHILD : 19 RIGHT CHILD :60
PARENT : 15 LEFT CHILD : 23 RIGHT CHILD :22
The Min val is 9
Step by step
Solved in 2 steps with 8 images
