# Top k Largest Numbers II

ID: 545; medium

## Solution 1 (Java)

``````public class Solution {

private Queue<Integer> minheap;
private int capacity;

/*
* @param k: An integer
*/
public Solution(int k) {
minheap = new PriorityQueue<>();
capacity = k;
}

/*
* @param num: Number to be added
* @return: nothing
*/
if (minheap.size() < capacity) {
minheap.offer(num);
return;
}
if (num > minheap.peek()) {
minheap.poll();
minheap.offer(num);
}
}

/*
* @return: Top k element
*/
public List<Integer> topk() {
// convert heap to list by initialization
List<Integer> res = new ArrayList<>(minheap);
Collections.sort(res, Collections.reverseOrder());
return res;

// // Use iterator
// List<Integer> res = new ArrayList<>();
// Iterator it = minheap.iterator();
// while (it.hasNext()) {
// }
// Collections.sort(res, Collections.reverseOrder());
// return res;
}
}``````

### Notes

• It is important to notice here that we used a min heap. Otherwise, we do not know when to offer or poll based on the number and also the size of the heap.

• Do not forget to reverse the order since the problem is asking for the top k largest numbers.

## Solution 2 (Java)

``````public class Solution {

private int[] heap;
private int n;
private int maxSize;
/*
* @param k: An integer
*/
public Solution(int k) {
heap = new int[k];
maxSize = k;
}

/*
* @param num: Number to be added
* @return: nothing
*/
if (n < maxSize) {
offer(num);
} else {
if (num > heap[0]) {
poll();
offer(num);
}
}
}

/*
* @return: Top k element
*/
public List<Integer> topk() {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
}
Collections.sort(res, Collections.reverseOrder());
return res;
}

/*
* add the number to the last element in the heap and then sift up
*/
private void offer(int num) {
heap[n] = num;
int k = n;
n++;

// sift up
while (k > 0) {
int parent = (k - 1) / 2;
if (heap[k] > heap[parent])
break;
int temp = heap[k];
heap[k] = heap[parent];
heap[parent] = temp;
k = parent;
}
}

/*
* swap the top number with the last element and sift down the last element
*/
private void poll() {
heap[0] = heap[n - 1];
int k = 0;
n--;

// sift down
while (true) {
int left = k * 2 + 1;
int right = left + 1;
int minIndex = k;
if (left < n && heap[left] < heap[minIndex]) {
minIndex = left;
}
if (right < n && heap[right] < heap[minIndex]) {
minIndex = right;
}
if (minIndex == k) break;
int temp = heap[minIndex];
heap[minIndex] = heap[k];
heap[k] = temp;
k = minIndex;
}
}
}``````

### Notes

• This is a version of the solution if we do not use a built-in priority queue.

• This solution utilizes the sift up and sift down methods used in Heapify.

Last updated