数据结构-堆（最大堆）

浅浅的花香味﹌ 2022-12-13 04:20 127阅读 0赞

## 最大堆 ##

实质是一棵**完全二叉树**

**每个根结点元素的值都比左右儿子的大**

每次都是取出堆顶元素(可以说是优先队列）

## 代码 ##

> 参考自浙大数据结构

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define ERROR -1
    const int MAXDATA = 1<<30;
    using namespace std;
    typedef int ElementType;
    typedef struct HeapStruct *MaxHeap;
    struct HeapStruct
    {
        
        ElementType *Elements; /*存储元素的数组*/
        int Size; /*当前堆元素个数*/
        int Capacity; /*堆的最大容量*/
    };
    
    
    /*建堆(申请需要的内存)*/
    MaxHeap Creat(int MaxSize)
    {
        
        /*创建容量为MaxSize的最大堆*/
        MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
        H->Elements = (ElementType*)malloc((MaxSize+1)*sizeof(ElementType));
        H->Size = 0;
        H->Capacity = MaxSize;
        H->Elements[0] = MAXDATA; /*定义哨兵为大于所有可能元素的值，以便后面更快操作*/
        return H;
    }
    
    bool IsFull(MaxHeap H)
    {
        
        return H->Size == H->Capacity;
    }
    bool IsEmpty(MaxHeap H)
    {
        
        return H->Size == 0;
    }
    
    void Insert(MaxHeap H,ElementType item)
    {
        
        int i;
        if(IsFull(H))
        {
        
            printf("最大堆已满！\n");
            return;
        }
        i = ++H->Size; /*指向堆中最后一个元素的位置*/
        for( ; H->Elements[i/2] < item; i/=2)
        {
        
            H->Elements[i] = H->Elements[i/2]; /*下移小的item*/
        }
        H->Elements[i] = item; /*将item插入*/
    }
    
    ElementType Delete(MaxHeap H)
    {
        
        if(IsEmpty(H))
        {
        
            printf("最大堆为空！\n");
            return ERROR;
        }
        int Parent,Child; /*parent指定最后一个元素temp放的位置*/
        ElementType MaxItem,temp;
        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++; /*Child指向左右结点较大者*/
            if(temp >= H->Elements[Child]) break;
            else /*移动temp到下一层:Parent = Child*/
                H->Elements[Parent] = H->Elements[Child];
        }
        H->Elements[Parent] = temp;
        return MaxItem;
    }
    void PushDown(MaxHeap H,int p)
    {
        
        /*将H中以p为根结点的堆调整为最大堆*/
        int Parent,Child;
        ElementType X = H->Elements[p]; /*取根结点存放的值*/
        for(Parent = p; Parent * 2 <= H->Size; Parent = Child)
        {
        
            Child = Parent * 2;
            if((Child < H->Size) && (H->Elements[Child] < H->Elements[Child+1]))
                Child++; /*指向更大的结点*/
    
            if(X >= H->Elements[Child]) break;
            else H->Elements[Parent] = H->Elements[Child];/*调整*/
        }
        H->Elements[Parent] = X;
    }
    
    /*根据输入的数据构建好MaxHeap*/
    void BuildHeap(MaxHeap H)
    {
        
        /*
        与删除一个元素的调整策略相同
        从最后一个子堆根结点开始依次调整堆
        */
        for(int i = H->Size/2; i > 0; --i)
        {
        
            PushDown(H,i);
        }
    }
    int main()
    {
        
        MaxHeap H = Creat(100);
        H->Size = 10;
        for(int i = 1; i <= 10; ++i)
        {
        
            H->Elements[i] = i;
        }
        BuildHeap(H);
        Insert(H,2021);
        Insert(H,1998);
        while(!IsEmpty(H))
        {
        
            printf("%d\n",Delete(H));
        }
        return 0;
    }