【原創】TOP k算法的簡單實作

        顧名思義，TOP k就是從海量的資料中選取最大的k個元素或記錄。基本思想就是維護一個具有k個元素的小頂堆。每當有新的元素加入時，判斷它是否大于堆頂元素，如果大于，用該元素代替堆頂元素，并重新維護小頂堆，直到所有元素被處理完畢。時間複雜度為O(N*logk)，基本達到線性複雜度。部分代碼如下：

//列印數組元素  void print(int data[], int length)  {      for(int i = 1; i <= length; ++i)          cout << data[i] << " ";      cout << endl;  }  //維護小頂堆  void modifySmallHeap(int data[], int location, int length)  {      int lchild = 2 * location;      int rchild = 2 * location + 1;      int smallest;      if(lchild <= length && data[lchild] < data[location])smallest = lchild;      else smallest = location;      if(rchild <= length && data[rchild] < data[smallest])smallest = rchild;      if(smallest != location)      {          swap(data[location], data[smallest]);          modifySmallHeap(data, smallest, length);      }  }  //建立小頂堆  void buildSmallHeap(int data[], int length)  {      for (int i = length / 2; i > 0; --i)      {          modifySmallHeap(data, i, length);      }  }  //top k算法的簡單實作  void HeapSortK(int data[], int length, int topk)  {      buildSmallHeap(data, topk);      for (int i = topk + 1; i <= length; ++i)      {          if(data[i] <= data[1])continue;          else          {              swap(data[1], data[i]);              modifySmallHeap(data, 1, topk);          }      }  }

       為了便于測試，可以利用随機數函數構造測試用例。鑒于一切從簡，我就不多說了。

PS:順便貼出一個小頂堆和大頂堆的圖檔