在实际工作中我们经常会遇到将一个list中最大[最小]的前TopK个元素输出的问题。
比如说在电商领域，求上个月卖的最好的前10个商品，或者是每个品类下卖的最好的前10个商品。
最常用的方式就是对列表排序，然后从前到后数K个元素。
例如Python中可以这样：
a = [2,1,3,4,2,4,65,7,22,3,6] a.sort() top10 = a[0:10]
其中的排序过程使得最后取出的前TopK个元素不仅能满足要求，而且还是排好序的。这似乎是一个非常不错的addtional benifit，不过你除非你确信或可接受由此带来的性能开销，最好不要轻易的接受这种不速的benifit。因为天下没有免费的午餐。。当然，就我见到的应用项目中，99%的做法还真就是这种sort + top的实现。没什么不好，只是他们比较“富裕”，能负担的起这个附加的午餐费而已。
不多当你的数据量很大，而且这个超大的List不能够直接load到内存，
而同时你的项目对计算能力要求很高，那么就必须自己实现一个堆结构来满足需求了。
接下来，本文就通过C语言实现一个小顶堆，来完成最大TopN元素选取的实现。
这里有一个关键点，就是不要试图排序。
具体步骤如下：
1. 建一个K个元素的空堆 HP，即一个K个元素的数组
2. 遍历原List，将元素依次压入HP中，在压入过程中：
2.1 如果压入的个数还不到K个，则直接压入，
2.2 如果压入之后的个数达到K个，则将该K个元素维护成一个堆结构
2.3 在压入每个元素之前，如果HP中已经有K个元素，则将新元素与HP的第一个元素比较
2.3.1 如果新元素大于HP的第一个元素，则将新元素放在HP的第一个位置，并调整HP堆。
2.3.2 如果新元素小于HP的第一个元素，则continue 到 2.
遍历完后HP中的K个元素即为List中的前TopK大的元素。
具体代码如下：
heap.h ——heap结构申明
#ifndef HEAP_H
#define HEAP_H
/* ------------------------------
* Data Define for Heap Structor
* Oh This is just a Min Heap!!!
* ------------------------------ */
typedef int (*HEAP_CMP_FN)(void *, void*);
typedef struct _heap {
int len;
int size;
void ** data;
HEAP_CMP_FN heap_cmp_fn;
} Heap;
/* ---------------------------------------------
* Interface Function Define for Heap Operation
* --------------------------------------------- */
Heap * heap_create(int size);
void * heap_add(Heap * hp, void * pdata);
void heap_free(Heap * hp);
#endif
heap.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "heap.h"
/* ----------------------------------
* Default Compare Function for Heap
* ---------------------------------- */
int default_heap_cmp_fn(int* m, int* n){
int i = *m - *n;
return i > 0 ? 1 : (i < 0 ? -1 : 0);
}
/* ----------------------------------
* Create and Return a Heap Structor
* ---------------------------------- */
Heap * heap_create(int size){
if (size < 2){
fprintf(stderr,"too small size no need heap\n");
return NULL;
}
Heap * hp = (Heap*)malloc(sizeof(Heap));
hp->len = 0;
hp->size = size;
hp->data = (void**)malloc(sizeof(void*) * size);
memset(hp->data,0,sizeof(void*) * size);
hp->heap_cmp_fn = (HEAP_CMP_FN)&default_heap_cmp_fn;
return hp;
}
#define HEAP_ADJUST(hp,l) do { \
int lt = l; \
int i = lt + lt + 1; \
int r = hp->len - 1; \
void * t = hp->data[lt]; \
do { \
if ((i<r) && (hp->heap_cmp_fn(hp->data[i], hp->data[i+1]) > 0)){ \
i += 1; \
} \
if (hp->heap_cmp_fn(t,hp->data[i]) <= 0){ \
break; \
} \
hp->data[lt] = hp->data[i]; \
lt = i; \
i += i + 1; \
}while (i <= r); \
hp->data[lt] = t; \
} while (0); \
/* ----------------------------------
* Add an Element into the Heap
* ---------------------------------- */
void * heap_add(Heap * hp, void * pdata){
if (hp->len < hp->size){
hp->data[hp->len] = pdata;
hp->len += 1;
if (hp->len >= hp->size){
int l = hp->len / 2;
while(--l >= 0){
HEAP_ADJUST(hp,l);
}
}
return NULL;
}
void * top = hp->data[0];
if (hp->heap_cmp_fn(top,pdata) < 0){
hp->data[0] = pdata;
HEAP_ADJUST(hp,0);
return top;
}
return pdata;
}
/* ----------------------------------
* Free the Heap Memory Space
* ---------------------------------- */
void heap_free(Heap * hp){
if (hp->data){
for (int i = 0; i < hp->len; i++){
free(hp->data[i]);
hp->data[i] = NULL;
}
free(hp->data);
hp->data = NULL;
}
free(hp);
}
heap_test.c
#include <stdlib.h>
#include <stdio.h>
#include "heap.h"
// int main(){
// Heap * hp = heap_create(10);
// for (int i = 0; i < 20; i++){
// int c = rand() % 100;
// printf("%d,",c);
// int * v = (int*)malloc(sizeof(int));
// *v = c;
// int * p = heap_add(hp,v);
// if (p)
// free(p);
// }
// printf("\n");
// for (int i = 0;i < hp->len;i++){
// printf("%d,",*((int*)hp->data[i]));
// }
// printf("\n");
// return 0;
// }
typedef struct {
int id;
float score;
} Element;
int comp(Element * m,Element * n){
if (m->score > n->score){
return 1;
}
else if (m->score<n->score){
return -1;
}
else{
return 0;
}
}
int main(){
Heap * hp = heap_create(5);
hp->heap_cmp_fn = (HEAP_CMP_FN)∁
for (int i = 0; i < 20; i++){
int id = rand() % 100;
float score = 100.0 * (float)rand() / RAND_MAX ;
Element * p = (Element*)malloc(sizeof(Element));
p->id = id;
p->score = score;
printf("%d,%f\n",id,score);
Element * t = heap_add(hp,p);
if (t)
free(t);
}
for (int i = 0;i < hp->len;i++){
fprintf(stderr,"%d,%f\n",((Element *)hp->data[i])->id,((Element *)hp->data[i])->score);
}
return 0;
}
如代码所示，该Heap结构默认支持int类型的数据，如果元素类型为自定义复杂结构，则需要提供一个定制的比较函数，赋值给堆结构的 heap_cmp_fn 函数指针即可，如测试代码中：
hp->heap_cmp_fn = (HEAP_CMP_FN)∁ // comp为定制比较函数