最小堆的插入删除函数

佚名 4年前 (2020-02-27) 算法 643人围观抢沙发百度已收录

最小堆的插入删除函数

这里记录最小堆插入删除函数的写法。如果需要最大堆，只需要基本操作的反过来就可以了。

操作基本都有注释。结合注释理解。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Talk is cheap . Show me the code .

vector<int> minHeap;//需要设施哨兵，minHeap[0]=INT_MIN;
void insert(int x) {
    minHeap.push_back(x);//将插入值放在堆底
    int child=minHeap.size()-1;
    while(minHeap[child/2]>minHeap[child]){//上滤操作，调整为最小堆
        swap(minHeap[child/2],minHeap[child]);//上滤操作
        child/=2;//完全二叉树在数组中表示的特点：child/2=parent
    }
}
int Delete(){
    int value=minHeap[1];//有哨兵，index为1的位置才是堆顶
    swap(minHeap[1],minHeap[minHeap.size()-1]);//交换栈顶和底部元素
    minHeap.pop_back();//将目标值弹出
    int parent=1,child=0;
    for(parent=1;parent*2<minHeap.size();parent=child){
        child=parent*2;//完全二叉树在数组中表示的特点：child/2=parent
        if(child!=minHeap.size()-1&&minHeap[child+1]<minHeap[child]) child++;
        //判断有无右孩子，若有，是左孩子较小还是右孩子较小，再更新child的下标值
        if(minHeap[parent]<minHeap[child]) break;//若符合堆的定义，弹出
        else swap(minHeap[parent],minHeap[child]);//下滤操作
    }
    return value;//返回删除的元素值
}