堆（建立，插入，删除）

短命女 2023-07-03 12:07 21阅读 0赞

首先定义优先队列，优先队列是一种特殊的队列，取出元素的顺序是依据优先权（关键字）的大小，而不是元素进出队列的顺序。  
如果使用二叉搜索树存储这个优先队列，就构成了“堆”结构。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]若任意的根节点的元素都比其子树中的任何元素都大，则该堆称为最大堆；反之称为最小堆。  
堆结构常进行的操作有（以最大堆为例子）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]

一 定义堆的结构：

typedef struct HeapStruct *MaxHeap;
    struct HeapStruct
    {
        
        int *element;  //建立一个指向数组的指针，也可以直接建立数组，现面通过下表直接访问。
        int size; //堆当前元素个数
        int Capacity;//堆的容量。
    };

二.创建堆

MaxHeap Create(int maxsize)
    {
        
        MaxHeap H=malloc(sizeof(struct HeapStruct));//为堆申请一个空间
        H->element=malloc((maxsize+1)*sizeof(int));//创建数组，从1开始使用，所以要加边界加1.
        H->size=0;
        H->Capacity=maxsize;
        H->element[0]=999999;//随意复制一个很大的数，便于插入元素。
    }

三.插入元素

void Insert(MaxHeap H,int item)
    {
        
        int i;
        if(H->size==H->Capacity){
        
            printf("最大堆已满");
            return;}
        i=++H->size;
        for(;H->element[i/2]<item;i/=2)//与上一个结点比较，若比他大就就把小的向下移动
            H->element[i]=H->element[i/2];
        H->element[i]=item;//因为0号元素很大，所以一定不会大于0号，最大的情况也会停留在1号位置。
    }

四.最大堆的删除  
删除的位置确定，即为根节点的位置。

MaxHeap DeleteMax(MaxHeap H)
    {
        
        int Parent,Child;
        int Maxitem,temp;
        if(IsEmpty(H)){
        
            printf("最大堆已经为空");
            return;
        }
        Maxitem=H->element[1];//先把要删除的要素保存起来
        temp=H->element[H->size--];//找到最边界的元素存起来，因为删除了了个元素，size要再减去1.
        for(Parent=1;Parent*2<H->size;Parent=Child){
        //parent*2就是其左儿子，如果存在就可以进行循环。
            Child=Parent*2;
            if((Child!=H->size)&&(H->element[Child]<H->element[Child+1]))
                Child++;//如果右儿子大，就切换到右儿子
            if(temp>=H->element[Child])break;
            else//否则就与左儿子交换
                H->element[Parent]=H->element[Child];//循环目的就是找到其左右儿子中较大的那个
    }
    H->element[Parent]=temp;
    return H;
    }

五.最大堆的建立  
方法一.在空堆上进行n次插入操作。  
方法二.按输入顺序输入建立一个完全二叉树，从第一个有子节点的结点开始调整，依次向前调整每一个结点，时间复杂度等于所有节点的高度和。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200206123552421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200206124434273.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FieXNzd2F0Y2hlcjE=,size_16,color_FFFFFF,t_70