$//1.$ Implement a Heap class based on my code ArrayBinaryTree.java

$//2.$ Test the insert and delete methods of your Heap class using the examples on my slide $"$PQ&Heap.pdf$".$

$//$

$//$ The output should be:

$//$

$//=============================$ Test insert$()$

$//$ Before insert$()...$

$//25697$

$//$ Inserting a new node $1...$

$//$ After insert$()...$

$//152976$ null null null null

$//=============================$ Test removeMin$()$

$//$ Before removeMin$()...$

$//25697$

$//$ Removing the minimum $...$

$//$ After removeMin$()...$

$//5769$ null

$//$

$//===============================================$ Note

$//$

$//1.$ DO NOT DELETE ANY COMMENT!!!

$//2.$ Modify the file name to "ArrayHeap.java" before compiling it$.$

$//$

$//===============================================$

public class ArrayHeap$>$ extends ArrayBinaryTree $\{$

private int size;

private int height;

@SuppressWarnings$("$unchecked$")$

public ArrayHeap$()\{$

super$()$;

this.size $=0$;

$\}$

public ArrayHeap$($E root$)\{$

super$($root$)$;

this.size $=1$;

$\}$

public ArrayHeap$($E$[]$ array$)\{$

super$($array$)$;

this.size $=$ array.length;

$\}$

public void expandArray$()\{$

@SuppressWarnings$("$unchecked$")$

E$[]$ newArray $=($E$[])$ new Comparable$[$this$.$array.length $*2]$;

for$($int i$=0$; i $<$ this.array.length; i$++)\{$

newArray$[$i$]=$ array$[$i$]$;

$\}$

this.array $=$ newArray;

$\}$

public int height$()\{$

return $($int$)$Math$.$ceil$($Math$.$log$($this$.$size $+1)/$ Math.log$(2))-1$;

$\}$

public void insert$($E element$)\{$

if $($this$.$size $>=$ this.array.length$)\{$

this.expandArray$()$;

$\}$

this.array$[$this$.$size$]=$ element;

this.size$++$;

this.upHeap$()$;

$\}$

public void upHeap$()\{$

$//$ parentElement.compareTo$($currentElement$)>0$ means

$//$ parentElement $>$ currentElement

int currentRank $=$ this.size $-1$;

while$($currentRank $>0)\{$

int parentRank $=$ getParentRank$($currentRank$)$;

E parentElement $=$ getElement$($parentRank$)$;

E currentElement $=$ getElement$($currentRank$)$;

if $($parentRank $>=0$ && parentElement.compareTo$($currentElement$)>0)\{$

E temp $=$ currentElement;

this.array$[$currentRank$]=$ parentElement;

this.array$[$parentRank$]=$ temp;

$\}$

currentRank $=$ parentRank;

$\}$

$\}$

public void removeMin$()\{$

if$($this$.$size $==0)\{$

System.out.println$("$The heap is empty!"$)$;

return;

$\}$

this.array$[0]=$ this.array$[$size $-1]$;

this.array$[$size $-1]=$ null;

this.size$--$;

this.downHeap$()$;

$\}$

public void downHeap$()\{$

$//$ COMPLETE THIS BLOCK

$\}$

public static void main$($String$[]$ args$)\{$

System.out.println$("=============================$ Test insert$()")$;

Integer$[]$ array $=\{2,5,6,9,7\}$;

ArrayHeap myHeap $=$ new ArrayHeap$($array$)$;

System.out.println$("$Before insert$()...")$;

myHeap.display$()$;

System.out.println$("$Inserting a new node $1...")$;

myHeap.insert$(1)$;

System.out.println$("$After insert$()...")$;

myHeap.display$()$;

System.out.println$("=============================$ Test removeMin$()")$;

Integer$[]$ array$2=\{2,5,6,9,7\}$;

ArrayHeap myHeap$2=$ new ArrayHeap$($array$2)$;

System.out.println$("$Before removeMin$()...")$;

myHeap$2.$display$()$;

System.out.println$("$Removing the minimum $...")$;

myHeap$2.$removeMin$()$;

System.out.println$("$After removeMin$()...")$;

myHeap$2.$display$()$;

$\}$

$\}$