public class Selector { private static void swap(Word[] array, int i, int j){ if(i == j) return; Word temp = array[i]; array[i] = array[j]; array[j] = temp; }

// Problem #4 (5 pts) // Fill in the following method with an O(n + klog(n)) time algorithm // that returns the k largest elements of array in order from // largest to smallest. // Note: This should return an array with k elements. // all comparisons must be done by the compareTo method. // Hint: Your approach should use a BinaryHeap. public static Word[] heapSelect(Word[] array, int k){ return null; }

} public class Word implements Comparable<Word>{ public String value; public Integer frequency; public Word(String value, Integer frequency){ this.value = value; this.frequency = frequency; } @Override public int compareTo(Word otherWord) { if(this.frequency.equals(otherWord.frequency)) return -1 * this.value.compareTo(otherWord.value); else return this.frequency.compareTo(otherWord.frequency); } public String toString(){ return "[" + value + ", " + frequency + "]"; } }

please solve problem 4 for me in O(n+klog n) time complexity. Using Max heap.

all Words consists of the word itself and the frequency. i.e [Chegg 54]