[Beauty of Programming 2.5] Finding the K Largest Numbers

This problem is equivalent to finding the k-th largest/smallest number.
Method 1: Sort and output directly. [The book “Beauty of Programming” notes that different sorting methods have different time complexities. Indeed, since we don’t need all n numbers sorted – we only need the k largest.]
Using quicksort:

1
2
3
4
5
6
vector<int> FindMostKSort(vector<int>& vNumbers, int k)
{
   sort(vNumbers.begin(),vNumbers.end());
   vector<int> vKNumbers(vNumbers.rbegin(), vNumbers.rbegin() + k);
   return vKNumbers;
}

Method 2: We don’t actually need all numbers sorted. We can simulate the partition step of quicksort to find the element at the k-th position after sorting.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void swap(int &a, int &b)
{
   int tmp = a;
   a = b;
   b = tmp;
}
void FindMostKPartition(vector<int>& vNumber, int k, int left, int right)
{
   int index = left;
   int tmp = vNumber[index];
   int i = left;
   int j = right;
   while (i < j)
   {
       while(i < j && vNumber[j] >= vNumber[index]) j--;
       swap(vNumber[j], vNumber[index]);
       index = j;
       while(i < j && vNumber[i] <= vNumber[index]) i++;
       swap(vNumber[i], vNumber[index]);
       index = i;
   }
   if (index - left + 1 == k)
   {
       cout << vNumber[index] << endl;
   }
   else if (index - left + 1 < k)
   {
       FindMostKPartition(vNumber, k - (index - left + 1), index + 1, right);
   }
   else
   {
       FindMostKPartition(vNumber, k, left, index - 1);
   }
}

Method 3: Heap sort [maintain a min-heap of size k. The STL code is remarkably short, though you could implement the heap with arrays yourself.]

PS: All sorting uses STL implementations. Implementing sorting from scratch will be attempted in the near future.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void FindMostKHeap(vector<int>& vNumbers, int k)
{
   vector<int> vKNumbers(vNumbers.begin(), vNumbers.begin() + k);
   make_heap(vKNumbers.begin(), vKNumbers.end(), greater<int>());
   for (vector<int>::size_type i = k; i < vNumbers.size(); i++)
   {
       if (vNumbers[i] > vKNumbers[0])
       {
           vKNumbers[0] = vNumbers[i];
           make_heap(vKNumbers.begin(), vKNumbers.end(), greater<int>());
       }
   }
   cout << vKNumbers[0] << endl;
}