堆

简介

堆是一种数据结构，主要只是三个操作：

加入一个数字
获取最大值
删除最大值
部分实现方法，还支持删除任意值。

基本实现

数组存储完全二叉树：
$1$ 号点是根节点，节点 $i$ 的两个孩子是 $2i$ 和 $2i+1$ 。

$0$ 号点是根节点，节点 $i$ 的两个孩子是 $2i+1$ 和 $2i+2$ 。

堆要保证任意节点大于等于自己的两个孩子

任意节点小于等于自己的父亲节点

如果不满足，需要调整

如果想自己实现一个堆，需要实现向上调整函数up和向下调整函数down。

向上调整函数：
如果当前节点是根节点，或者当前节点小于等于自己的父亲节点，那么退出。
如果当前节点大于自己的父亲节点，那么和父亲节点交换，并且继续向上调整。

// 小根堆
void up(int x) {
	while (x > 1) { // 如果自己不是根节点
		if (a[x] < a[x / 2]) { // 如果自己小于自己的父亲节点
			swap(a[x], a[x / 2]); // 交换自己和自己的父亲节点
			x /= 2; // 自己变成自己的父亲节点
		} else {
			break; // 自己大于等于自己的父亲节点，退出
		}
	}
}

向下调整函数：
如果当前节点没有孩子，那么推出
如果当前节点，小于两个孩子节点中较大的一个，那么和孩子节点交换，并继续继续向下调整

// 小根堆
void down(int x) {
	while (2 * x <= n) { // 如果自己有孩子节点
		int p = 2 * x; // 初始化成左孩子
		if (p + 1 <= n && a[p + 1] < a[p]) { // 如果自己有右孩子，并且右孩子更小
			p++; // 更新成右孩子
		}
		if (a[x] > a[p]) { // 如果自己的孩子比自己小
			swap(a[x], a[p]); // 交换自己和自己的孩子节点
			x = p; // 自己变成自己的孩子节点
		} else {
			break; // 自己小于等于自己的孩子节点，那么退出
		}
	}
}

建堆

一个最简单的实现方法，当然是把每个元素依次加入堆，总时间复杂度 $O(n \log n)$

void makeheap() {
    for (int i = 1; i <= n; i++) {
        up(i);
    }
}

另一个方法是，从 $n/2$ 向前，每个元素向下调整，总时间复杂度 $O(n)$

void makeheap() {
    for (int i = n / 2; i >= 1; i--) {
        down(i);
    }
}

加入一个数字

把新加入的数字放在末尾，向上调整即可。

void push(int x) {
    a[++n] = x;
    up(n);
}

获取最大值

直接获取最大值即可。

int top() {
    return a[1];
}

删除最大值

交换堆顶（要删除的数字）和最后一个节点，对堆顶进行向下调整。

void pop() {
    swap(a[1], a[n--]);
    down(1);
}

删除任意值

堆并不支持删除任意值，如果希望支持，需要记录每个值在哪个位置上。
然后和删除最大值类似，把要删除的节点和最后一个节点交换，然后向下调整，向上调整。

代码

#include <bits/stdc++.h>
using namespace std;
int a[30], n;
void up(int p) {
    while (p > 1 && a[p] > a[p / 2]) {
        swap(a[p], a[p / 2]);
        p = p / 2;
    }
}
void down(int p) {
    while (p * 2 <= n) {
        int u = p * 2;
        if (u + 1 <= n && a[u + 1] > a[u]) {
            u++;
        }
        if (a[u] > a[p]) {
            swap(a[p], a[u]);
            p = u;
        } else {
            break;
        }
    }
}
void makeheap() {
    for (int i = n / 2; i >= 1; i--) {
        down(i);
    }
}
void push(int x) {
    a[++n] = x;
    up(n);
}
int top() {
    return a[1];
}
void pop() {
    swap(a[1], a[n--]);
    down(1);
}
int main() {
    n = 10;
    for (int i = 1; i <= n; i++) {
        a[i] = rand();
    }
    makeheap();
    for (int i = 1; i <= 10; i++) {
        push(rand());
    }
    while (n > 0) {
        cout << top() << endl;
        pop();
    }
    return 0;
}

相当于生成 $20$ 个随机数，并从大到小输出。

STL

STL中有make_heap，push_heap，pop_heap三个函数，可以帮助实现堆。

因为堆不支持删除的缘故，经常被set/multiset取代。
priority_queue 是唯一一个的数据结构，默认情况下比较大的数值在前面。

make_heap，push_heap，pop_heap 默认是大根堆。
priority_queue 是用 vector 和这3个函数实现的。

其他

堆排序是三种 $O(n \log n)$ 排序算法（快速排序，归并排序）中唯一空间复杂度是 $O(1)$ 。

有许多用堆的题目，可以被优化成使用队列，比如合并石子，蚯蚓。

大部分用Dijkstra算法求最短路的题目，都需要使用优先队列。

参考题目

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

https://www.luogu.com.cn/problem/P1090

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 $n-1$ 次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 $1$ ，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 $3$ 种果子，数目依次为 $1$ ， $2$ ， $9$ 。可以先将 $1$ 、 $2$ 堆合并，新堆数目为 $3$ ，耗费体力为 $3$ 。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 $12$ ，耗费体力为 $12$ 。所以多多总共耗费体力 $=3+12=15$ 。可以证明 $15$ 为最小的体力耗费值。

输入格式

共两行。
第一行是一个整数 $n(1\leq n\leq 10000)$ ，表示果子的种类数。

第二行包含 $n$ 个整数，用空格分隔，第 $i$ 个整数 $a_i(1\leq a_i\leq 20000)$ 是第 $i$ 种果子的数目。

输出格式

一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 $2^{31}$ 。

样例 #1

样例输入 #1

3 
1 2 9

样例输出 #1

提示

对于 $30\%$ 的数据，保证有 $n \le 1000$ ：

对于 $50\%$ 的数据，保证有 $n \le 5000$ ；

对于全部的数据，保证有 $n \le 10000$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x, ans;
int main() {
	cin >> n;
	priority_queue<int, vector<int>, greater<int> > q;
	for (int i = 0; i < n; i++) {
		cin >> x;
		q.push(x);
	}
	for (int i = 1; i < n; i++) {
		int x = q.top();
		q.pop();
		int y = q.top();
		q.pop();
		ans += x + y;
		q.push(x + y);
	}
	cout << ans << endl;
}

题解

合并果子，用堆进行贪心

P4331 [BalticOI 2004]Sequence 数字序列

https://www.luogu.com.cn/problem/P4331

题目描述

给定一个整数序列 $a_1, a_2, ··· , a_n$ ，求出一个递增序列 $b_1 < b_2 < ··· < b_n$ ，使得序列 $a_i$ 和 $b_i$ 的各项之差的绝对值之和 $|a_1 - b_1| + |a_2 - b_2| + ··· + |a_n - b_n|$ 最小。

输入格式

第一行为数字 $n (1≤n≤10^6)$ ，接下来一行共有 $n$ 个数字，表示序列 $a_i (0≤a_i≤2×10^9)$ 。

输出格式

第一行输出最小的绝对值之和。

第二行输出序列 $b_i$ ，若有多种方案，只需输出其中一种。

样例 #1

样例输入 #1

5
2 5 46 12 1

样例输出 #1

47
2 5 11 12 13

提示

【数据范围】

40%的数据 $n≤5000$ ；

60%的数据 $n≤300000$ ；

100%的数据 $n≤1000000 , 0≤a_i≤2×10^9$ ；

题目来源： $Baltic$ $OI$ $2004$ $Day$ $1, Sequence$

感谢@TimeTraveller提供SPJ。

参考代码

题解

有一个用堆很简单的方法，可以参考CF 13C和CF 713C

CF865D Buy Low Sell High

https://codeforces.com/problemset/problem/865/D
https://www.luogu.com.cn/problem/CF865D

参考代码

#include <bits/stdc++.h>
using namespace std;
priority_queue<int> q;
int n, x;
long long z;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &x);
		q.push(-x);
		q.push(-x);
		z += x + q.top();
		q.pop();
	}
	printf("%lld\n", z);
	return 0;
}

题解

一个用堆贪心的题目