# Top k Largest Numbers II

{% embed url="<https://www.lintcode.com/problem/545/>" %}

## Solution 1 (Java)

```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
     */
    public void add(int num) {
        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()) {
        //     res.add((Integer)it.next());
        // }
        // 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)

```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
     */
    public void add(int num) {
        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++) {
            res.add(heap[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](/algo/heap-and-priority-queue/heapify.md).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.yushunchen.com/algo/heap-and-priority-queue/top-k-largest-numbers-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.