【数据结构】找出N个数据中最大的前k个数据（利用堆排序）-创新互联

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

目前创新互联公司已为成百上千的企业提供了网站建设、域名、虚拟空间、网站托管维护、企业网站设计、眉县网站维护等服务，公司将坚持客户导向、应用为本的策略，正道将秉承"和谐、参与、激情"的文化，与客户和合作伙伴齐心协力一起成长，共同发展。

首先我们先分析：既然要选出前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<iostream>
using namespace std;

#include<assert.h>

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]<a[i])
        {
            arr[0] = a[i];
            AdjustDown(arr, 0, K);
        }
    }

    return arr;
    delete[] arr;
}


void Test()
{
    int arr[] = { 12, 2, 10, 4, 6, 8, 54, 67, 25, 178 };
    int k = 5;
    int* ret = HeapSet(arr, sizeof(arr) / sizeof(arr[0]), k);
    Print(ret, k); 
}


int main()
{
    Test();
    system("pause");
    return 0;
}

由此可以看出，时间复杂度为：Ｋ＋（Ｋ-2）/２*lgn＋（Ｎ－Ｋ）*lgn --＞ O(N)

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

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证，机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

网站标题：【数据结构】找出N个数据中最大的前k个数据（利用堆排序）-创新互联
网站路径：https://www.cdcxhl.com/article38/csoppp.html

成都网站建设公司_创新互联，为您提供手机网站建设、App设计、搜索引擎优化、网站导航、网站设计、外贸网站建设

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容