[数据结构与算法]堆（数组实现）

堆

存储方式

用一维数组来存储一棵树。
从数组下标1开始存储，对于下标为$x$的元素，其左孩子的下标为$2x$，右孩子的下标为$2x+1$

两个基本操作

• down(x)
  从第x个结点处向下调整二叉树，使得该二叉树再次满足堆的定义。例如在小根堆中若堆顶元素变大了，则需要逐步将该元素向下移动，直至到达一个合适的位置。

void down(int r)
{
    int min = r; //用min存储根结点、左孩子、右孩子 这3个结点中最小的结点下标
    if (r * 2 <= size && h[r * 2] < h[min]) min = r * 2; //如果左孩子存在且较小，则修改min值
    if (r * 2 + 1 <= size && h[r * 2 + 1] < h[min]) min = r * 2 + 1; //如果右孩子存在且较小，再修改min值
    if (min != r) //此时min为三者中最小的那个结点的下标。若min不是根结点，说明需要进行调整。
    {
        swap(h[min], h[r]); //交换
        down(min); //继续向下调整
    }
}

• up(x)
  从第x个结点处向上调整二叉树，使得该二叉树再次满足堆的定义

void up(int r)
{
    while (r / 2 > 0 && h[r / 2] > h[r]) //该结点存在父结点且父结点要大于该结点
    {
        swap(h[r / 2], h[r]); //交换
        r /= 2; //上移
    }
}

可以实现的功能

建立堆

down(x)、up(x)的时间复杂度均为$O(logn)$，以建立含n个元素的小根堆为例，若每插入一个元素就down一次，则建堆的时空复杂度为$O(nlogn)$。
此处先建立数组，再将数组转化为堆，从二叉树的倒数第2层的位置开始down，使建堆过程的时间复杂度优化为$O(n)$

for (int i = 1; i <= n; i ++) cin >> h[i]; //存入数组中
size = n; //初始化
for (int i = n / 2; i >= 1; i --) down(i); //将数组转化为堆

例题1：堆排序

#include <iostream>
using namespace std;

const int N = 100010;
int h[N], siz;//size为堆中的元素个数，同时也是最后一个元素的下标

void down(int r)
{
    int min = r; //用min存储根结点、左孩子、右孩子 这3个结点中最小的结点下标
    if (r * 2 <= siz && h[r * 2] < h[min]) min = r * 2; 
    if (r * 2 + 1 <= siz && h[r * 2 + 1] < h[min]) min = r * 2 + 1; 
    if (min != r)
    {
        swap(h[min], h[r]); 
        down(min);
    }
}
int main()
{
    int m, n;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];//读入数组
    siz = n;//初始化
    for (int i = n / 2; i >= 1; i --) down(i);//将数组转化为堆

    while (m --) //不断地输出堆顶元素，再调整堆
    {
        cout << h[1] << ' ';
        h[1] = h[siz];
        siz --;
        down(1);
    }
    return 0;
}

带映射的堆

有时我们需要记录第k个插入的数是什么，此时便需要再维护两个一维数组ph和hp。
ph[k] = i表示第k个插入的元素在堆中的下标为i；hp[i] = k表示堆中下标为i的元素是第k个插入的。 ph中存的是下标，hp中存的是插入顺序，这两个数组互相映射。

此时若想要交换堆中的两个元素，我们不仅要交换这两个元素的值，还要修改对应的hp、ph信息。

void heap_swap(int a, int b) //传入两个下标a，b，交换这两个结点
{
    swap(ph[hp[a]], ph[hp[b]]); //修改第k个插入的元素的下标为交换之后的下标
    swap(hp[a], hp[b]); //修改该位置的元素的插入序号
    swap(h[a], h[b]); //最后进行结点值的交换
}

函数down、up中的swap也要改为heap_swap

插入元素

void insert(int x)
{
	h[++ siz] = x; //先插入至数组中
	cnt ++; //记录该元素是第几个插入的
	ph[cnt] = siz, hp[siz] = cnt; //记录该结点的信息
	up(siz); //向上调整，将数组调整为堆
}

删除堆顶元素

	heap_swap(1, siz); //将末尾元素覆盖堆顶
    siz --; //元素数目减一（删除末尾元素）
    down(1); //自顶而下调整堆

删除第k个插入的元素

void del(int k)
{
    int t = ph[k]; //找到第k个插入的元素的下标
    heap_swap(t, siz); //将末尾元素覆盖该元素
    siz --; //元素数目减一（删除末尾元素）
    down(t), up(t); //不管三七二十一，上下都调整一次
}

修改第k个插入的元素

void modify(int k, int x)
{
    int t = ph[k]; //找到第k个插入的元素的下标
    h[t] = x; //修改为x
    down(t), up(t); //调整堆
}

例题2，模拟堆

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

const int N = 100010;
int h[N], hp[N], ph[N], siz;

void heap_swap(int a, int b) //传入两个下标a，b，交换这两个结点
{
    swap(ph[hp[a]], ph[hp[b]]); //修改第k个插入的元素的下标为交换之后的下标
    swap(hp[a], hp[b]); //修改该位置的元素的插入序号
    swap(h[a], h[b]); //最后进行结点值的交换
}
void down(int r)
{
    int min = r; //用min存储根结点、左孩子、右孩子 这3个结点中最小的结点下标
    if (r * 2 <= siz && h[r * 2] < h[min]) min = r * 2; //如果左孩子存在且较小，则修改min值
    if (r * 2 + 1 <= siz && h[r * 2 + 1] < h[min]) min = r * 2 + 1; //如果右孩子存在且较小，再修改min值
    if (min != r) //此时min为三者中最小的那个结点的下标。若min不是根结点，说明需要进行调整。
    {
        heap_swap(min, r); //传入两个下标，交换结点
        down(min); //继续向下调整
    }
}   
void up(int r)
{
    while (r / 2 > 0 && h[r / 2] > h[r]) //该结点存在父结点且父结点要大于该结点
    {
        heap_swap(r / 2, r); //传入两个下标，交换结点
        r /= 2; //上移
    }
}
int main()
{
    int n, cnt = 0; //cnt记录插入结点的序号
    cin >> n;
    while (n --)
    {
        char op[5];
        scanf("%s", op); //读入题目操作
        if (strcmp(op, "I") == 0) //插入操作：将x添加到堆中
        {
            int x;
            cin >> x;
            h[++ siz] = x; //先插入至数组中
            cnt ++; //记录该元素是第几个插入的
            ph[cnt] = siz, hp[siz] = cnt; //记录该结点的信息
            up(siz); //向上调整，将数组调整为堆
        }
        else if (strcmp(op, "PM") == 0) cout << h[1] << endl; //输出堆顶元素
        else if (strcmp(op, "DM") == 0) //删除堆顶元素
        {
            heap_swap(1, siz); //将末尾元素覆盖堆顶
            siz --; //元素数目减一（删除末尾元素）
            down(1); //自顶而下调整堆
        }
        else if (strcmp(op, "D") == 0) //删除第k个插入的元素
        {
            int k;
            cin >> k;
            int t = ph[k]; //找到第k个插入的元素的下标
            heap_swap(t, siz); //将末尾元素覆盖该元素
            siz --; //元素数目减一（删除末尾元素）
            down(t), up(t); //不管三七二十一，上下都调整一次
        }
        else //将第k个插入的元素修改为x
        {
            int k, x; 
            cin >> k >> x;
            int t = ph[k]; //找到第k个插入的元素的下标
            h[t] = x; //修改为x
            down(t), up(t); //调整堆
        }
    }
    return 0;
}

关注博主即可阅读全文