背景

在同構(gòu)的n個(gè)數(shù)據(jù)中取Top K的最大值或者最小值有很多方法，例如：

• 排序后，取前K個(gè)或者后K個(gè)，算法復(fù)雜度為nlog(n);
• 維護(hù)大小為K的最大（?。┒眩詈笕《阎械脑?，算法 復(fù)雜度為nlog(k)。
  當(dāng)n很大時(shí)，第二種方法可以得到顯著的速度提升。本文以C++保準(zhǔn)庫(kù)提供的priotiry_queue為基礎(chǔ)，實(shí)現(xiàn)基于堆的Top K算法。

步驟

1. 創(chuàng)建有限隊(duì)列

//自定義結(jié)構(gòu)的比較器，這里為優(yōu)先級(jí)隊(duì)列實(shí)現(xiàn)一個(gè)Great比較器，使優(yōu)先級(jí)隊(duì)列元素從小到大跑得了排序
struct cmpPairSecondFloatGreat{
    bool operator() (const std::pair<int32_t, float>&a, const std::pair<int32_t, float>& b) {
        return a.second > b.second;
    }
};
//定義優(yōu)先級(jí)隊(duì)列，隊(duì)列實(shí)現(xiàn)最小堆，即top為最小值。
std::priority_queue<std::pair<int32_t, float>, std::vector<std::pair<int32_t, float>>, cmpPairSecondFloatGreat> noise_words;

以取最大Top K為例，將自定義比較器給優(yōu)先級(jí)隊(duì)列。

2. 更新優(yōu)先級(jí)隊(duì)列中的值

for (int i = 0; i < 100000000; i++) {
    float num = float(rand());
    if (pq.size() < 3){ //以Top 3為例
      pq.push(make_pair(0, num));
    } else {
      if( num < pq.top().second) {
        continue;
      } else {
        pq.pop(); // 如果當(dāng)前值比待插入值大，則將隊(duì)頭元素刪除，將當(dāng)前值插入隊(duì)列中。
        pq.push(make_pair(1, num));
      }
    }
    vecs.push_back(make_pair(0, num));
  }

3. 獲取Top K的值
   取出有限隊(duì)列中的值，即得到Top K的值。

while (!pq.empty()) {
    cout << pq.top().second << " ";
    pq.pop();
  }

總結(jié)

通過有限隊(duì)列內(nèi)部實(shí)現(xiàn)的堆算法，手動(dòng)控制有限隊(duì)列的大小，即可模擬實(shí)現(xiàn)基于最大（?。┒训腡op K算法。