堆
概念详解
基本结构
堆是一颗完全二叉树
小根堆：每个节点都小于等与其子节点的值
存储方式：用一个一维数组来存；x的左儿子是2x，右儿子是2x+1
堆的两个核心操作：
- down(u)——下沉： 比较 u 与它的两个儿子，若某个儿子比 u 更小（小根堆），就与最小的儿子交换，然后递归下去，直到满足堆性质。用于”根变大了”的修复，例如删除堆顶后用最后一个元素补位后 down(1)。
- up(u)——上浮： 若 u 比父节点小，就与父节点交换并继续向上，直到根或父节点更小。用于插入新元素（插到末尾再 up）或某元素变小后的修复。
五种基本操作都建立在这两个操作之上（见上面代码）：插入 = 末尾插入 + up；求最小值 = 堆顶 heap[1]；删除最小值 = 末尾元素补堆顶 + down(1)；删除/修改任意元素 = 先用末尾元素覆盖 k 位置，再同时 down(k) 和 up(k)——因为不知道新值会变大还是变小，两个操作最多只有一个真正生效。
在建堆的时候从n/2的地方开始down即可，这样建堆的时间复杂度相比于朴素建堆的方式（nlogn）只需要（n甚至小于n的时间复杂度）
为什么从 n/2 开始向下 down 就能 O(n) 建堆？ 编号 > n/2 的节点都是叶子，本身已是合法的堆；从最后一个非叶节点 n/2 开始，自底向上依次 down，每个节点只需要关心它的两个儿子。复杂度为 O(n)：第 h 层有约 n/2^h 个节点、每个最多下降 h 层，求和后收敛于 O(n)，比”逐个插入、每次 up O(log n)“的 O(n log n) 建堆更快。
删除/修改任意元素时的 ph、hp 映射（模拟堆）： 题目要求”按插入顺序”删除或修改第 k 个插入的数，但堆中元素的位置会随 down/up 不断变化，于是需要两套互相映射的数组：ph[k] = 第 k 个插入的数在堆中的位置，hp[pos] = 堆中位置 pos 上是第几个插入的数。每次交换堆中两个位置时，必须同时同步交换 ph 和 hp，这就是 heap_swap 函数三连交换的原因。
例题：堆排序
题目描述
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。 第二行包含 n 个数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示数列中前 m 小的数。
数据范围
- 1 ≤ m ≤ n ≤ 10⁵
- 1 ≤ 数列中元素 ≤ 10⁹
import java.io.*;import java.util.*;public class Main{ static int[] h = new int[100010]; static int size = 0;
public static void down(int u){ int t = u; if(2*u <= size && h[2*u] < h[t]) t = 2*u; if(2*u + 1 <= size && h[2 * u +1] < h[t]) t = 2*u+1; if(u != t){ int temp = u; u = t; t = temp; down(t); } } public static void up(int u){ while(u / 2 > 0&& h[u/2] > h[u]){ int temp = h[u/2]; h[u/2] = h[u]; h[u] = temp; u = u/2; } } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); for(int i = 0;i < n ;i++){ st = new StringTokenizer(br.readLine()); h[i] = Integer.parseInt(st.nextToken()); } size = n; for(int i = n/2 ;i > 0;i--) down(i); while(m-- > 0){ System.out.print(h[1]); h[1] = h[size]; size--; down(1); } }}例题：模拟堆
模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
I x：插入一个数 x；PM：输出当前集合中的最小值；DM：删除当前集合中的最小值（当最小值不唯一时，删除最早插入的最小值）；D k：删除第 k 个插入的数；C k x：修改第 k 个插入的数，将其变为 x。现在要进行 N 次操作，对于所有第 2 个操作（即
PM），输出当前集合的最小值。输入格式：
第一行包含整数 N。 接下来 N 行，每行包含一个操作指令，操作指令为
I x、PM、DM、D k或C k x中的一种。输出格式：
对于每个输出指令
PM，输出一个结果，表示当前集合中的最小值。 每个结果占一行。
import java.io.*;import java.util.*;public class Main{ static int[] h = new int[100010]; static int size = 0; static int[] ph = new int[100010]; static int[] hp = new int[100010]; public static void down(int u){ int t = u; if(2*u <= size && h[2*u] < h[t]) t = 2*u; if(2*u + 1 <= size && h[2 * u +1] < h[t]) t = 2*u+1; if(u != t){ heap_swap(u,t); down(t); } } public static void heap_swap(int a , int b){ //交换ph int temp = ph[hp[a]]; ph[hp[a]] = ph[hp[b]]; ph[hp[b]] = temp; //交换hp temp = hp[a]; hp[a] = hp[b]; hp[b] = temp; //交换h temp = h[a]; h[a] = h[b]; h[b] = temp; } public static void up(int u){ while(u / 2 > 0 && h[u/2] > h[u]){ heap_swap(u / 2, u ); u = u/2; } } public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine().trim()); int m = 0; while(n -- > 0){ String[] op = br.readLine().trim().split("\\s+"); if(op[0].equals("I")){ int x = Integer.parseInt(op[1]); size ++; m ++; ph[m] = size; hp[size] = m; h[size] = x; up(size); }else if(op[0].equals("PM") ){ bw.write(h[1] + "\n"); }else if(op[0].equals("DM")){ heap_swap(1,size); size--; down(1); }else if(op[0].equals("D")){ int k = Integer.parseInt(op[1]); k = ph[k]; heap_swap(k,size); size--; down(k); up(k); }else{ int k = Integer.parseInt(op[1]); int x = Integer.parseInt(op[2]); k = ph[k]; h[k] = x; down(k); up(k); } } bw.flush(); }}如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时