Own implementation of MaxHeap(good for beginners). O(n) space complexity and O(n*logn) worst time complexity. Java

• ``````public class Solution {
public static List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int val: nums) {
if (map.containsKey(val)) {
map.put(val, map.get(val)+1);
} else {
map.put(val, 1);
}
}
int[] heap = buildHeap(map);
int temp, size = heap.length-1;
for(int i = 0; i < heap.length; i++) {
temp = heap[0];
heap[0] = heap[size];
heap[size] = temp;
size--;
percolateDown(heap, 0, size, map);
}
List<Integer> result = new ArrayList<Integer>();
for(int i = heap.length-1, j = 0; i >= 0 && j < k; i--, j++) {
}

return result;
}

public static int[] buildHeap(HashMap<Integer, Integer> map) {
int[] result = new int[map.size()];
int i = 0;
for(int key: map.keySet()) {
result[i++] = key;
}
for(i = (result.length - 1)/2; i >= 0; i--) {
percolateDown(result, i, result.length-1, map);
}

return result;
}

public static void percolateDown(int[] items, int i, int size, HashMap<Integer, Integer> map) {
if (i > size || i < 0) {
return ;
}
int max = i, temp = -1, left, right;
left  = 2*i+1;
right = 2*i+2;
if (left <= size && map.get(items[left]) > map.get(items[i])) {
max = left;
}
if (right <= size && map.get(items[right]) > map.get(items[max])) {
max = right;
}
if (max != i) {
temp       = items[i];
items[i]   = items[max];
items[max] = temp;
percolateDown(items, max, size, map);
}
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.