我們舉例，假若從10000萬個(gè)數(shù)里選出前100個(gè)大的數(shù)據(jù)。

目前創(chuàng)新互聯(lián)公司已為成百上千的企業(yè)提供了網(wǎng)站建設(shè)、域名、虛擬空間、網(wǎng)站托管維護(hù)、企業(yè)網(wǎng)站設(shè)計(jì)、眉縣網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

首先我們先分析：既然要選出前100個(gè)大的數(shù)據(jù)，我們就建立一個(gè)大小為100的堆（建堆時(shí)就按找大堆的規(guī)則建立，即每一個(gè)根節(jié)點(diǎn)都大于它的子女節(jié)點(diǎn)），然后再將后面的剩余數(shù)據(jù)若符合要求就插入堆中，不符合就直接丟棄該數(shù)據(jù)。

那我們現(xiàn)在考慮：確定是該選擇大堆的數(shù)據(jù)結(jié)構(gòu)還是最小堆的數(shù)據(jù)結(jié)構(gòu)呢。

分析一下：

若選用大堆的話，堆頂是堆的大值，我們考慮既然要選出從10000萬個(gè)數(shù)里選出前100個(gè)大的數(shù)據(jù)，我們?cè)诮ǘ训臅r(shí)候，已經(jīng)考慮了大堆的特性，那這樣的話大的數(shù)據(jù)必然在它頂端。假若真不巧，我開始的前100個(gè)數(shù)據(jù)中已經(jīng)有這10000個(gè)數(shù)據(jù)中的大值了，那對(duì)于我后面剩余的10000-100的元素再想入堆是不是入不進(jìn)去了！??！所以，選用大堆從10000萬個(gè)數(shù)里選出前100個(gè)大的數(shù)據(jù)只能找出一個(gè)，而不是100個(gè)。

那如果選用最小堆的數(shù)據(jù)結(jié)構(gòu)來解決，最頂端是最小值，再次遇到比它大的值，就可以入堆，入堆后重新調(diào)整堆，將小的值pass掉。這樣我們就可以選出大的前K個(gè)數(shù)據(jù)了。言外之意，假若我們要找出N個(gè)數(shù)據(jù)中最小的前k個(gè)數(shù)據(jù)，就要用大堆了。

代碼實(shí)現(xiàn)(對(duì)于大堆最小堆的代碼，若有不明白的地方，大家可以查看我的博客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個(gè)大的數(shù)據(jù)：" << 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個(gè)數(shù)據(jù)保存
    for (int i = 0; i < K; i++)
    {
        arr[i] = a[i];
    }

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

    //對(duì)剩余的N-K個(gè)元素比較大小
    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;
}

由此可以看出，時(shí)間復(fù)雜度為：Ｋ＋（Ｋ-2）/２*lgn＋（Ｎ－Ｋ）*lgn  --＞  O(N)

空間復(fù)雜度為：K-->O(1)。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

網(wǎng)站標(biāo)題：【數(shù)據(jù)結(jié)構(gòu)】找出N個(gè)數(shù)據(jù)中最大的前k個(gè)數(shù)據(jù)（利用堆排序）-創(chuàng)新互聯(lián)
網(wǎng)站路徑：http://jinyejixie.com/article38/csoppp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供手機(jī)網(wǎng)站建設(shè)、App設(shè)計(jì)、搜索引擎優(yōu)化、網(wǎng)站導(dǎo)航、網(wǎng)站設(shè)計(jì)、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)