TopN算法

TopN算法：从已经存在的数组中，找出最大（或最小）的前n个元素。

算法（以找最大的n个元素为例）：
1. 取出数组的前n个元素，创建长度为n的小根堆；
2. 从n开始循环数组的剩余元素，如果当前元素比小根堆的根节点大，则将当前元素设置成小根堆的根节点，并通过调整让堆保持小根堆；
3. 循环完成后，小根堆中的所有元素就是需要找的最大的n个元素；
4. 根据需要对小根堆中的所有元素继续利用堆排序算法进行排序。

算法实现的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);          }      }  }