优先队列（堆）

- 日理万妓 2022-08-30 04:05 172阅读 0赞

## 优先队列（堆） ##

优先队列（堆）用于调度、排序方面，基本模型如下：

![在这里插入图片描述][20210718171326312.png_pic_center]  
队列中的节点都是有优先级的，如图删除的时候是最小值节点。  
heap.h

struct heap_struct;
    typedef struct heap_struct *priority_queue;
    typedef int ElementType;
    
    priority_queue init(int max_elements);
    void destory(priority_queue h);
    void make_empty(priority_queue h);
    void insert(ElementType x, priority_queue h);
    ElementType delete_min(priority_queue h);
    ElementType find_min(priority_queue h);
    int is_empty(priority_queue h);
    int is_full(priority_queue h);
    
    ElementType find_k_min(priority_queue h,int k);
    
    struct heap_struct{
        
        int capacity;
        int size;
        ElementType * elements;
    };

实现中需要注意三点：  
1.插入时，将待插入节点放入最后一个空穴，逐层上滤（percolate up）；  
2.删除时，删除根节点后，将空穴中两个儿子中较小者移入空穴；  
3.当有偶数个元素时，会遇到节点只有一个儿子，小心发生错误。  
应用：1.求出第K小的元素；2.求出第K大的元素。  
heap.c

void keep_top_k(ElementType x,priority_queue h);
    
    int main(){
        
        priority_queue h = init(10);
        ElementType * data = h->elements;
        int i = 0;
        for(i=1;i<100;i++){
        
            insert(i,h);
        }
        int len = h->size;
        for(i=0;i<len;i++)
            printf("%d\n",data[i]);
        destory(h);
    }
    
    priority_queue init(int max_elements){
        
        struct heap_struct * h = malloc(sizeof(struct heap_struct));
        h->capacity = max_elements;
        h->size = 0;
        ElementType * e = malloc(sizeof(ElementType)*(max_elements+1));  //occupy slot 0
        e[0] = -1;
        h->elements = e;
        return h;
    }
    
    void destory(priority_queue h){
        
        ElementType * e = h->elements;
        free(e);
        free(h);
    }
    
    void make_empty(priority_queue h){
        
        h->size = 0;
    }
    
    void insert(ElementType x,priority_queue h){
        
        if(h->size == h->capacity){
        
            keep_top_k(x,h);
            return;
        }
        int t_slot = (h->size)+1;
        int dest = t_slot;
        if(t_slot > h->capacity){
        
            printf("there is no free slot\n");
            return;
        }
    
        ElementType * data = h->elements;
        data[dest] = x;
        while(data[dest] < data[dest/2]){
        
            if(dest == 1){
        
                data[dest] = x;
                break;
            }
            data[dest] = data[dest/2];
            data[dest/2] = x;
            dest = dest/2;
        }
        data[dest] = x;
        (h->size)++;
    }
    
    ElementType delete_min(priority_queue h){
        
        ElementType ret;
        int len = h->size;
        int capa = h->capacity;
        ElementType * data = h->elements;
        ret = data[1];
        
        int del_posi = 1;
        while(del_posi <= len){
        
            if(del_posi*2 >= len){
        
                data[del_posi] = data[len];
                break;
            }
            else{
        
                if(data[del_posi*2]<data[del_posi*2+1]){
        
                    data[del_posi] = data[del_posi*2];
                    del_posi = del_posi*2;
                }
                else{
        
                    data[del_posi] = data[del_posi*2+1];
                    del_posi = del_posi*2+1;
                }
            }
        }
        len--;
        h->size = len;
        return ret;
    }
    
    ElementType find_k_min(priority_queue h,int k){
        
        ElementType ret;
        int i= 0 ;
        for(i=0;i<k;i++){
        
            ret = delete_min(h);
        }
        return ret;
    }
    
    void keep_top_k(ElementType x,priority_queue h){
        
        int len = h->size;
        int layer = 0;
        int i = 0;
        ElementType * data = h->elements;
        while(len!=0){
        
            len=len/2;
            layer++;
        }
        layer--;
        int po = 1;
        while(layer!=0){
        
            po=po*2;
            layer--;
        }
    
        int insert_po = po;
        int temp_max = data[po];
        for(i=0;i<=len;i++){
        
            if(data[i]>temp_max){
        
                temp_max = data[i];
                insert_po=i;
            }
        }
        if(x<temp_max){
        
            data[insert_po] = x;
        }
        else
            return;
    }
    
    int is_empty(priority_queue h){
        
        if(h->size == 0)
            return 1;
        else
            return 0;
    }
    
    int is_full(priority_queue h){
        
        if((h->size)==(h->capacity))
            return 1;
        else 
            return 0;
    }

[20210718171326312.png_pic_center]: /images/20220829/e18e1e16a5e2414eaae16dfb3c6d43e2.png