TopK問題-スタック・ソート・ベース

一、紹介
TopK問題とは,実は配列の中で最大の前k個の値を探すことである.そのため,配列中のk番目の大きな値を見つけることができれば,TopK問題は解決される.ここで宣言しますが、本文の書き方はきっと一番ではありません.しかし、最近いくつかの問題を見て、その核心はすべてk番目の値を探すことです.ここで、私はただまとめただけです.
二、例を挙げて説明する
例えば、配列a[N]について、その最大の最初のk個の数をとる.
1、配列b[k]で初期小天井スタックを構築する(0で配列bを初期化すればよい).
2、i=1,2,...,Nから順にaを遍歴する.
2.1、もし:a[i]>b[0]であれば、b[0]の代わりにa[i]を用い、同時に小天井スタックを再調整する.
2.2、そうでなければ、b[0]を一定に保つ.
3、手順2をi=Nまで繰り返します.
三、詳細コード
3.1、小天井

#define NUM 10
typedef int ELEM;
void heap(ELEM a[],int left,int right)
{
    if (left >= right) 
            return ;
    int r = left;//        
    int LChild = 2*r+1;//           
    int Child = LChild;

    ELEM temp = a[r];//         

    //        
    while(LChild <= right)
    {
        if(LChild < right && a[LChild] > a[LChild+1])
                    Child = LChild + 1;//Child           
        if(temp > a[Child]) 
        {
                a[r] = a[Child];                    
                r = Child;//         
                LChild = 2*r+1;//         
                Child = LChild;//        
        }
        else
            break;
    }
    a[r] = temp;
    return;
}

3.2、主関数

int main(int argc,char **argv) 
{   
    if(argc < 2)
    {
        printf("      ！");
        return 0;
    }   
    int i;
    int k = atoi(argv[1]);
    ELEM a[NUM] = {2,5,3,1,6,13,15,1859,131,13};

    ELEM* b = (ELEM*)malloc(k*sizeof(ELEM));    
    memset(b,0,k*sizeof(ELEM));

    //    
    for(i = 0;i < NUM;i++)
    {
            if(a[i] > b[0])
            {
                    b[0] = a[i];
                    heap(b,0,k-1);
            }
    }

    //        k    ，   b( )    .
    printf("a    k  :");
    for (i = 0;i < k;i++)
        printf("%d ",b[i]);     

    free(b);
    b = NULL;

    return 0;
}

3.3、出力結果k=5の場合、上記のコード出力結果は、

a    k  :13 13 131 1859 15

(ここでのk個数は無秩序)
4、説明
最初のk個の最小数を取る場合は、上記の小さなトップスタックを大きなトップスタックに変更して主関数に変更します.

if(a[i] > b[0])
{
        b[0] = a[i];
        heap(b,0,k-1);
}

の「a[i] > b[0]」を「a[i] < b[0]」に変更すればよい.
上記の思想は主に「プログラミングの美しさ,p 142~p 144」から参考にしている.