堆（二叉堆）总结-创新互联

（1）小根堆（小堆、最小堆）

（2）大根堆（大堆、大堆）

（1）插入某个节点

（2）删除任意下标节点

（3）替换任意下标节点

堆的操作有up和down，down 和 up 都是针对下标进行的操作：

#include#include 
using namespace std;
const int N=100010;
int heap[N],size;

void down(int x){
    int t=x;
    if(2*x<=size && heap[t]>heap[2*x]) t=2*x; //前面的<=size是为了保证当前节点存在子节点
    if(2*x+1<=size && heap[t]>heap[2*x+1]) t=2*x+1;
    if(x!=t){
        swap(heap[x],heap[t]);
        down(t);
    }
}

void up(int x){
    while(x/2>0 && heap[x]>heap[x/2]){
        swap(heap[x],heap[x/2]);
        x/=2;
    }
}

int main()
{
    
    return 0;
}

放一道题目：         AcWing 838. 堆排序（已做笔记）

变形之后的堆与一般的堆的不同之处在于可以修改和删除第k（k表示顺序）个插入的节点元素，而不是下标为k的节点元素

#include#include 
using namespace std;
const int N=100010;
int heap[N],size;
int cnt;//用于编号是第cnt个插入的节点
int ph[N];//表示第k个插入的节点在堆中的下标是多少
int hp[N];//表示堆中下标对应的是第几个插入的节点

void heap_swap(int a,int b){//a和b都表示下标
    swap(heap[a],heap[b])；
    swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a],hp[b]);
}

void down(int x){
    int t=x;
    if(2*x<=size && heap[t]>heap[2*x]) t=2*x;
    if(2*x+1<=size && heap[t]>heap[2*x+1]) t=2*x+1;
    if(x!=t){
        heap_swap(x,t);//注意：这里使用的是下标进行操作，而不是像之前那样只交换值
        down(t);
    }
}

void up(int x){
    while(x/2>0 && heap[x]

对于变形之后的堆，在进行节点的删除和修改的时候都不能只是单纯的进行值覆盖了，而是要用heap_swap()函数对值、下标、第cnt个插入的节点全部进行交换；

放一道题目：        AcWing 839. 模拟堆（一定要认真看这道题！）

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧