优先队列（堆）-蒲公英云

优先队列（堆）

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

优先队列（堆）

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

在这里插入图片描述
队列中的节点都是有优先级的，如图删除的时候是最小值节点。
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;
}