k largest(or smallest) elements in an array | added Min Heap method | GeeksforGeeks

Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.

Method 5(Use Oder Statistics) - Quick Select
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)

http://blog.csdn.net/hackbuteer1/article/details/6651804

1、 随机取某个数，将其与数组末尾元素交换。
a)        idx=rand(0,n-1);生成[0,n-1]间的随机数。
b)        Swap(array[idx], array[n-1]);
2、 用末尾元素x，将比x小的数交换至前，比x大的数交换至后，并返回此时x在数组中的位置mid。
3、 如果mid==n-k，那么返回该值，这就是第k大的数。
如果mid>n-k，那么第k大的数在左半数组，且在左半数组中是第k-(n-mid)大的数。
如果mid<n-k，那么第k大的数在右半数组，而且仍然是第k的数。

Method 6 (Use Min Heap): Time: O(k + (n-k)Logk + kLogk), Space:O(K)

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

=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.

Method 4 (Use Max Heap) - Time: O(n + klogn), Space: O(n)
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)

int Partition(int* pArray, int begin, int end)
{
  int pivot = *(pArray+end);
  int i = begin - 1;

  for(int j = begin; j < end; j++)
  {
    if(*(pArray+j) >= pivot)
     {
       i = i + 1;
       swap(pArray+i,pArray+j);
     }
  }
  swap(pArray+i+1,pArray+end);
  return i+1;
}
//递归的找出第k大元素============================
int QuickSort_K_MAX(int low, int high, int k)
{
 if(low >= high)
    return intarray[high];
 int mid = Partition(intarray,low,high); //划分子递归数组

 if(k < mid)
   QuickSort_K_MAX(low,mid-1,k);  //左递归

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)

http://blog.sina.com.cn/s/blog_73428e9a0101c0zz.html
1. 寻找第2大数的方法
int findSecond(int *a,int size)
{
    int i,max,s_max;
    max=a[0];    //最大值
    s_max=a[1];  //次大值
    for(i=0;i
    {
        if(a[i]>max)
        {
            s_max=max;  //更新最大值和次大值
            max=a[i];
        }
        else if(a[i]<max && a[i]>s_max)   //更新次大值
            s_max=a[i];
    }
    return s_max;
}

http://en.wikipedia.org/wiki/Selection_algorithm

Read full article from k largest(or smallest) elements in an array | added Min Heap method | GeeksforGeeks