【データ構造】N個のデータの中で最大の前k個のデータを探し出す(ヒープで並べ替える)

例えば、10000万個の数から上位100個の最大データを選ぶといいです.
まず分析します.最初の100個の最大のデータを選ぶためには、大きさが100のヒープを作ります.(ヒープを作る時は一番山のような規則で作ります.つまり、各ルートのノードはその子供のノードより大きいです.).その後、後の残りのデータを要求に合致したら、山に入れます.
一番多くのデータ構造を選ぶべきか、それとも一番小さい山のデータ構造を選ぶべきかを今考えています.
分析してみます
一番山を選ぶなら、一番大きい山は一番大きい山です.10000万個の数から一番前の100個の最大のデータを選ぶべきだと考えています.私達は山を建てる時、一番多い特性を考慮しました.そうすると、一番大きいデータはきっとその先端にあります.もしあいにくなら、最初の100個のデータの中にすでにこの10000個のデータの中の最大値がありました.それは私の後に残っている10000-100の元素に対して再び山に入れないのですか?だから、最大の山を選んで10000万個の数の中から前の100個の最大のデータを選んで1つだけ探し出すことができて、100個ではありません.
もし最小のヒープのデータ構造を選択して解決したら、一番上の部分は最小の値で、再度それより大きい値に出会ったら、積み重ねに入れて、再び山を調整して、小さい値のパスを落とします.これで最大の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  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 < 0);
    int* arr = new int[K];
    //  K     
    for (int i = 0; i =0; i--)
    {
        AdjustDown(arr,i,K);
    } 

    //    N-K       
    for (int i = K; i 

このことから、時間の複雑さは、K＋(K−2)／2＊lgn＋(N−K)＊lgnであることがわかる.  --＞  O(N)
空間複雑度はK-->O(1)です.
転載先:https://blog.51cto.com/10740184/1768075