堆

优先队列：取出元素的顺序是依照元素的优先权大小，而不是元素进入队列的先后顺序。
二叉堆
结构性：由数组表示的完全二叉树
有序性：任一结点的关键字是其子树所有结点的最大值（最小值）
最大堆/大顶堆 MaxHeap（MinHeap）
操作集

MaxHeap Create(int MaxSize);
Boolean IsFull(MaxHeap H);
Insert(MaxHeap H, ElementType item);
Boolean IsEmpty(MaxHeap H);
ElementType DeleteMax(MaxHeap H);

typedef struct HeapStruct *MaxHeap;
struct HeapStruct{
    ElementType *Elements;
    int Size;    int Capacity;
}

MaxHeap Create(int MaxSize)
{
    MaxHeap H=malloc(sizeof(struct HeapStruct));
    H->Elements=malloc((MaxSize+1)*sizeof(ElementType));
    //MaxSize+1是因为是从下标1位置开始放元素的
    H->Size=0;    H->Capacity=MaxSize;
    H->Elements[0]=MaxData;
    //哨兵，大于堆中所有可能的元素，便于后序操作
    return H;
}

//新元素在堆中上滤找到正确位置
void Insert(MaxHeap H, ElementType item)
{
    int i;
    if(IsFull(H)) {...}
    i=++(H->Size);
    for( ;H->Elements[i/2]<item;i/=2)    
        H->Elements[i]=H->Elements[i/2];
        //和父节点比较若比父节点大，则父节点下来，新结点上去
    H->Elements[i]=item;
}
//因为有个哨兵元素，即使插入的是最大的元素最终一定也能跳出循环

//删掉最大的元素
ElementType DeleteMax(MaxHeap H)
{
    int Parent, Child;
    ElementType MaxItem, temp;
    if(IsEmpty)...
    MaxItem=H->Elements[1];
    temp=H->Elements[H->Size];    H->Size--;
    for(Parent=1;Parent*2<=H->Size;Parent=Child){
        Child=Parents*2;
        if((Child!=H->Size)&&(H->Elements[Child]<H->Elements[Child+1))
            Child++; 
        if(temp>=H->Elements[Child]) break;
        else
            H->Elements[Parents]=H->Elements[Child];
    }
    H->Elements[Parent]=temp;
    return MaxItem;

堆.PNG
堆构建.PNG