# Top k Largest Numbers

## Question

> Given an integer array, find the top k largest numbers in it.

**Example**

Given \[3,10,1000,-99,4,100] and k = 3. Return \[1000, 100, 10].

## Analysis

此题运用Priority Queue，也就是Max Heap来求解十分简洁。重点在于对该数据结构的理解和应用。 使用Max Heap，也就是保证了堆顶的元素是整个堆最大的那一个。第一步，先构建一个capacity为k的Max Heap，这需要O(n)时间；第二步，对这个Max Heap进行k次poll()操作，丛中取出k个maximum的元素，这一步操作需要O(k *logn)。因此最终整个操作的时间复杂度是 O(n + k* logn)，空间复杂度是O(k)

对于Top k largest(or smallest) elements in an array问题，有如下几种常见方法：

1. 冒泡排序k次
2. 使用临时数组
3. 使用排序
4. 使用最大堆
5. 使用排序统计
6. 使用最小堆

(摘自GeeksForGeeks)

**Method 1. Use bubble k times**

Thanks to Shailendra for suggesting this approach.

1\) Modify Bubble Sort to run the outer loop at most k times.

2\) Print the last k elements of the array obtained in step 1.

Time Complexity: O(nk)

Like Bubble sort, other sorting algorithms like Selection Sort can also be modified to get the k largest elements.

**Method 2. Use temporary array**

K largest elements from arr\[0..n-1]

1\) Store the first k elements in a temporary array temp\[0..k-1].

2\) Find the smallest element in temp\[], let the smallest element be min.

3\) For each element x in arr\[k] to arr\[n-1] If x is greater than the min then remove min from temp\[] and insert x.

4\) Print final k elements of temp\[]

Time Complexity: O((n-k) *k). If we want the output sorted then O((n-k)* k + klogk)

**Method 3. Use sorting**

1\) Sort the elements in descending order in O(nLogn)

2\) Print the first k numbers of the sorted array O(k).

Time complexity: O(nlogn)

**Method 4. Use Max heap**

1\) Build a Max Heap tree in O(n)

2\) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

**Method 5. Use Order Statistics**

1\) Use order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time O(n) 2) Use QuickSort Partition algorithm to partition around the kth largest number O(n). 3) Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)

Thanks to Shilpi for suggesting the first two approaches.

**Method 6. Use Min Heap**

This method is mainly an optimization of method 2 temp array. Instead of using temp\[] array, use Min Heap.

Thanks to geek4u for suggesting this method.

1\) Build a Min Heap MH of the first k elements (arr\[0] to arr\[k-1]) of the given array. O(k)

2\) For each element, after the kth element (arr\[k] to arr\[n-1]), compare it with root of MH. ……a) If the element is greater than the root then make it root and call heapify for MH ……b) Else ignore it.

The step 2 is O((n-k) \* logk)

3\) Finally, MH has k largest elements and root of the MH is the kth largest element.

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)

All of the above methods can also be used to find the kth largest (or smallest) element.

## Solution

Max Heap

```java
class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
     public int[] topk(int[] nums, int k) {
         Comparator<Integer> comparator = new Comparator<Integer>() {
             @Override
             public int compare(Integer o1, Integer o2) {
                 if(o1 < o2) {
                     return 1;
                 } else if(o1 > o2) {
                     return -1;
                 } else {
                     return 0;
                 }
             }
         };
         PriorityQueue<Integer> minheap = new PriorityQueue<Integer>(k, comparator);

         for (int i : nums) {
             minheap.add(i);
         }

         int[] result = new int[k];
         for (int i = 0; i < result.length; i++) {
             result[i] = minheap.poll();
         }
         return result;
    }
};
```

Min Heap

```java
class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();
        for (int i = 0; i < k; i++) {
           minheap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minheap.peek()) {
                minheap.poll();
                minheap.offer(nums[i]);
            }
        }
        Iterator it = minheap.iterator();
        List<Integer> result = new ArrayList<Integer>();
        while(it.hasNext()) {
            result.add((Integer) it.next());
        }
        Collections.sort(result, Collections.reverseOrder());

        int[] res = new int[result.size()];
        Iterator<Integer> iter = result.iterator();
        for (int i = 0; i < res.length; i++) {
            res[i] = iter.next().intValue();
        }
        return res;
    }
};
```

Sorting

```java
class Solution {
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    public int[] topk(int[] nums, int k) {
        Arrays.sort(nums);
        int[] result = new int[k];
        int j = 0;
        for (int i = nums.length - 1; i > nums.length - k - 1; i--) {
            result[j] = nums[i];
            j++;
        }
        return result;
    }
};
```

## Reference

* [基于堆实现的优先级队列：PriorityQueue 解决 Top K 问题](http://my.oschina.net/leejun2005/blog/135085)
* [geeksforgeeks.org: k largest(or smallest) elements in an array](http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/)
* [My Favorite Interview Question by Arden Dertat - "In an integer array with N elements (N is large), find the minimum k elements (k << N)."](http://www.ardendertat.com/2011/05/30/my-favorite-interview-question/)


---

# 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://aaronice.gitbook.io/lintcode/heap/top_k_largest_numbers.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.