top-k 算法浅析

浏览: 144 发布日期: 2017-07-26 分类: c

简介

top-k算法,其实就是寻找最大的k个数(具体详见《编程之美》第2.5节“寻找最大的k个数”)。比如一个数组:1,2,5,9,4,3,7 需要寻找最大的2个数,那么就是9和7。最早之前我接触到topk算法的时候,觉得解决思路就是排序,排完序之后,取前k个数就可以了。但是这种思路虽然简单,但是效率是很差的。因为题目只要求最大的k个数,并不需要k个数有序,也不需要后n-k个数有序。

解决方法

我用的是解法四,用一个容量为k的最小堆来储存最大的k个数。最小堆的堆顶元素就是最大k个数中最小的一个。每次新考虑一个数x,如果x比堆顶的元素y小,则不需要改变原来的堆,因为这个元素比最大的k个数小。如果x比堆顶的元素大,那么用x替换堆顶的元素y。在x替换堆顶元素y后,x可能破坏最小堆的结构(每个结点都比它的父亲结点大),需要更新堆来维持堆的性质。

代码实现(C语言)

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

// 定义取最大N个数
#define TOP_K 6
int heap[6];

// 交换数据
void swap(int *a, int *b)
{
    int temp = *b;
    *b = *a;
    *a = temp;
}

// 调整最小堆
void min_heapify(int arr[], int start, int end)
{
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)
    {
        if (son + 1 <= end && arr[son] > arr[son + 1])
            son++;
        if (arr[dad] < arr[son])
            return;
        else
        {
            swap(&arr[dad], &arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

// 建立最小堆
void buid_heap(int heap[])
{
    int i;
    for (i = TOP_K / 2; i >= 0; i--)
    {
        min_heapify(heap, i, TOP_K - 1);
    }
}

// 8,8,8,9,9,9
int main()
{
    int arr[] = {3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6};
    int len = (int)sizeof(arr) / sizeof(*arr);
    int i;

    // 堆赋值
    for (i = 0; i < TOP_K; i++)
    {
        heap[i] = arr[i];
    }

    buid_heap(heap); // 建立最小堆

    // 循环遍历整个数组
    for (i = TOP_K + 1; i <= len; i++)
    {
        if (arr[i] > heap[0]) // 只有大于根节点才处理
        {
            heap[0] = arr[i];
            min_heapify(heap, 0, TOP_K - 1); // 向下调整堆
        }
    }

    // 打印最大key个数
    for (i = 0; i < TOP_K; i++)
    {
        printf("%d ", heap[i]);
    }
}
返回顶部