TopN算法

TopN算法：從已經存在的數組中，找出最大（或最小）的前n個元素。

算法（以找最大的n個元素為例）：

1. 取出數組的前n個元素，創建長度為n的小根堆；
   
2. 從n開始循環數組的剩余元素，如果當前元素比小根堆的根節點大，則將當前元素設置成小根堆的根節點，并通過調整讓堆保持小根堆；
   
3. 循環完成后，小根堆中的所有元素就是需要找的最大的n個元素；
   
4. 根據需要對小根堆中的所有元素繼續利用堆排序算法進行排序。 </p>

   算法實現的C++版本如下：

   void sift(int pData, int k, int m)
   {
    int i = k, j = k  2;
    while (j <= m) {
    if (j < m && pData[j] > pData[j + 1]) ++j;
    if (pData[i] < pData[j]) break;
    else
    {
        pData[0] = pData[i];
        pData[i] = pData[j];
        pData[j] = pData[0];
        i = j;
        j = i * 2;
    }
   
    }
   }

void TopN(int pData, int len, int pTop, int n, bool sortFlag) // pData[1, len], pTop[1, n] { memcpy(pTop, pData, (n + 1) * sizeof(int)); for (int i = n / 2; i >= 1; --i) sift(pTop, i, n);

for (int i = n + 1; i <= len; ++i)
{
    if (pData[i] > pTop[1])
    {
        pTop[1] = pData[i];
        sift(pTop, 1, n);
    }
}

if (sortFlag)
{
    for (int i = 1; i < n; ++i)
    {
        pTop[0] = pTop[1];
        pTop[1] = pTop[n - i + 1];
        pTop[n - i + 1] = pTop[0];
        sift(pTop, 1, n - i);
    }
}

}</pre>