PLEASE DO NOT CHANGE ANY PARAMETER NAME, ANY METHOD NAME OR ANY OTHER SOMETHINGS. FILL IN THE BLANK WHICH IS NECESSARY. THANK YOU IN ADVANCE.

THERE ARE TWO CLASSES(MINHEAP AND SORTING)

MinHeap:

public class MinHeap { private static final int DEFAULT_CAPACITY = 10; private int currentSize; // size of the min heap private int[] array; // the array that keeps the heap public MinHeap(){ this (DEFAULT_CAPACITY); } public MinHeap(int capacity){ currentSize = 0; array = new int[capacity + 1]; // +1 because we are not using array[0] } public MinHeap(int[] items){ currentSize = items.length; array = new int[(currentSize + 2) * 11 / 10]; int i = 1; for(int item:items) array[i++] = item; buildHeap(); } public int[] getArray(){ return this.array; } public int getCurrentSize(){ return currentSize; } public boolean isEmpty(){ return currentSize == 0; } public void makeEmpty(){ currentSize = 0; } public int findMin(){ if( isEmpty() ) return -1; return array[1]; } private void enlargeArray(int newSize){ int [] old = array; array = new int[newSize]; for(int i = 0; i < old.length; i++){ array[i] = old[i]; } } public void insert(int x){ if(x <= 0) return; if(currentSize == array.length - 1) enlargeArray(array.length * 2 + 1); percolateUp(x, ++currentSize); } private void percolateUp(int x, int hole){ for( array[0] = x; x < array[hole/2]; hole /=2 ) array[hole] = array[hole/2]; array[hole] = x; } private void percolateDown(int hole){ int child; int tmp = array[hole]; for(; hole * 2 <= currentSize; hole = child){ child = hole * 2; if( child != currentSize && array[child+1] < array[child]) child++; if( array[child] < tmp ) array[hole] = array[child]; else break; } array[hole] = tmp; } public int deleteMin(){ if(isEmpty()) return -1; int minItem = findMin(); array[1] = array[currentSize--]; percolateDown(1); return minItem; } private void buildHeap(){ for(int i = currentSize/2; i > 0; i--){ percolateDown(i); } } public void printHeap(){ int level = 0; System.out.println(" ---------------------------"); for (int i = 1; i < currentSize + 1; i++) { System.out.print(array[i] + " "); if ((i + 1) % Math.pow(2, level) == 0) { System.out.println(); level++; } } System.out.println(" --------------------------- "); } }

Sorting:

public class Sorting { public static void altSelectionSort(int[] arr){ /* * * IMPLEMENT THIS METHOD * */ } public static void heapSortDecr(int[] arr){ /* * * IMPLEMENT THIS METHOD * */ } }