当前位置：首页 > article >正文

Acwing 堆

article 2024/9/20 15:09:19

堆的基本操作（以小根堆为例）

插入一个数；
求集合当中的最小值；
删除最小值；
删除任意一个元素；
修改任意一个元素；
构造堆

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

用数组模拟存储一棵二叉树，采用二叉树层序便利的方式作为数组的下标，此处讨论数组下标从1开始，若某个节点的下标为x，则其左儿子下标为2x，右儿子下标为2x+1.以上所有操作都可以用下沉down和上升up两个操作来完成：

down(x):传入数组下标x。将x与其子节点进行比较，与两个字节点中最小且比x小的节点位置进行交换，不断下沉，知道合适的位置；

up(x):传入数组下标x。若x比父节点更小，则与父节点进行交换，不断上升到合适的位置；

using namespace std;
const int N=1e6+10;
int h[N],lsize;//h[]存储结点，lsize为数组大小 从下标为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;
    }
}

下面我们使用这两个操作，叙述一下上述5个基本操作如何实现：

插入一个数：插入到数组末尾，对于这个新插入的数，使用up()不断向上调整；
求集合当中的最小值：即根节点，数组首元素；
删除最小值：交换堆顶和堆尾，然后堆的大小减一，然后堆新的堆顶元素进行down向下调整；
删除任意一个元素：交换当前元素和堆尾，堆的大小减一，然后可以去除判断，直接down操作和up操作，其实只会执行其中之一；
修改任意一个元素：先找到需要修改的数字和位置，然后直接修改，下面直接down和up，维护最小堆、；
构造堆：采用不断向下调整的方法构造。叶子节点无需再向下调整，只有非叶子结点需要向下调整，而最后一个非叶子结点编号为n/2(从1开始编号)。

Acwing 838.堆排序

输入样例：

5 3

4 5 1 3 2

输出样例：

1 2 3

具体代码实现（详解版）：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6+10;

int h[N],lsize;//h[]存储节点，lsize为数组大小，从下标为1开始存储

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){ //发生改变
       swap(h[u],h[t]);
       down(t);//继续递归向下调整
    }
}

int main(){
    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);
    }
    
    return 0;
}

Acwing 839. 模拟堆

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

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

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

下面完整给出模拟堆的板子：

const int N = 1e6+10; 

int h[N], lsize; // h[]用于存储堆元素，lsize为当前堆的大小，从下标为1开始存储

// ph[k] = i: 表示第k个插入的数的数组下标为i
// hp[i] = k: 表示数组下标为i的数是第k次插入的
int hp[N], ph[N];

// 交换堆中两个位置a和b的元素，并维护ph和hp数组的映射关系
void head_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]); // 交换下标
    swap(hp[a], hp[b]);         // 交换插入次序
    swap(h[a], h[b]);           // 交换堆中实际的元素值
}

// 下沉操作，传入数组下标u，使得堆的性质恢复（最小堆）
void down(int u){
    int t = u; // t是当前要比较的节点
    // 如果左子节点存在且小于当前节点，更新t为左子节点下标
    if(2 * u <= lsize && h[2 * u] < h[t]) t = 2 * u; 
    // 如果右子节点存在且小于当前最小节点，更新t为右子节点下标
    if(2 * u + 1 <= lsize && h[2 * u + 1] < h[t]) t = 2 * u + 1; 
    // 如果t发生改变，说明需要调整堆
    if(t != u){ 
       head_swap(u, t); // 交换节点
       down(t);         // 递归调整子节点
    }
}

// 上浮操作，传入数组下标u，维护最小堆的性质
void up(int u){
    // 当父节点存在且父节点的值大于当前节点时，进行交换
    while(u / 2 && h[u / 2] > h[u]){
        head_swap(u, u / 2); // 交换当前节点和父节点
        u /= 2;              // 继续向上调整父节点
    }
}

本题的具体代码实现（详解版）：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1e6+10; 

int h[N], lsize; // h[]用于存储堆元素，lsize为当前堆的大小，从下标为1开始存储

// ph[k] = i: 表示第k个插入的数的数组下标为i
// hp[i] = k: 表示数组下标为i的数是第k次插入的
int hp[N], ph[N];

// 交换堆中两个位置a和b的元素，并维护ph和hp数组的映射关系
void head_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]); // 交换下标
    swap(hp[a], hp[b]);         // 交换插入次序
    swap(h[a], h[b]);           // 交换堆中实际的元素值
}

// 下沉操作，传入数组下标u，使得堆的性质恢复（最小堆）
void down(int u){
    int t = u; // t是当前要比较的节点
    // 如果左子节点存在且小于当前节点，更新t为左子节点下标
    if(2 * u <= lsize && h[2 * u] < h[t]) t = 2 * u; 
    // 如果右子节点存在且小于当前最小节点，更新t为右子节点下标
    if(2 * u + 1 <= lsize && h[2 * u + 1] < h[t]) t = 2 * u + 1; 
    // 如果t发生改变，说明需要调整堆
    if(t != u){ 
       head_swap(u, t); // 交换节点
       down(t);         // 递归调整子节点
    }
}

// 上浮操作，传入数组下标u，维护最小堆的性质
void up(int u){
    // 当父节点存在且父节点的值大于当前节点时，进行交换
    while(u / 2 && h[u / 2] > h[u]){
        head_swap(u, u / 2); // 交换当前节点和父节点
        u /= 2;              // 继续向上调整父节点
    }
}

int main(){
    int n, m = 0; // n表示操作次数，m记录插入的次序
    cin >> n;     
    while(n --){  
        char op[10]; // 存储操作符的字符串
        cin >> op;
        if(!strcmp(op, "I")){ // 插入操作
            int x;
            cin >> x;
            lsize++, m++;     // 增加堆的大小并更新插入次序
            h[lsize] = x;     // 将新元素放入堆的最后
            ph[m] = lsize;    // 更新ph数组，记录第m次插入的元素在lsize位置
            hp[lsize] = m;    // 更新hp数组，记录lsize位置的元素是第m次插入
            up(lsize);        // 调用上浮操作，维护最小堆性质
        }
        else if(!strcmp(op, "PM")){ // 输出最小值
            cout << h[1] << endl;   // 最小值在堆顶，即h[1]
        }
        else if(!strcmp(op, "DM")){ // 删除最小值
            head_swap(1, lsize);    // 将堆顶元素与最后一个元素交换
            lsize--;                // 删除最后一个元素（即原来的最小值）
            down(1);                // 调用下沉操作，维护最小堆性质
        }
        else if(!strcmp(op, "D")){ // 删除第k个插入的数
            int k;
            cin >> k;
            k = ph[k];              // 通过ph数组找到第k个插入的数在堆中的位置
            head_swap(k, lsize);    // 将该元素与堆的最后一个元素交换
            lsize--;                // 删除最后一个元素
            down(k), up(k);         // 调整堆，使得堆的性质恢复
        }
        else{ // 修改第k个插入的数为x
            int k, x;
            cin >> k >> x;
            k = ph[k];              // 通过ph数组找到第k个插入的数在堆中的位置
            h[k] = x;               // 修改该位置的值为x
            down(k), up(k);         // 调用上浮和下沉操作，维护最小堆的性质
        }
    }
    
    return 0;
}

好的，以上就是用数组模拟堆的操作，还是有一定得到技巧性，对于此类型的题目要多加练习。

查看全文

http://www.kler.cn/news/311970.html