堆

(二叉）堆是一个数组，可以被看成近似的完全二叉树

父节点/左孩子/右孩子

int parent(int i){
    return i/2;
}
int left(int i){
    return 2*i;
}
int right(int i){
    return 2*i+1;
}

二叉堆可以分为最大堆和最小堆
最大堆：某个节点至多与其父节点一样大
最小堆：除了根以外的所有节点i，都有A[parent(i)]<=A[i]
堆排序算法我们可以使用最大堆，最小堆通常用于构造优先队列
堆的高度定义为根节点的高度（从下往上数0，1，2...)
堆结构的一些基本操作的运行时间至多与树的高度成正比，即O(logn)

维护最大堆--O(logn)

void max_heapify(int A[],int i,int length){//数组传参不用带引用 
    int l = left(i);
    int r = right(i);
    int largest;
    if(l<=length && A[l]>A[i]){
        largest = l;
    }else{
        largest = i;
    }
    if(r<=length && A[r]>A[largest]){
        largest = r;
    }
    if(largest != i){
        swap(A[i],A[largest]);
        max_heapify(A,largest,length);
    }
}

构造堆--O(n)

void build_max_heap(int A[],int length){//这里下标是以1开始的
    for(int i=length/2;i>=1;i--){
        max_heapify(A,i,length);
    }
}

堆排序--O(nlogn)

void heapsort(int A[],int length){//从小到大的堆排序 
    build_max_heap(A,length);
    for(int i=length;i>=2;i--){
        swap(A[1],A[i]);
        length = length-1;
        max_heapify(A,1,length);
    }
}

最小堆

void min_heapify(vector<pair<int,int> > &A,int i,int length){//数组传参不用带引用 
    int l = left(i)+1;
    int r = right(i)+1;
    int shortest;
    if(l<=length && A[l].first<A[i].first){
        shortest = l;
    }else{
        shortest = i;
    }
    if(r<=length && A[r].first<A[shortest].first){
        shortest = r;
    }
    if(shortest != i){
        swap(A[i],A[shortest]);
        min_heapify(A,shortest,length);
    }
}
//这里下标是以0开始的
void build_min_heap(vector<pair<int,int> > &A,int length){
    for(int i=length/2-1;i>=0;i--){
        min_heapify(A,i,length);
    }
}

优先队列的一些操作--O(logn)

1. Insert - (push)

堆的插入就是把新的元素放到堆底，然后检查它是否符合堆的性质，如果符合就丢在那里了，如果不符合，那就和它的父亲交换一下，一直交换交换交换，直到符合堆的性质，那么就插入完成了

void swap(int &x,int &y){int t=x;x=y;y=t;}//交换函数 
int heap[N];//定义一个数组来存堆
int siz;//堆的大小 
void push(int x){//要插入的数 
    heap[++siz]=x;
    now=siz;
    //插入到堆底 
    while(now){//还没到根节点，还能交换 
        ll nxt=now>>1;//找到它的父亲 
        if(heap[nxt]>heap[now])swap(heap[nxt],heap[now]);//父亲比它大，那就交换 
        else break;//如果比它父亲小，那就代表着插入完成了 
        now=nxt;//交换 
    }
    return; 
}

2.Minimun

3.Extract-min

4.Decrease-key

5.Delete - (pop)

删除操作，但是在实际的代码操作中，并不是这样进行删除操作的，有一定的微调，代码中是直接把堆顶和堆底交换一下，然后把交换后的堆顶不断与它的子节点交换，直到这个堆重新符合堆性质

void pop(){
    swap(heap[siz],heap[1]);siz--;//交换堆顶和堆底，然后直接弹掉堆底 
    int now=1;
    while((now<<1)<=siz){//对该节点进行向下交换的操作 
        int nxt=now<<1;//找出当前节点的左儿子 
        if(nxt+1<=siz&&heap[nxt+1]<heap[nxt])nxt++;//看看是要左儿子还是右儿子跟它换 
        if(heap[nxt]<heap[now])swap(heap[now],heap[nxt]);//如果不符合堆性质就换 
        else break;//否则就完成了 
        now=nxt;//往下一层继续向下交换 
    }
}

优先队列（堆）的STL实现

如果开了O2优化能使程序的编译效率大大提升
注意堆里面的大小，并非传统意义下的大小
定义一个优先队列：

首先你需要一个头文件：#include<queue>
priority_queue<int> q;//这是一个大根堆q
priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q

优先队列的操作：

q.top()//取得堆顶元素，并不会弹出
q.pop()//弹出堆顶元素
q.push()//往堆里面插入一个元素
q.empty()//查询堆是否为空，为空则返回1否则返回0
q.size()//查询堆内元素数量

额外提一下重载在堆的使用

bool operator < (node a , node b) {
    return a.w > b.w;
}

熟悉优先队列STL的人都知道，priority_queue默认大根堆，但如果我们想把他直接用去优化dijkstra肯定是不行的，所以我们可以以上的一段代码加入来将priority_queue变为小根堆，定义优先队列这样写priority_queue <node> q就行了</node>

当然，你也可以将重载运算符写在sruct里：

struct node {
    int id , w;
    bool operator < (const node &b) const {
        return w > b.w;
    }
}

如果你不使用重载运算符的话，就得这么写：

struct node {
    int id , w;
}
struct cmp {
    bool operator ()(node a , node b) {
        return a.w > b.w;
}
priority_queue <node , vector <node>  , cmp> q;

参考文献：
https://www.cnblogs.com/henry-1202/p/9307927.html
https://www.luogu.com.cn/blog/Jydon/wzx-AK-IOI