大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

【数据结构】找出N个数据中最大的前k个数据(利用堆排序)

我们举例,假若从10000万个数里选出前100个最大的数据。

创新互联建站-专业网站定制、快速模板网站建设、高性价比贵定网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式贵定网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖贵定地区。费用合理售后完善,十余年实体公司更值得信赖。

首先我们先分析:既然要选出前100个最大的数据,我们就建立一个大小为100的堆(建堆时就按找最大堆的规则建立,即每一个根节点都大于它的子女节点),然后再将后面的剩余数据若符合要求就插入堆中,不符合就直接丢弃该数据。

那我们现在考虑:确定是该选择最大堆的数据结构还是最小堆的数据结构呢。

分析一下:

若选用最大堆的话,堆顶是堆的最大值,我们考虑既然要选出从10000万个数里选出前100个最大的数据,我们在建堆的时候,已经考虑了最大堆的特性,那这样的话最大的数据必然在它顶端。假若真不巧,我开始的前100个数据中已经有这10000个数据中的最大值了,那对于我后面剩余的10000-100的元素再想入堆是不是入不进去了!!!所以,选用最大堆从10000万个数里选出前100个最大的数据只能找出一个,而不是100个。

那如果选用最小堆的数据结构来解决,最顶端是最小值,再次遇到比它大的值,就可以入堆,入堆后重新调整堆,将小的值pass掉。这样我们就可以选出最大的前K个数据了。言外之意,假若我们要找出N个数据中最小的前k个数据,就要用最大堆了。

代码实现(对于最大堆最小堆的代码,若有不明白的地方,大家可以查看我的博客http://10740184.blog.51cto.com/10730184/1767076):

#define _CRT_SECURE_NO_WARNINGS 1
#include
using namespace std;

#include

void AdjustDown(int* a, int parent, int size)
{
    int child = 2 * parent + 1;
    while (child < size)
    {
        if (child + 1 < size && a[child] > a[child + 1])
        {
            child++;
        }
        if (a[parent]>a[child])
        {
            swap(a[parent], a[child]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}


void Print(int* a, int size)
{
    cout << "前k个最大的数据:" << endl;
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
}


int* HeapSet(int*a,int N,int K)
{
    assert(a);
    assert(K > 0);
    int* arr = new int[K];
    //将前K个数据保存
    for (int i = 0; i < K; i++)
    {
        arr[i] = a[i];
    }

    //建堆
    for (int i = (K-2)/2; i >=0; i--)
    {
        AdjustDown(arr,i,K);
    } 

    //对剩余的N-K个元素比较大小
    for (int i = K; i < N; i++)
    {
        if (arr[0]

由此可以看出,时间复杂度为:K+(K-2)/2*lgn+(N-K)*lgn  -->  O(N)

空间复杂度为:K-->O(1)。


网站标题:【数据结构】找出N个数据中最大的前k个数据(利用堆排序)
转载注明:http://dzwzjz.com/article/ghgghp.html
在线咨询
服务热线
服务热线:028-86922220
TOP