【基础算法模板】堆

堆的结构

一个完全二叉树

堆的性质（小根堆为例）：

每一个节点的值小于等于它左右子节点的值，根节点的值是最小的。

堆的存储

完全二叉树都可以转换成一维数组存储。

下标 x 的左儿子的位置：2x

下标 x 的右儿子的位置：2x + 1

堆的两个基础操作（小根堆为例）：

• down( x )，下沉操作，如果把一个节点的值变大了就要向下调整

首先判断 6 要比它的左右子节点的值都大， 6 要与左右子节点中较小的 3 交换

重复操作直到没有满足条件的子节点元素为止

• up( x )，上浮操作，如果把一个节点的值变小了就要向上调整

将原来的 5 该值为 2，只需要将 2 与它的父节点 4 比较，2 比 4 小，要交换

以此类推，直到满足小根堆特性为止。

手写堆的五个操作：

• 手写堆的五个操作都可以通过堆的两个基础操作的排列组合实现。
• 用 heap 表示堆，size 表示堆的大小。
• 元素从下标 1 开始算。因为 x == 0，2x == 0，2x + 1 == 1，以 0 开始的根节点的位置会与其左儿子的位置产生冲突，而右儿子的位置却占用了左儿子的位置，需要手动修改不方便。

模板：

// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;// 交换两个点，及其映射关系
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 (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){heap_swap(u, t);down(t);}
}void up(int u)
{while (u / 2 && h[u] < h[u / 2]){heap_swap(u, u / 2);u >>= 1;}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

测试样例1：

• 建堆有两种方式，假设有 n 个元素
• 第一种，遍历每个元素，对每个元素进行 down 操作，时间复杂度是 O(n * logn)
• 第二种，遍历每个元素先存入数组 h[ ] 里，时间复杂度为 O(n)；然后对除去最后一层以上的所有节点进行 down 操作，时间复杂度为 O(n)；总时间复杂度为 O(n)。这样做可行的原因是，其他层元素调整好后，最后一层自然而然就不用调整了，最后一层是在其他层元素调整的过程中调整好的。
  • 证明一下为什么是 O(n)：
  • 倒数第二层有 n / 4 个节点，倒数第三层有 n / 8 个节点，倒数第四层有 n / 16 个节点……
  • 倒数第二层进行 down 最多会向下操作1次，倒数第三层进行 down 最多会向下操作2次....
  • 时间复杂度就是 = n / 4 * 1 + n / 8 * 2 + n / 16 * 3…… 
• 

/*
题目描述；输入一个长度为n的整数数列,从小到大输出前m小的数。输入格式： 
第一行包含整数n和m。  
第二行包含n个整数，表示整数数列。 输出格式： 
共一行，包含m个整数，表示整数数列中前m小的数。  数据范围：
1 <= m <= n <= 10e5,
1 <= 数列中元素 <= 10e9 输入样例：
5 3
4 5 1 3 2 输出样例：
1 2 3 
*/ #include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n, m;
int h[N], size;void down(int u){int t = u;if(u * 2 <= size && h[u * 2] < h[t])	t = u * 2;if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t])	t = u * 2 + 1;if(u != t){swap(h[u], h[t]);down(t);}
}void up(int u){while(u / 2 && h[u / 2] > h[u]){swap(h[u / 2], h[u]);u /= 2;}
} int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i ++)	scanf("%d", &h[i]);size = n;// 建堆，时间复杂度 O(N) for(int i = n / 2; i; i --)	down(i);while(m --){printf("%d ", h[1]);h[1] = h[size];size --;down(1);}return 0;
}

测试样例2：

• 解 heap_swap 函数
• ph[N]：映射堆中位置到插入索引。hp[N]：映射插入索引到堆中位置。
• swap(ph[hp[a]], ph[hp[b]]);
  • hp[a]：获取堆中位置为 a 的元素在堆数组 h 中的实际索引。
  • ph[hp[a]]：获取堆中实际索引为 hp[a] 的元素对应的插入索引。
  • ph[hp[b]]：获取堆中实际索引为 hp[b] 的元素对应的插入索引。
  • 这一行代码交换了两个元素在 ph 数组中的值。ph 数组记录的是堆中每个位置的原始插入索引，所以在交换两个位置的元素时，需要同步更新这些原始插入索引的映射关系。
• swap(hp[a], hp[b]);
  • hp[a] 和 hp[b]：记录的是堆中位置 a 和 b 在堆数组 h 中的实际索引。
  • 这行代码交换了 hp 数组中的值。hp 数组用于记录每个插入索引在堆中的实际位置，因此交换两个位置的元素时，需要同步更新它们在 hp 数组中的位置。
• swap(h[a], h[b]);
  • h[a] 和 h[b]：这行代码直接交换了堆数组 h 中位置 a 和 b 的值，即交换了两个元素的实际值。

• heap_swap 函数执行了三个主要操作来保证两个堆元素交换的一致性：

  • 更新映射数组 ph 以确保插入索引的映射关系正确。

  • 更新映射数组 hp 以确保堆中位置的映射关系正确。
  • 实际交换堆数组 h 中的值。

/*
题目描述；
维护一个集合，初始时集合为空，支持以下几种操作：
1、"I x"，插入一个数 x; 
2、"PM"，输出当前集合中的最小值 
3、"DM"，删除当前集合中的最小值（当集合不唯一时，删除最早插入的最小值） 
4、"D k"，删除第 k 个插入的数 
5、"C k x"，修改第 k 个插入的数，将其变为 x 现在要进行 N 次操作，对于所有第二个操作，输出当前集合的最小值 输入格式： 
第一行包含整数 N  
接下来N行，每行包含一个操作指令，操作指令为 "I x","PM","DM","D k","C k x"中的一种输出格式： 
对于每个输出指令"PM"，输出一个结果，表示当前集合中的最小值 
每个结果占一行  数据范围：
1 <= N <= 10e5
-10e9 <= x <= 10e9输入样例：
8
I  -10
PM
I -10
D 1
C 2 8
I 6
PM
DM输出样例：
-10
6
*/ #include <iostream>
#include <algorithm>
#include <string.h>using namespace std;const int N = 100010;// ph[j] == k，第 j 个插入的点在堆里的下标是 k 
// hp[k] == j，堆里下标是 k 的点对应是第 j 个插入的
int h[N], ph[N], hp[N], size;	// 交换两个点，及其映射关系
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(u * 2 <= size && h[u * 2] < h[t])	t = u * 2;if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t])	t = u * 2 + 1;if(u != t){heap_swap(u, t);down(t);}
}void up(int u){while(u / 2 && h[u / 2] > h[u]){heap_swap(u / 2, u);u /= 2;}
} int main(){int n, m = 0;scanf("%d", &n);while(n --){char op[10];int k, x;scanf("%s", op);if(!strcmp(op, "I")){scanf("%d", &x);size ++;m ++;ph[m] = size, hp[size] = m;h[size] = x;up(size);}else if(!strcmp(op, "PM"))	printf("%d\n", h[1]);else if(!strcmp(op, "DM")){heap_swap(1, size);size --;down(1);}else if(!strcmp(op, "D")){scanf("%d", &k);k = ph[k];heap_swap(k, size);size --;down(k), up(k);}else{scanf("%d%d", &k, &x);k = ph[k];h[k] = x;down(k), up(k);}}return 0;
}