堆和优先队列

堆：

分大顶堆和小顶堆，这里实现的是小顶堆，也就是说父亲节点一定小于孩子节点，不像二叉排序树这样，堆对子节点之间的大小没有限制，限制的仅仅只有一个条件，父亲一定比孩子节点小，这就是小顶堆，大顶堆则相反

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

优先队列：堆中的每个元素都带有一个优先级，入队是无序的，出队是有序的，排序过程只需要在每步插入和删除都平衡一下堆就够了，所以有种排序算法叫堆排序

代码实现

结构：

这里用数组实现,length代表堆数组的长度，注意这里的树形结构是完全二叉树结构

int Heap[MAX]={0};
int length = 0;

寻找父亲和孩子节点

这里反回的是节点的索引

int parent(int j){
    if(j>0){
        return (j-1)/2;  //返回当前节点父亲的位置      
    } 
    return -1;  //返回当前节点父亲的位置 
}

int left(int j){
    return j*2+1;
}
int right(int j){
    return j*2+2;
}

元素上浮

上浮操作发生在插入的时候，因为插入永远都是从尾部插入，为了平衡堆，所以需要将插入的元素 上浮到符合小顶堆的位置

//上浮 
void up(int j){
    if(j>0 && Heap[j]<Heap[parent(j)]){ //如果比父母小 
        swap(Heap[j],Heap[parent(j)]);// 交换 
        up(parent(j)); //递归 
    } 
}

元素下沉

下沉操作发生在删除元素的时候，因为删除元素的逻辑是将堆顶元素和尾部元素替换，注意，堆顶元素永远都是整个堆的最小的元素

那为什么要和尾部元素替换呢？为了方便堆顶元素的移除，尾部元素移除很方便快速

将尾部元素替换到堆顶后，可能会打破平衡，所以需要将刚替换的堆顶元素下沉

//下沉 
void down(int j){
    //堆是一颗完全二叉树 先有左边 再有右边 
    if(has_left(j)){
        int small = left(j);
        if(has_right(j))
            if(Heap[small]>Heap[right(j)])
                small = right(j);
        
            
        if(Heap[small]<Heap[j]){
            swap(Heap[small],Heap[j]);
            down(small); //递归 
        }
    }
}

添加和删除

//添加 
void add(int val){
    Heap[length++] = val;
    up(length-1); //将新元素上浮  
}

//删除 取堆顶元素 
int remove(){
    
    swap(Heap[0],Heap[length-1]);//先和最后一个换 再删除
    int r = Heap[--length]; //返回结果 
    
    down(0);  //堆顶下沉
    return r; 
}

取最小值

int get_min(){
    if(length>0){
        return Heap[0];
    }else{
        return -1;
    }
}

所有可执行代码

#include <iostream>
using namespace std;
#define MAX 100

int Heap[MAX]={0};
int length = 0; 

int parent(int j){
    if(j>0){
        return (j-1)/2;  //返回当前节点父亲的位置      
    } 
    return -1;  //返回当前节点父亲的位置 
}

int left(int j){
    return j*2+1;
}
int right(int j){
    return j*2+2;
}


bool has_left(int j){
    return left(j)<length; 
}
bool has_right(int j){
    return right(j)<length;
}

//上浮 
void up(int j){
    if(j>0 && Heap[j]<Heap[parent(j)]){ //如果比父母小 
        swap(Heap[j],Heap[parent(j)]);// 交换 
        up(parent(j)); //递归 
    } 
}

//下沉 
void down(int j){
    //堆是一颗完全二叉树 先有左边 再有右边 
    if(has_left(j)){
        int small = left(j);
        if(has_right(j))
            if(Heap[small]>Heap[right(j)])
                small = right(j);
        
            
        if(Heap[small]<Heap[j]){
            swap(Heap[small],Heap[j]);
            down(small); //递归 
        }
    }
} 

int get_min(){
    if(length>0){
        return Heap[0];
    }else{
        return -1;
    }
} 

//添加 
void add(int val){
    Heap[length++] = val;
    up(length-1); //将新元素上浮  
}

//删除 取堆顶元素 
int remove(){
    
    swap(Heap[0],Heap[length-1]);//先和最后一个换 再删除
    int r = Heap[--length]; //返回结果 
    
    down(0);  //堆顶下沉
    return r; 
} 







int main(int argc, char *argv[])
{
    add(43); 
    add(53);
    add(4);
    add(3);
    add(9);
    add(100);

    cout<<remove()<<endl;
    cout<<remove()<<endl;
    cout<<remove()<<endl;
    cout<<remove()<<endl;
    cout<<remove()<<endl;
    cout<<remove()<<endl;
    
    cout<<"----------"<<endl; 

    return 0;
}
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄