学步园

TOP K即返回给定集合最大的K个元素，这个集合有可能很大，十亿，有可能万亿，所以对算法的要求比较高。以下是我的总结：

一、采用快速排序的分治算法思想进行求解：

快速排序的思想是使用一个标志点将数组分为两个部分，小于该点的数据移动到该点的左侧，大于该点的数据移动到该点的右侧，然后进行递归，最后达到有序。同理我们也可以使用该思想求数组的TOP K。也是使用第一个元素左右标志，小于该点的元素移到左侧，大于该点的元素移到右侧，第一次partition后有有三种情况：

1、标志点右侧的数据正好是K-1，那么加上标志点就是要求的TOP K个元素

2、标志点右侧的数据个数N小于K-1，那么就需要在标志点左侧的集合中寻找TOP （K- N），通过递归就可以实现

3、标志点右侧的数据个数N大于K-1，那么就需要在标志点右侧的集合中需要TOP K个元素，通过递归实现

代码如下：

#include <stdio.h>
#include <unistd.h>

void getRand(int* data, int length) {
    int i;
    srand((unsigned int) getpid());
    for (i = 0; i < length; i++) {
        data[i] = rand() % 1000;
    }
    //print the array
    printf("generate the array using rand:\n");
    for (i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

void partition(int arr[], int low, int high, int *pos){
        int key = arr[low];
        int i = low, j = high;
        while(i < j){
                while(i < j && arr[j] > key) j--;
                if(i < j){
                        arr[i++] = arr[j];
                }
                while(i < j && arr[i] < key) i++;
                if(i < j){
                        arr[j--] = arr[i];
                }
                //arr[i] = key;
        }
        arr[i] = key;
        *pos = i;
}

int topK(int arr[], int low, int high, int k){
        int pos =0;
        partition(arr, low, high, &pos);
        int num = high - pos + 1;
        int index = -1;
        if(num == k){
                index = pos;
        }else if(num > k){
                index = topK(arr, pos + 1, high, k);
        }else{
                index =  topK(arr, low, pos -1, k - num);
        }
        return index;
}

int main(){
        int arr[10] = {0};
        getRand(arr, 10);
        int pos;
        pos = topK(arr, 0, 9, 5);
        for(;pos < 10;pos++){
                printf("%d\t", arr[pos]);
        }
        printf("\n");
}

这种算法的缺点是需要针对数据做频繁的移动操作，如果数据量较大就需要使用文件的形式进行分治计算。

二、使用最小堆取得TOP K元素是一种很好的方式

至于为为什么使用最小堆，那是因为最小堆堆顶是最小的元素，只有大于堆顶的元素才会加入堆，然后对堆进行adjust。这种方式只需要维护K个元素的 最小堆。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void print(int arr[], int size){
        int i = 0;
        for(; i < size;i++){
                printf("%d\t", arr[i]);
        }
}
//最小堆是排序的
void add(int arr[],int size,int num){
        if(num > arr[0]){
                arr[0] = num;
                //调整堆
                int i = 0;
                for(;i < size -1 && num > arr[i+1];i++){
                        arr[i] = arr[i+1];
                }
                arr[i] = num;
        }
}
//最小堆不排序（开始元素是1）
void sink(int arr[], int size, int num){
        if(num > arr[1]){
                arr[1] = num;
                int i = 1;
                while(2 * i <= size){
                        int j = 2 * i;
                        if(j < size && arr[j + 1] < arr[j]) j++;
                        if(arr[i] > arr[j]){
                                int tmp = arr[i];
                                arr[i] = arr[j];
                                arr[j] = tmp;
                                i = j;
                        }else{
                                break;
                        }
                }
        }
}

void getRand(int* data, int length) {
    int i;
    srand((unsigned int) getpid());
    for (i = 0; i < length; i++) {
        data[i] = rand() % 1000;
    }
    //print the array
    printf("generate the array using rand:\n");
    for (i = 0; i < length; i++) {
        printf("%d ", data[i]);
    }
    printf("\n");
}

int main(int argc, char *argv[]){
        int arr[11] = {0};
        int heap[10] = {0};
        int heap2[11] = {0};
        getRand(arr, 11);
        int i;
        for(;i< 11;i++){
                add(heap, 10, arr[i]);
                sink(heap2, 10, arr[i]);

        }
        print(heap, 10);
        int j = 1;
        for(; j < 11;j++){
                printf("%d\t", heap2[j]);
        }
}