`

基于堆 [Heap] 结构的 TopK 问题实现

阅读更多

在实际工作中我们经常会遇到将一个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)&comp;
    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; // comp为定制比较函数

 

 

 

 

分享到:
评论

相关推荐

    topK 问题的5种解决方案

    ### TopK 问题的五种解决方案 在计算机科学与数据处理领域中,TopK 问题是一种常见的需求场景,其核心任务是从一个数组或列表中找到最大的 K 个元素。这类问题广泛应用于各种场合,比如搜索引擎返回最相关的 K 条...

    典型的Top K算法 找出一个数组里面前K个最大数.doc

    Heap排序是解决Top K问题的常用方法,我们可以使用Heap来存储Top K个元素,然后不断地将新的元素与Heap的根节点进行比较,如果新的元素比Heap的根节点更大,那么就将新的元素加入Heap中,并将Heap的根节点删除。...

    TOP,K算法.pdf

    【TOP K 算法详解】 ...通过快速选择或堆数据结构,我们可以高效地解决这类问题。需要注意的是,在实际工程中,算法的性能优化、内存管理和并发处理等因素也非常重要,需要根据具体场景进行综合考虑。

    topk_K._python_

    在编程领域,尤其是在数据处理和算法分析中,找到一个数组或列表中的第k大的数是一项常见的任务。...通过学习和理解`topk.py` 和 `quicksort.py` 中的实现,我们可以更好地掌握这些方法,并在实际问题中灵活运用。

    优先级队列(堆实现)

    在实际编程中,`PriorityQueue`常被用作高效的解决方案,如解决Top-K问题、优先级调度等。例如,我们可以用优先级队列来实现一个简单的任务调度器,优先处理优先级高的任务。 总之,`PriorityQueue`通过堆数据结构...

    Min-Max-Heap:提供 min-heap 和 max-heap 的 Java 实现,这是一种高效的数据结构,广泛用于解决从项目列表中获取前 k 个元素的问题

    在实际应用中,最小最大堆常用于解决诸如求数据流中的中位数、维护实时 Top-K 元素等问题。在 Java 中实现最小最大堆,不仅可以帮助处理这些问题,还可以利用 Java 的类库和多线程特性,实现并发访问和更新,进一步...

    算法面试通关40讲完整课件 11-13 优先队列(PriorityQueue)

    1. **堆数据结构**:优先队列通常基于堆实现,最常见的是二叉堆(Binary Heap)。二叉堆是一种近乎完全二叉树,分为两种主要类型:最小堆(Min Heap)和最大堆(Max Heap)。在最小堆中,每个节点的值都小于或等于其...

    C282-Heaps:类分配-堆实现

    1. **优先级队列**:Java中的`PriorityQueue`类就是基于堆实现的,可以高效地插入和删除具有高优先级的元素。 2. **内存管理**:Java的垃圾收集器使用堆来存储对象。新生代、老年代的概念中,堆被划分为不同区域,...

    算法实验代码

    在实际应用中,如堆排序和Top-K问题,优先队列扮演着重要角色。 这些实验代码提供了直观的实现,可以帮助你深入理解这些算法的运作机制和性能特性。在山建大的课程中,这样的实践操作对于提升学生的算法分析和问题...

    Python heapq使用详解及实例代码

    `heapq` 是 Python 内置的一个模块,它提供了一系列基于最小堆的数据结构操作。在 Python 中,`heapq` 模块实现了堆队列算法,也称为优先队列算法。最小堆是一种特殊的树形数据结构,其中每个父节点的关键值都不大于...

    堆排序

    堆排序常用于需要在线性时间复杂度内找到最大或最小元素的情况,例如在求解Top-K问题时。此外,堆排序也是优先队列的一种常见实现方式。 总之,堆排序是计算机科学中一种重要的排序算法,它通过构建和操作堆来达到...

    lrucacheleetcode-leetcode-problems-go:来自leetcode的问题在Go中的解决方案

    它们常用于优先队列和 Top K 问题。在 Go 中,可以使用 `container/heap` 包来操作堆。 3. **树**:树数据结构广泛应用于各种问题,如二叉搜索树、平衡树等。在 LeetCode 中,树相关的问题涵盖了插入、删除、查找...

    立法会:leetcode练习

    7. **堆(Heap)**:如最大堆和最小堆,它们在求解最大值或最小值问题时非常有用,例如找出Top K问题。Jupyter Notebook可以帮助我们理解和实现堆的数据结构。 8. **哈希表**:哈希表常用于解决查找、去重等高效...

Global site tag (gtag.js) - Google Analytics