TopK问题

问题描述：100W个数中找出最大的前K个数。
问题解决方式：
找最大的数要建立小堆，原因是：若建大堆的话，其他更大的数没办法进入堆内。

//TopK问题：
//100W个数中找出最大的前K个数。//建小堆
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
void AdjustDown(int*heap, size_t size, size_t root)
{
    assert(heap);
    size_t parent = root;
    size_t child = 2 * parent + 1;
    while (child < size)
    {
        if ((child + 1 < size)&&heap[child] > heap[child + 1])
        {
            child = child + 1;
        }
        if (heap[child] < heap[parent])
        {
            swap(heap[child], heap[parent]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}
void GetTopK(int*arr, size_t n, int K)
{
    int *heap = new int[K];
    for (int i = 0; i < K; i++)
    {
        heap[i] = arr[i];
    }
    //建堆
    for (int i = (K - 2) >> 1; i >= 0; --i)
    {
        AdjustDown(heap, K, i);
    }
    //排序
    for (int i = K; i < n; i++)//用K+1个元素之后的元素和堆顶比较，如果大于堆顶，交换然后调整
    {
        if (arr[i]>heap[0])
        {
            swap(arr[i], heap[0]);
            AdjustDown(heap, K, 0);
        }
    }
    for (int i = 0; i < K; i++)
    {
        cout << heap[i] << " ";
    }
}
int main()
{
    const size_t M = 10000;
    const size_t K = 100;
    int arr[M] = { 0 };
    for (int i = 0; i < M; i++)
    {
        arr[i] = rand() % M;//这些数都小于M
    }
    //待会打印的前K个元素，就应该是下面这5个。
    arr[0] = 555555;
    arr[99] = 41789;
    arr[987] = 14589;
    arr[100] = 9999;
    arr[235] = 5678;
    GetTopK(arr, M, K);
    system("pause");
    return 0;
}

时间复杂度：K*log（K）+N*log(k)
近似为N*log(k)