在实际工作中我们经常会遇到将一个list中最大[最小]的前TopK个元素输出的问题。
比如说在电商领域,求上个月卖的最好的前10个商品,或者是每个品类下卖的最好的前10个商品。
这类问题,很多数据库或数据仓库工具可以提供直接的实现,比如第一个问题在mysql中就直接order by + limit就好; 而第二个问题在Hive中也很简单, distribute + order by + rownum + where也可以直接搞定,在Oracle则用 partition 就好。
而这些实现的原理都是基于对原list做一次排序,然后在排序结果的基础上取出前TopK个元素。
例如Python中可以这样:
a=[2,1,3,8,7,6,4,7,8,0,-1,3,2,6,3,9] a.sort() top10 = a[0:10]
其中的排序过程使得最后取出的前TopK个元素不仅能满足要求,而且还是排好序的。这似乎是一个非常不错的addtional benifit,不过你除非你确信或可接受由此带来的性能开销,最好不要轻易的接受这种不速的benifit。因为天下没有免费的午餐。。当然,就我见到的应用项目中,99%的做法还真就是这种sort + top的实现。没什么不好,只是他们比较“富裕”,能负担的起这个附加的午餐费而已。
不过,当有一天,我也用上述方法来解决我项目中的问题时发现,程序运行的很慢很慢,因为我的数据量很大很大。。。初步估计要运行好几百个小时,这当然是不能忍的。当然也是因为Python这种解释性语言本身比较低效。
所以必须换一种语言,顺道也换一种更经济的实现策略,就是本文接下来要介绍的:基于堆的topK实现。
很多同学可能都比较熟悉堆排序,但我们的问题并不需要排序,一旦排序,不管用什么方式,都会重蹈覆辙。
让我们重新回顾一下问题:取给定List中的前TopK个最大的元素并输出。
关键点:
1. topK个最大的元素
2. 我们并不需要顺序,因此一切涉及到sort的工作都是不必要的。
3. 要且只要topK个元素,no more needed!!
因此,我们虽然用堆,但并不需要将整个list都建成堆,只需要维护一个K个元素的堆即可。
其次,我们的堆并不用来排序,这点很重要!!!
具体步骤如下:——求最大的TopK个元素
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为定制比较函数
相关推荐
### TopK 问题的五种解决方案 在计算机科学与数据处理领域中,TopK 问题是一种常见的需求场景,其核心任务是从一个数组或列表中找到最大的 K 个元素。这类问题广泛应用于各种场合,比如搜索引擎返回最相关的 K 条...
Heap排序是解决Top K问题的常用方法,我们可以使用Heap来存储Top K个元素,然后不断地将新的元素与Heap的根节点进行比较,如果新的元素比Heap的根节点更大,那么就将新的元素加入Heap中,并将Heap的根节点删除。...
【TOP K 算法详解】 ...通过快速选择或堆数据结构,我们可以高效地解决这类问题。需要注意的是,在实际工程中,算法的性能优化、内存管理和并发处理等因素也非常重要,需要根据具体场景进行综合考虑。
在编程领域,尤其是在数据处理和算法分析中,找到一个数组或列表中的第k大的数是一项常见的任务。...通过学习和理解`topk.py` 和 `quicksort.py` 中的实现,我们可以更好地掌握这些方法,并在实际问题中灵活运用。
在实际编程中,`PriorityQueue`常被用作高效的解决方案,如解决Top-K问题、优先级调度等。例如,我们可以用优先级队列来实现一个简单的任务调度器,优先处理优先级高的任务。 总之,`PriorityQueue`通过堆数据结构...
在实际应用中,最小最大堆常用于解决诸如求数据流中的中位数、维护实时 Top-K 元素等问题。在 Java 中实现最小最大堆,不仅可以帮助处理这些问题,还可以利用 Java 的类库和多线程特性,实现并发访问和更新,进一步...
1. **堆数据结构**:优先队列通常基于堆实现,最常见的是二叉堆(Binary Heap)。二叉堆是一种近乎完全二叉树,分为两种主要类型:最小堆(Min Heap)和最大堆(Max Heap)。在最小堆中,每个节点的值都小于或等于其...
1. **优先级队列**:Java中的`PriorityQueue`类就是基于堆实现的,可以高效地插入和删除具有高优先级的元素。 2. **内存管理**:Java的垃圾收集器使用堆来存储对象。新生代、老年代的概念中,堆被划分为不同区域,...
在实际应用中,如堆排序和Top-K问题,优先队列扮演着重要角色。 这些实验代码提供了直观的实现,可以帮助你深入理解这些算法的运作机制和性能特性。在山建大的课程中,这样的实践操作对于提升学生的算法分析和问题...
`heapq` 是 Python 内置的一个模块,它提供了一系列基于最小堆的数据结构操作。在 Python 中,`heapq` 模块实现了堆队列算法,也称为优先队列算法。最小堆是一种特殊的树形数据结构,其中每个父节点的关键值都不大于...
堆排序常用于需要在线性时间复杂度内找到最大或最小元素的情况,例如在求解Top-K问题时。此外,堆排序也是优先队列的一种常见实现方式。 总之,堆排序是计算机科学中一种重要的排序算法,它通过构建和操作堆来达到...
它们常用于优先队列和 Top K 问题。在 Go 中,可以使用 `container/heap` 包来操作堆。 3. **树**:树数据结构广泛应用于各种问题,如二叉搜索树、平衡树等。在 LeetCode 中,树相关的问题涵盖了插入、删除、查找...
7. **堆(Heap)**:如最大堆和最小堆,它们在求解最大值或最小值问题时非常有用,例如找出Top K问题。Jupyter Notebook可以帮助我们理解和实现堆的数据结构。 8. **哈希表**:哈希表常用于解决查找、去重等高效...