JAVA JAVA JAVA PLEASE POST OUTPUT IN JAVA Implement a minimum (min) heap of inte
ID: 3680947 • Letter: J
Question
JAVA JAVA JAVA
PLEASE POST OUTPUT IN JAVA
Implement a minimum (min) heap of integers, and write a driver to demonstrate its functionality. Min heaps work the same way as maximum (max) heaps except the a parent is always smaller than its children.
The class your min heap should have the following methods
insert: Add a new element to the heap, and bubble up as needed.
delete: Remove the first element from the heap and then reheapify.
heapSort: Make a copy of the heap, then remove and print each element from the clone. Make sure this doesn’t modify the current heap.
print: Prints the elements in the heap in breadth order.
Example Print Out:
Int Min Heap Tester
Populating Heap with values
21
37
49
11
23
1
13
16
33
17
Printing Heap
1
16
11
21
17
49
13
37
33
23
Testing heap sort
1 11 13 16 17 21 23 33 37 49
Removing an element from the heap
The element removed is 1 and the heap now is:
11
16
13
21
17
49
23
37
33
Explanation / Answer
public class MinHeap
{
private int[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 1;
public MinHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
private int parent(int pos)
{
return pos / 2;
}
private int leftChild(int pos)
{
return (2 * pos);
}
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}
public static void swap(int arr[], int i, int j)
{
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void sort()
{
minHeapify(0);
for (int i = size; i > 0; i--)
{
swap(Heap, 0, i);
N = N-1;
minHeapify(i);
}
}
private void minHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)])
{
if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
public void insert(int element)
{
Heap[++size] = element;
int current = size;
while (Heap[current] < Heap[parent(current)])
{
swap(current,parent(current));
current = parent(current);
}
}
public void print()
{
for (int i = 1; i <= size / 2; i++ )
{
System.out.print(" PARENT : " + Heap[i] + " LEFT CHILD : " + Heap[2*i]
+ " RIGHT CHILD :" + Heap[2 * i + 1]);
System.out.println();
}
}
public void minHeap()
{
for (int pos = (size / 2); pos >= 1 ; pos--)
{
minHeapify(pos);
}
}
public int delete()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
public static void main(String...arg)
{
System.out.println("The Min Heap is ");
MinHeap minHeap = new MinHeap(15);
minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
System.out.println("The Min val is " + minHeap.delete());
minHeap.sort();
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.