最大堆最小堆怎么删除和添加

最大堆和最小堆是：二叉堆的两种形式。
最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。

最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。

image.png

最大堆的插入
最大堆的插入的思想就是先在最后的结点添加一个元素，然后沿着树上升。跟最大堆的初始化大致相同。

MaxHeap<T> &Insert(const T&x)
{
if(CurrentSize == MaxSize)
exit(1); //没有足够空间

    //为x寻找应插入位置  
    //i从新的叶节点开始，并沿着树上升  
    int i = ++ CurrentSize;  
    while(i != 1 && x > heap[i/2])  
    {  
        //不把x放进heap[i]  
        heap[i] = heap[i/2];        //元素下移  
        i /= 2;     //移向父节点  
    }  
    heap[i] = x;        //这时候才把x放进去  
    return *this;  
}  

最大堆的删除
最大堆的删除，即删除最大的元素。我们先取最后的元素提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置

MaxHeap<T> &DeleteMax(T &x)
{
//检查堆是否为空
if(CurrentSize == 0)
exit(1); //队列空

    x = heap[1];        //最大元素  
    T y = heap[CurrentSize--];      //最后一个元素  
    //从根开始，重构大堆  
    int i = 1, ci = 2;      //ci为i的儿子  
    while(ci < CurrentSize)  
    {  
        if(ci < CurrentSize && heap[ci] < heap[ci + 1])           //比较两个子节点大小，取其大  
            ci ++;  
        //能否放y  
        if(heap[ci] > y)     //不能  
        {  
            heap[i] = heap[ci];     //孩子上移  
            i = ci;                 //下移一层  
            ci *= 2;  
        }  
        else            //能  
            break;  
    }  
    heap[i] = y;  
    return *this;  
}