最小堆怎么建立

女爷i 2022-08-08 14:47 130阅读 0赞

有一个面试题，100w个数中找到最大的100个数。  
解决方式是，用一个100个容量的最小堆， 这100个数总数目前已知的最大的100个，而且  
堆顶是小的， 在继续遍历时候，只和堆定比较， 如果这个数，比堆顶的大， 就把这个数加入  
这个堆。  
当遍历完成后，这个最小堆中的数，就是最大的100个数了。

当理解了这个， 我还有一个疑惑， 什么是最小堆。

[http://blog.csdn.net/genios/article/details/8157031][http_blog.csdn.net_genios_article_details_8157031]

学习了这个篇帖子。 受益匪浅。 文章写的很好， 一开始很难理解，跟着模拟了一下，

关键是要自己模拟程序，去移动一下 这个树，才理解。

typedef struct heap HEAP;
    struct heap {
         int arr[127];
         int size;
    };
    
    void insert(HEAP *h,int n){
           int sz = h->size++;
           printf("%d --- %d\n",sz,n);
           while(sz>0){
                if(n < h->arr[(sz-1)/2]){//若改成 > 则为大根堆
                    h->arr[sz] = h->arr[(sz-1)/2];
                    sz = (sz-1)/2;
                }else{
                    h->arr[sz] = n;
                    return;
                }
           }
           h->arr[0] = n;
    }
    
    void delete(HEAP *h){
           h->size--;
           h->arr[0] = h->arr[h->size];
           h->arr[h->size] = 0;
           int i = 1,cv = h->arr[0],tmp;
           while(i < h->size){
                   if(i < h->size-1 && h->arr[i] > h->arr[i+1])
                          i++;
                   if(h->arr[i] < cv){
                          h->arr[(i-1)/2] = h->arr[i];
                          h->arr[i] = cv;
                          i = i*2 + 1;
                   }else{
                          return;
                   }
           }
    }

下面这个是我自己改的，上面的是 wikipedia上copy的

#include <iostream>
    
    typedef struct heap HEAP;
    
    struct heap
    {
        int arr[100];
        int size;
    };
    
    
    //将数字num 插入 最小堆
    //游标 比 位置 小一
    void insert(HEAP *h, int num)
    {
    
        int sz = h->size;
        h->size++;
    
        while( sz >0 ){
            if(num > h->arr[(sz-1)/2]){
                h->arr[sz] = num;
                return;
            }else{
                h->arr[sz] = h->arr[(sz-1)/2]; 
                sz = (sz-1)/2;
            }   
        }   
    
        h->arr[0] = num;
    
    }
    
    
    
    
    void c_delete(HEAP *h) 
    {
        h->size--;
        h->arr[0] = h->arr[h->size];
        h->arr[h->size] = 0;
    
        int i=1;
        int cv = h->arr[0];
    
        while(i<h->size){
            if(cv < h->arr[i] && cv < h->arr[i+1]){
                return ;
            }   
    
            if(h->arr[i] > h->arr[i+1])
                i++;
            else{
                h->arr[(i-1)/2] = h->arr[i];
                h->arr[i] = cv;
                i = i*2 +1;
            }
        }
    }
    
    
    int main()
    {
        return 0;
    }

[http_blog.csdn.net_genios_article_details_8157031]: http://blog.csdn.net/genios/article/details/8157031