最大堆最小堆解决TOPK问题

堆：实质是一颗完全二叉树，最大堆的特点：父节点值均大于子节点；最小堆的父节点值均小于子节点；

一般使用连续内存存储堆内的值，因而可以根据当前节点的索引值推断子节点的索引值：

节点i的父节点为(i-1)/2；

节点j的左子结点：j * 2 + 1;

节点j的右子结点：j * 2 + 2;

以下代码实现了最大堆最小堆，当比较函数使用std::greater，得到最大堆，当比较函数使用std::less得到最小堆；

代码及测试用例如下：

  1 //最大最小堆
  2 //MaxMinHeap.h
  3 
  4 #pragma once
  5 #include <assert.h>
  6 
  7 using namespace std;
  8 
  9 template <typename T>
 10 void mswap(T &a, T &b)
 11 {
 12     T tmp = a;
 13     a = b;
 14     b = tmp;
 15 }
 16 
 17 template <typename T,typename Compare = std::less<T>>
 18 class MaxMinHeap
 19 {
 20 public:
 21     int hSize ;    //堆空间
 22     int hCurNum;//堆内已占用空间
 23     T *data;
 24 
 25 private:
 26     Compare comp;//比较函数
 27 public:
 28     MaxMinHeap(int size)
 29     {
 30         hSize = size;
 31         assert(hSize>0);
 32         data = new T[hSize];
 33         hCurNum = 0;
 34     };
 35     ~MaxMinHeap(void)
 36     {
 37         if(data!=NULL)
 38             delete []data;
 39     };
 40 
 41     void headAdd(T num)
 42     {
 43         if (hCurNum==hSize)
 44         {
 45             if (comp(num,data[0]))//greater 大顶堆 保留最小的K个数；less 小顶堆 保留最大的K个数
 46                 return;
 47             data[0]=num;
 48             HeapFixDown(0,hCurNum);
 49         }
 50         else
 51         {
 52             data[hCurNum++]=num;
 53             HeapFixUp(hCurNum-1);
 54         }
 55     };
 56     //最大堆排序后得到升序序列；最小堆排序后得到降序序列
 57     void sort()
 58     {
 59         for (int i=hCurNum-1; i >=1 ; --i)
 60         {
 61             mswap(data[i],data[0]);
 62             HeapFixDown(0,i);
 63         }
 64     }
 65 
 66     void GetHnum(T &n)//获取最大堆的最小值或者最小堆的最大值
 67     {
 68         n = data[0];
 69     };
 70     void HeapFixUp(int index)
 71     {
 72         assert (index < hCurNum);
 73         T tmp=data[index];
 74         int j = (index - 1)/2;//父节点
 75         while(j>=0 && index !=0)
 76         {
 77             if(comp(data[j],tmp))
 78                 break;
 79             data[index]=data[j];
 80             index = j;
 81             j = (index - 1)/2;
 82         }
 83         data[index]=tmp;
 84     };
 85 
 86     //从节点index开始进行向下调整
 87     void HeapFixDown(int index, int n)
 88     {
 89         assert(index<hCurNum);
 90         assert(n<hCurNum);
 91 
 92         T tmp=data[index];
 93         int j = index*2+1;
 94         while(j<n)
 95         {
 96             if(j+1 < n && comp(data[j+1],data[j]))//大顶堆中左右孩子找最大的，小顶堆左右孩子找最小的
 97                 ++j;
 98             if(comp(tmp,data[j]))
 99                 break;
100             data[index]=data[j];
101             index = j;
102             j = index*2+1;
103         }
104         data[index]=tmp;
105     };
106 };
107 
108 #include <functional>
109 #include <iostream>
110 #include "MaxMinHeap.h "
111 
112 using namespace std;
113 
114 int main(int argc ,  char ** argv)
115 {
116     MaxMinHeap<float,greater<float>> test(20);
117 
118     for (int i = 0 ;i < 20; ++i)
119     {
120         test.headAdd(-i*2+38);
121     }
122     for (int i = 0 ; i < 20 ; ++i)
123     {
124         cout<<test.data[i]<<endl;
125     }
126     test.sort();
127     for (int i = 0 ; i < 20 ; ++i)
128     {
129         cout<<test.data[i]<<" ";
130     }
131     cout<<endl;
132     return 0;
133 }

最大堆 最小堆 解决TOPK问题

最大堆最小堆解决TOPK问题