使用最小堆使用优先级队列(c语言版本)

绝地灬酷狼 2022-03-07 00:28 164阅读 0赞

下面的例子来自Weiss的《数据结构与算法分析：c语言描述》，自己亲自敲了一遍，跑了个demo，并将结果记录下来。

binheap.h的头文件声明

//description: 使最小堆实现优先级队列
    //date: 2019-03-15
    
    #ifndef __BINHEAP_H__
    #define __BINHEAP_H__
    
    typedef int ElementType;
    
    struct HeapStruct {
        int Capacity; //最大容量
        int Size; //当前大小
        ElementType *Elements; //元素数组
    };
    
    typedef struct HeapStruct *PriorityQueue;
    
    
    
    PriorityQueue Initialize(int MaxElements);
    
    void Destroy(PriorityQueue H);
    
    void MakeEmpty(PriorityQueue H);
    
    int IsEmpty(PriorityQueue H);
    
    int IsFull(PriorityQueue H);
    
    void Insert(ElementType X, PriorityQueue H);
    
    ElementType DeleteMin(PriorityQueue H);
    
    ElementType FindMin(PriorityQueue H);
    
    
    
    #endif

binheap.c源码文件

#include "binheap.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MinData (-32767)
    #define MinPQSize (10)
    
    PriorityQueue
    Initialize(int MaxElements){
        PriorityQueue H;
    
        if(MaxElements < MinPQSize){
            printf("Priority queue size is too small");
            exit(-1);
        }
    
        H = malloc(sizeof(struct HeapStruct));
        if(H == NULL){
            printf("failed to alloc memory space for HeapStruct");
            exit(-1);
        }
    
        /* allocate the array plus one extra for sentinel  */
        H->Elements = malloc( (MaxElements+1) * sizeof(ElementType));
        if(H->Elements == NULL){
            printf("failed to allocate memory for Elements array");
            exit(-1);
        }
    
        H->Capacity = MaxElements;
        H->Size = 0;
        H->Elements[0] = MinData; //此处设置哨兵
    
        return H;
    }
    
    void
    Destroy(PriorityQueue H){
        free(H->Elements);
        free(H);
    }
    
    void
    MakeEmpty(PriorityQueue H){
        H->Size = 0;
    }
    
    void
    Insert(ElementType X, PriorityQueue H){
        int i;
    
        if(IsFull(H)){
            printf("Priority queue is full");
            return;
        }
    
        //从尾部向头部检查
        for(i=++H->Size; H->Elements[i/2]>X; i/=2){
            H->Elements[i] = H->Elements[i/2];
        }
        H->Elements[i] = X;
    }
    
    ElementType
    DeleteMin(PriorityQueue H){
        int i,Child;
        ElementType MinElement, LastElement;
    
        if(IsEmpty(H)){
            printf("FATAL: Priority queue is empty");
            return H->Elements[0];
        }
        MinElement = H->Elements[1];
        LastElement = H->Elements[H->Size--];
    
        for(i=1; i * 2 <= H->Size; i=Child){
            /*Find smaller child*/
            Child = i * 2;
            if(Child != H->Size && H->Elements[Child+1] < H->Elements[Child])
                Child++;
    
            /*Percolate one level */
            //此时最后一个元素已经在堆顶部了，头部与最后一个元素交换过了
            if(LastElement > H->Elements[Child])
                H->Elements[i] = H->Elements[Child];
            else
                break;
        }
        H->Elements[i] = LastElement;
    
        return MinElement;
    }
    
    ElementType
    FindMin(PriorityQueue H){
        if(!IsEmpty(H))
            return H->Elements[1];
        printf("FATAL: Priority queue is Empty");
        return H->Elements[0];
    }
    
    int
    IsEmpty(PriorityQueue H){
        return H->Size == 0;
    }
    
    int
    IsFull(PriorityQueue H){
        return H->Size == H->Capacity;
    }
    
    
    //=================================
    int main(){
        int i, NUM=30;
        PriorityQueue pq = Initialize(NUM);
        for(i=0; i<NUM; i++)
            Insert(i, pq);
    
        while(!IsEmpty(pq)){
            i = DeleteMin(pq);
            printf("%d\n", i);
        }
        Destroy(pq);
    
        return 0;
    }

下面是运行图示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Rhb182Mjc_size_16_color_FFFFFF_t_70]: /images/20220307/f14fa168783a4339ab1e8e58c5e215b5.png