设计并实现TopKRecord结构，可以不断地网其中加入字符串，可以根据字符串chu’xian的情况随时打印加入次数最多前K个字符串。
    image.png
    image.pngimage.pngimage.pngimage.png

    image.pngimage.png

    1. class Node{
    2.     public:
    3.         string s;
    4.         int count;
    5.     Node(string ss, int c):s(ss),count(c){}
    6. };
    1. class TopKRecord{
    2.   private:
    3.     vector<Node*> heap;
    4.     int index;//队尾的后一个位置
    5.     unordered_map<string,Node*> strNodeMap;
    6.     unordered_map<Node*,int> nodeIndexMap;
    7.   public:
    8.     TopKRecord(int size){
    9.          heap.resize(size);
    10.         index=0;
    11.     }
    12.     void add(string str){
    13.         Node* curNode=nullptr;
    14.         int location=-1;
    15.          if(find(strNodeMap.begin(),strNodeMap.end(),str)==strNodeMap.end()){
    16.              curNode = new Node(str,1);
    17.             strNodeMap[str]= curNode;
    18.             nodeIndexMap[curNode]=-1;
    19.         }else{
    20.              curNode=strNodeMap[str];
    21.             curNode->count++;
    22.             location=nodeIndex[curNode];
    23.         }
    24.         if(location==-1){
    25.              if(index < heap.size()){
    26.                 nodeIndexMap[curNode]=index;
    27.                  heap[index]=curNode;
    28.                 heapBuild(index);
    29.                 index++;
    30.             }else{
    31.                  if(curNode->count>heap[0]->count){
    32.                      Node* root=heap[0];
    33.                     nodeIndex[root]=-1;
    34.                     heap[0]=curNode;
    35.                     nodeIndex[curNode]=0;
    36.                     heapKeep(0,index);
    37.                 }
    38.             }
    39.         }else{
    40.              heapKeep(location,index);   
    41.         }
    42.     }
    43. };
    1. void heapKeep(int start, int end){
    2.      int left=start*2+1;
    3.     int right=left+1;
    4.     int cur=start;
    5.     int smallest=cur;
    6.     while(left<end){
    7.          if(heap[cur]->val>heap[left]->val){
    8.             smallest=left;
    9.         }
    10.         if(right<=end&&heap[smallest]->val>heap[right]->val){
    11.              smallest=right;   
    12.         }
    13.         if(smallest!=cur){
    14.             swap(smallest,cur);
    15.         }else{
    16.             break;
    17.         }
    18.         cur=smallest;
    19.         left=cur*2+1;
    20.         right=left+1;
    21.     }
    22. }
    1. void heapBuild(int start){
    2.      int cur=start;
    3.     int parent=(cur-1)/2;
    4.     int smallest=cur;
    5.     while(parent>=0){
    6.         if(heap[parent]->val>heap[cur]->val){
    7.              swap(cur,parent);   
    8.             cur=parent;
    9.             parent=(cur-1)/2;
    10.         }else{
    11.             break;
    12.         }
    13.     }
    14. }

    TopKRecord::swap(i,j)是最为关键的地方之一，它要保证，交换节点的值时，要更新nodeIndexMap中其位置的更新，这十分关键。

    1. void swap(int i, int j){
    2.      int t=heap[i]->val;   
    3.     heap[i]->val=heap[j]->val;
    4.     heap[j]->val=t;
    5.     //更新节点的位置记录
    6.     nodeIndexMap[heap[i]]=j;
    7.     nodeIndexMap[heap[j]]=i;
    8. }

    关于void reduce(str)

    不在堆中，只需更新哈希表；若还在堆中，同时要heapBuild(location)；若减小为零，heapBuild操作把之交换到root节点后，删除此root节点： swap(0,index);—index; heapKeep(0,index);

    打印topK，时间复杂度为O(k)：

    1. void printTopK(){
    2.      for(int i=0;i<index;++i){
    3.          cout << heap[i]->val << ",";   
    4.     }
    5. }