堆

6.堆

堆的基本操作（以小根堆为例，大根堆相反）

1. 插入一个数
2. 求集合当中的最小值
3. 删除最小值
4. 删除任意一个元素
5. 修改任意一个元素

基本结构是一颗完全二叉树。以小根堆为例，每个节点都要小于其左右两个子树种的所有节点，根节点即为集合中的最小值。

用数组来模拟存储一颗二叉树，采用二叉树层序遍历的方式作为数组的下标。若数组下标从0开始，若某个节点下标为x，则其左儿子下标为2x + 1，其右儿子下标为2x + 2。若数组下标从1开始，若某个节点下标为x，则其左儿子下标为2x，右儿子下标为2x + 1。此处讨论数组下标从1开始

以上所有操作都可以用下沉down和上升up两个操作来完成

• **down(x)：**注意传入的是数组下标。将x与其子结点进行比较，与两个子结点中最小且比x小的结点位置进行交换，不断下沉，直到合适的位置
• **up(x)：**注意传入的是数组下标。若x比父节点更小，则与父节点位置进行交换，不断上升到合适的位置

1.插入一个数

插入到数组末尾，对于这个新插入的数，使用up()不断向上调整

2.求集合当中的最小值

即根节点，数组首元素

3.删除最小值

交换堆顶和堆尾，然后堆的大小减一。即数组末尾元素覆盖数组首元素，然后对新的堆顶元素进行down向下调整

4.删除任意一个元素

交换当前元素和堆尾，然后堆的大小减一。即数组末尾元素覆盖当前元素，然后比较当前元素与被删除元素的大小，更大则向下调整，更小则向上调整。为了简化代码，去除判断，直接down和up操作都写上，只会执行一个

5.修改任意一个元素

直接修改，并且判断修改前后的新值与旧值大小关系，决定做down还是up。同删除任意元素操作，为了简化代码，去除判断，直接down和up操作都写上，只会执行一个。

6.给定一个序列，构造小顶堆：采用不断向下调整的方法构造。叶子节点无需再向下调整，只有非叶子结点需要向下调整，而最后一个非叶子结点编号为n/2(从1开始编号)，若从0开始编号为n/2-1(堆排序（完全二叉树）最后一个非叶子节点的序号是n/2-1的原因_完全二叉树最后一个非叶子结点的序号-CSDN博客)

down和up操作

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int h[N],lsize;//h[]存储结点，lszie为数组大小 从下标为1的位置开始存储
 
void down(int u){//传入的是数组下标
    int t=u;//承接u的值，进行遍历比较操作
    if(2*u<=lsize && h[2*u]<h[t]) t=2*u;//左子结点
    if((2*u+1)<=lsize && h[2*u+1]<h[t]) t=2*u+1;//右子结点
    if(t!=u){
        swap(h[u],h(t));
        down(t);//继续递归向下调整
    }
    
}
 
void up(int u){//这里也可以像down一样改成递归
    while(u/2 && h[u/2]>h[u]){
        swap(h[u/2],h[u]);
        u/=2;
    }
}
 
 

AcWing 838.堆排序

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int h[N],lsize;//h[]存储结点，lszie为数组大小 从下标为1的位置开始存储
 
void down(int u){//传入的是数组下标
    int t=u;//承接u的值，进行遍历比较操作
    if(2*u<=lsize && h[2*u]<h[t]) t=2*u;//左子结点
    if((2*u+1)<=lsize && h[2*u+1]<h[t]) t=2*u+1;//右子结点
    if(t!=u){
        swap(h[u],h(t));
        down(t);//继续递归向下调整
    }
    
}
 
int mian(){
    int n,m;
    cin>>n>>m;
    lsize=n;
    for(int i=1;i<=n;i++) cin>>h[i];
    //构造堆
    for(int i=n/2;i;i--) down(i);
    while(m--){
        cout<<h[1]<<" ";//最小的数即为堆顶元素
        //调整堆
        h[1]=h[lsize];
        lsize--;
        down(1);
    }
    
}

AcWing 839.模拟堆

实现思路：除了基本的down和up操作，这里还要求删除和修改第k个数，因此需要数组来记录数的下标和插入次序的关系

• 数组ph[k]=i：表示第k个插入的数的数组下标
• 数组hp[i]=k：表示数组下标为i的数是第几次插入的

每次交换不再是单纯的交换值，而是需要交换对应关系，即ph[]和hp[]数组的映射关系也要修改

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N=1e6+10;
int h[N],lsize;
int hp[N],ph[N];//下标和插入次序的关系
 
//重新编写交换操作 因为不再是单纯的值交换
void heap_swap(int a,int b){//依旧传入的是下标
    swap(ph[hp[a]],ph[hp[b]]);//交换下标
    swap(hp[a],hp[b]);//交换插入次序
    swap(h[a],h[b]);//交换值
}
 
void down(int u){
    int t=u;
    if(2*u<=lsize && h[2*u]<h[t]) t=2*u;//左子结点
    if((2*u+1)<=lsize && h[2*u+1]<h[t]) t=2*u+1;//右子结点
    if(t!=u){
        heap_swap(h[u],h(t));
        down(t);//继续递归向下调整
    }
    
}
 
void up(int u){//这里也可以像down一样改成递归
    while(u/2 && h[u/2]>h[u]){
        heap_swap(h[u/2],h[u]);
        u/=2;
    }
}
 
int main() {
    int n,m=0;//m记录插入次序 即第几次插入
    cin>>n;
    while(n--)
    {
        char op[10];
        cin>>op;
        if(!strcmp(op,"I"))//插入一个数
        {
            int x;
            cin>>x;
           	h[++lsize]=x;
            ph[m++]=lsize;
            hp[lsize]=m;
            up(lsize);
        }
        else if(!strcmp(op,"PM"))//输出最小值
        {
            cout<<h[1]<<endl;
        }
        else if(!strcmp(op,"DM"))//删除最小值
        {
            heap_swap(1,lsize);
            lsize--;
            down(1);
        }
        else if(!strcmp(op,"D"))//删除第k个数
        {
            int k;
            cin>>k;
           	k=ph[k];
            heap_swap(k,lsize);
            lsize--;
            down(k),up(k);//省去判断，只会执行一个
        }
        else//修改第k'个数
        {
            int k,x;
            cin>>k>>x;
            k=ph[k];
            h[k]=x;
            down(k),up(k);//省去判断，只会执行一个
        }
    }
    return 0;
}