堆的基本操作

堆的基本操作
1. heap.top()
2. heap.pop(x)
3. heap.push()
4. heap.remove(k) // 删除第k个节点
5. heap.alter(k,x) // 修改第k个节点为x

用数组来实现堆的存储方式：用x表示父节点,2*x为左孩子，2*x+1为右孩子

若实现的是小根堆，则存在父节点>左孩子节点，父节点>右孩子节点

我们定义两个操作来实现堆

down操作

down操作主要用来将当前节点向下移动到正确的位置

void down(int  x){
    int u=x;
    if(2*x<=si && heap[2*x]<heap[x])u=2*x;
    if(2*x+1<=si && heap[2*x+1]<heap[u])u=2*x+1;   // 这两行主要用于寻找左右节点的最小值，这样写可以减少代码的行数
    if(u!=x){
        swap(heap[u],heap[x]);
        down(u);  // 递归扫描孩子节点
    }
}

up操作

up 操作主要用于将当前节点上升到正确位置

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

显然down与up在同一节点只会同时一个有效

模拟heap.top()

直接返回heap[1]就行了

int heap_top(){
    return heap[1];  
}

模拟heap.pop()

void heap_pop(){
    swap(heap[1],heap[size]);  // 交换最小值与最后一个节点
    size--;                 // 相当于删除最小值
    down(1);                // 将其调整到正确的位置
}

模拟heap.push()

void heap_push(int x){
    heap[++size]=x;         // 增加一个值为x的节点
    up(size);               // 将该节点上升到正确的位置
}

模拟heap.remove(k)

void heap_remove(int k){
    h[k]=h[size];           // 修改当前节点为最后一个节点
    size--;                 // 删除当前节点
    down(k);                
    up(k);                  // down(k) 与 up(k) 同一时间最多只会有一个有效，不用特判断
}

模拟heap.alter(k,x)

void heap_alter(int k,int x){
    heap[k]=x;              // 修改当前节点的值
    down(k);                
    up(k);                  // down(k) 与 up(k) 同一时间最多只会有一个有效，不用特判断
}