【数据结构】最大堆的插入与删除

红太狼 2022-06-15 04:21 225阅读 0赞

堆是一种特殊的队列，从堆中取出元素的顺序不是按照元素进入队列的先后顺序，而是依据元素的优先权，或者说是大小，所以堆也叫做“优先队列”。  
堆最常使用二叉树结构表示，可以看作是一种特殊的完全二叉树，对于一个最大堆来说可以描述为一颗所有非叶节点的子节点的值都小于该节点的完全二叉树，易得根节点的值最大，所以最大堆也叫大根堆。最小堆的描述与最大堆类似。  
对于堆结构来说最大堆与最小堆的操作是类似的，所以这里以最大堆为例练习堆的操作。  
首先给出最大堆的结构定义。

typedef struct heap{
        int *Elements;//存放堆元素的数组
        int Size;//堆的当前元素个数
        int Capacity;//堆的最大容量
    }* MaxHeap;

创建空的最大堆

MaxHeap Create(int MaxSize)
    {
        MaxHeap H = (MaxHeap)malloc(sizeof(struct heap));
        H->Elements = (int*)malloc((MaxSize+1)*sizeof(int));//多分配一个空间存放哨兵
        H->Size = 0;
        H->Capacity = MaxSize;
        H->Elements[0] = MaxDate;//定义一个大于堆中所有可能元素的哨兵，方便后续的操作
        return H;
    }

插入操作  
插入新元素时需要从堆中新增的结点的父节结点开始向上寻找合适的位置插入。

void Insert(MaxHeap H,int item)
    {
        int i;
        if(H->Size==H->Capacity){
            printf("堆已满");
            return;
        }
        i = ++H->Size;
        for(;H->Elements[i/2]<item;i/=2)
            H->Elements[i] = H->Elements[i/2];
        H->Elements[i] = item;
    }

删除操作  
删除时首先将根节点取出，之后把树中最后一个结点拿出来，之后从树的根节点开始向下寻找合适的位置插入。

int DeleteMax(MaxHeap H)
    {
        int Parent,Child;
        int MaxItem,temp;
        if(H->Size==0){
            printf("堆为空");
            return;
        }
        MaxItem = H->Elements[1];
        temp = H->Elements[H->Size--];
        for(Parent = 1; Parent*2<=H->Size; Parent = Child){
            Child = Parent * 2;
            if((Child<H->Size)&&(H->Elements[Child]<H->Elements[Child+1]))
                Child++;
            if(temp>=H->Elements[Child])
                break;
            else
                H->Elements[Parent] = H->Elements[Child];
        }
        H->Elements[Parent] = temp;
        return MaxItem;
    }