堆排问题

GitHub跳转原题关系图返回列表

把权值换成序号后每结点 4 位压成 64 位状态,在 M 种交换构成的排列图上 BFS,首次生成合法大根堆排列的层数即最少交换次数。

OJ: roj

题目 ID: 1689

难度:提高

标签:搜索BFS状态压缩位运算python

创建: 2026-10-07 15:54

更新: 2026-10-07 15:54

形式化题目

给定一棵 NN 个结点的二叉树,结点 ii 有互不相同的点权 FiF_i,以及 MM 种交换方式 (uj,vj)(u_j, v_j):一次操作可以任选一种方式,交换 uju_j 与 vjv_j 当前持有的点权。 同一种方式可以反复使用。

要求用最少的操作次数,把点权的分布变成一棵大根堆:对每个非根结点 ii, 其点权严格大于子树中所有结点的点权;等价地,Fi>Fp(i)F_i > F_{p(i)} 对每个 ii 成立, 其中 p(i)p(i) 是 ii 的父亲(根的 pp 为 00)。

求最少操作次数。数据保证有解。

把"点权的分布"看成一个排列,题目就变成一句纯图论的话:

  • 状态:把权值分配到各结点的方案,共 N!N! 种可能;
  • 边:每一种交换方式 (uj,vj)(u_j, v_j) 都是一次"交换排列第 uju_j、vjv_j 个位置",边权为 11;
  • 起点:题面给定的初始分布;
  • 终点集合:所有满足大根堆性质的分布(不止一个);
  • 答案:起点到终点集合的最短距离。

正解

思路

第一步:点数权没有意义,只有相对大小有意义。

大根堆的所有条件都是形如"Fi>Fp(i)F_i > F_{p(i)}"的不等号,不涉及具体数值。因此可以把 NN 个权值 按从小到大排个名,用排名替换权值:最小的换成 N−1N-1、最大的换成 00,得到一个序号序列 rki∈{0,1,…,N−1}\mathrm{rk}_i \in \{0, 1, \dots, N-1\}。于是大根堆性质被改写成一个纯粹的下标比较:

rki<rkp(i)(∀ i,  p(i)≠0).\mathrm{rk}_i < \mathrm{rk}_{p(i)} \qquad (\forall\, i,\; p(i) \neq 0).

这一步之后,初始状态 Fi⩽100F_i \leqslant 100 的具体取值完全不参与计算。

第二步:目标状态不唯一,所以不能"算距离到某一个目标"。

如果题目像八数码那样有唯一目标排列,就可以直接判定可达性;但大根堆只规定了父子间的偏序, 同一棵树上合法的堆排列有很多个。比如 N=4N = 4 的链 1→2→3→41 \to 2 \to 3 \to 4,可行序号序列是 0 1 2 30\,1\,2\,3;而完全二叉树 2,32,3 是 11 的孩子时,0 1 2 30\,1\,2\,3 与 0 2 1 30\,2\,1\,3 都是堆。 所以正确的做法不是求到某个终点的距离,而是把终点当成一个集合:BFS 时凡是生成出满足 堆性质的排列,就立即接受。

第三步:状态压缩成 64 位整数。

N⩽16N \leqslant 16,每个结点的序号恰好取值 0∼150 \sim 15,用 4 个二进制位就能存下 (这正是 N⩽16N \leqslant 16 这个上界的来源)。把结点 ii 的序号放在状态的第 4(i−1)4(i-1) 位起, 整棵树就是一个 64 位无符号整数,可以直接丢进哈希表当键:

state=∑i=1Nrki⋅16 i−1.\texttt{state} = \sum_{i=1}^{N} \mathrm{rk}_i \cdot 16^{\,i-1}.

一次交换 (u,v)(u, v) 就变成"取出这两段 4 位、交换后写回",三次位运算搞定:

text
a = (state >> su) & 15;          // u 的序号
b = (state >> sv) & 15;          // v 的序号
state' = state & ~(15 << su) & ~(15 << sv) | (b << su) | (a << sv);

判堆也不需要对每个结点单独查表,只需扫一遍 N−1N-1 条父子边,比较两段 4 位。

第四步:为什么 BFS 就是答案。

每次交换的代价都是 11,状态图是无权图,从起点出发的 BFS 第 dd 层恰好是 "用 dd 次交换能到达且 dd 次内均未到达过"的全部排列。又因为同一种方式可以重复使用, 边是无向的(交换是对合),所以状态图的连通分量就是可达集合,BFS 不会漏解。 因此首次生成出合法堆排列时的层数就是最少交换次数。

下面是第一组样例的状态图前三层。权值 1,2,3,41,2,3,4 换成序号后初始排列是 (3,2,1,0)(3,2,1,0), 四种子树上的交换方式 (u,v)(\mathrm{u},\mathrm{v}) 用 1 起编号。

flowchart TD
  S["(3,2,1,0) 起点 d=0"] -->|"(1,2)"| A1["(2,3,1,0)"]
  S -->|"(1,4)"| A2["(0,2,1,3)"]
  S -->|"(2,3)"| A3["(3,1,2,0)"]
  S -->|"(1,3)"| A4["(1,2,3,0)"]
  A2 -->|"(2,3)"| G["(0,1,2,3) 合法堆 d=2"]
  A3 -->|"(1,4)"| G
  A1 -.->|"d=1 层全都不满足堆性质"| X["..."]
  A4 -.-> X

第 1 层(d=1d=1)的四个状态都不是堆:(2,3,1,0)(2,3,1,0) 里结点 2 的序号 33 比父亲结点 1 的 22 大, (0,2,1,3)(0,2,1,3) 里结点 4 的 33 比父亲结点 2 的 22 大,另外两个同理。到第 2 层才出现 (0,1,2,3)(0,1,2,3),它对应权值分布 F=(4,3,2,1)F = (4,3,2,1),确实是一条链上的大根堆,于是答案是 22。 题面给出的方案 “先 (2,3)(2,3) 再 (1,4)(1,4)” 正是图中经 A3A_3 的那条实线路径。

代码

Python 版:

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:36
# update_at: 2026-10-07 15:54

import sys
from collections import deque
from collections.abc import Iterator

# 状态编码:state[i] 是结点 i+1 当前持有的权值序号。权值越大序号越小(最大权值为 0),
# 于是「父亲的序号小于儿子的序号」就是大根堆性质,和权值的具体数值无关。
type State = tuple[int, ...]        # 整棵树的当前权值排列
type Swaps = list[tuple[int, int]]  # 所有交换方式,统一写成 0 基下标且前者更小


def is_heap(state: State, fa: list[int], n: int) -> bool:
    """state 是否已满足大根堆性质:每个非根结点的序号都小于其父亲的序号。"""
    return all(state[fa[i] - 1] < state[i - 1] for i in range(1, n + 1) if fa[i])


def encode(weights: list[int], n: int) -> State:
    """把点权换成序号排列:最小权值的序号是 n-1,最大权值是 0。"""
    by_weight = sorted(zip(weights, range(1, n + 1)))  # 结点按权值升序
    rank = {node: n - 1 - pos for pos, (_, node) in enumerate(by_weight)}
    return tuple(rank[node] for node in range(1, n + 1))


def expand(state: State, swaps: Swaps) -> Iterator[State]:
    """逐个产出 state 经过一次交换能到达的排列。"""
    for i, j in swaps:
        # 交换第 i、j 位:切片拼出「前半段 + j 的值 + 中间段 + i 的值 + 后半段」
        yield state[:i] + (state[j],) + state[i + 1:j] + (state[i],) + state[j + 1:]


def min_swaps(start: State, fa: list[int], n: int, swaps: Swaps) -> int:
    """BFS:第一次生成出合法堆排列时的层数就是最少交换次数。"""
    if is_heap(start, fa, n):
        return 0                            # 初始排列已经是堆,一次都不用交换
    dist = {start: 0}
    queue = deque([start])
    while queue:
        state = queue.popleft()
        for nxt in expand(state, swaps):
            if nxt in dist:
                continue
            dist[nxt] = dist[state] + 1     # BFS 保证首次发现就是最短距离
            if is_heap(nxt, fa, n):
                return dist[nxt]            # 终点是一个集合,命中即答案
            queue.append(nxt)
    return -1                               # 题面保证有解,这里只是兜底


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)
    fa = [0] + [next(data) for _ in range(n)]     # fa[i] = 结点 i 的父亲,0 表示根
    weights = [next(data) for _ in range(n)]      # weights[i-1] = 结点 i 的点权

    swaps: Swaps = []
    for _ in range(m):
        u, v = next(data), next(data)
        swaps.append((u - 1, v - 1) if u < v else (v - 1, u - 1))

    print(min_swaps(encode(weights, n), fa, n, swaps))


if __name__ == "__main__":
    solve()

C++ 版(同一算法):

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 15:36
 * update_at: 2026-10-07 15:54
 */
// 一本通 1689 堆排问题
//
// 算法:状态压缩 + BFS
//  - 点权互不相同,把权值按大小换成序号 0..N-1(最大权值换成 0),
//    大根堆性质就变成「父亲的序号 < 儿子的序号」,与具体数值无关。
//  - N <= 16,每个结点用 4 位存序号,整棵树的排列压成一个 64 位整数状态。
//  - 一种交换方式就是一条边,边权为 1,同一方式可重复使用。
//    以初始排列为起点跑 BFS,第一次生成出合法的堆排列时所在层数就是最少交换次数。
//  - 状态数上界是 N!,开不出数组,visited 只能用 unordered_set(哈希风险见复杂度说明)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;  // 状态整数:16 个结点各占 4 位,共 64 位,必须用无符号

const int MAXN = 20;
const int MAXM = 130;

ll N;      // 结点个数
ll M;      // 交换方式的种数
ll fa[MAXN];        // fa[i] = 结点 i 的父亲,0 表示它是根
ull rank_of[MAXN];  // rank_of[i] = 结点 i 的权值序号,最大权值为 0
                    // 左侧要左移 4(i-1) 位,用无符号类型才不会在有符号位移上溢出

struct Swap {  // 一种交换方式
    ll u;
    ll v;
};
Swap swp[MAXM]; // swp[1..M] 存所有交换方式,下标从 1 开始和题面一致

// 判断状态 s 是否已经满足大根堆性质:每个结点序号都小于其父亲的序号
bool is_heap(ull s) {
    for (ll i = 1; i <= N; i++) {
        if (fa[i] == 0) continue;             // 根没有父亲,不用比较
        ll ps = 4 * (fa[i] - 1);              // 父亲在状态里的位偏移
        ll cs = 4 * (i - 1);                  // 结点 i 在状态里的位偏移
        if (((s >> ps) & 15ULL) > ((s >> cs) & 15ULL)) return false;
    }
    return true;
}

// 从初始状态 start 出发做 BFS,返回首次出现堆排列时的交换次数(数据保证有解)
// 逐层扩展:cur 是第 depth 层的全部状态,nxt 是下一层。
// 一个状态一旦被生成出来就立刻判堆:BFS 保证它第一次出现的层数就是最少交换次数,
// 所以命中即可返回,不必等它出队,省下整整一层的哈希表容量。
ll bfs(ull start) {
    if (is_heap(start)) return 0;  // 初始排列已经是堆,一次都不用交换
    unordered_set<ull> vis;        // 状态数上界是 N!,开不出数组,只能用哈希表记录访问
    vis.reserve(1 << 20);
    vis.insert(start);
    vector<ull> cur, nxt;
    cur.push_back(start);
    for (ll depth = 1; !cur.empty(); depth++) {
        nxt.clear();
        for (size_t k = 0; k < cur.size(); k++) {
            ull s = cur[k];
            for (ll i = 1; i <= M; i++) {
                ll su = 4 * (swp[i].u - 1), sv = 4 * (swp[i].v - 1);
                ull a = (s >> su) & 15ULL;  // 两个结点的当前序号
                ull b = (s >> sv) & 15ULL;
                // 清掉这两个 4 位再写回去,就完成一次权值交换
                ull t = (s & ~(15ULL << su) & ~(15ULL << sv)) | (b << su) | (a << sv);
                if (!vis.insert(t).second) continue;
                if (is_heap(t)) return depth;
                nxt.push_back(t);
            }
        }
        cur.swap(nxt);
    }
    return -1;  // 题面保证有解,这里只是兜底
}

int main() {
    scanf("%lld %lld", &N, &M);
    for (ll i = 1; i <= N; i++) scanf("%lld", &fa[i]);
    vector<pair<ll, ll> > vw;  // (权值, 结点编号),用于把权值换成序号
    for (ll i = 1; i <= N; i++) {
        ll w;
        scanf("%lld", &w);
        vw.push_back(make_pair(w, i));
    }
    for (ll i = 1; i <= M; i++) scanf("%lld %lld", &swp[i].u, &swp[i].v);

    sort(vw.begin(), vw.end());  // 权值升序;序号倒过来给,最大权值的序号是 0
    for (ll r = 0; r < N; r++) rank_of[vw[r].second] = N - 1 - r;

    ull start = 0;
    for (ll i = 1; i <= N; i++) start |= rank_of[i] << (4 * (i - 1));

    printf("%lld\n", bfs(start));
    return 0;
}

复杂度

设 SS 为 BFS 实际访问到的状态数(可以差到 N!N!,但答案很小时只展开前若干层):

  • 时间:每个状态枚举 MM 种交换、每次判堆需要 O(N)O(N);由于这里在生成时判堆并立即返回, 判堆次数是 O(SM)O(SM),总时间 O(SMN+SM)O(SMN + SM),即 O(SMN)O(SMN)。
  • 空间:哈希表 + 当前层/下一层各存 O(S)O(S) 个 64 位状态,共 O(S)O(S)。
  • 实测:第 7 个测试点(N=16N = 16,M=120M = 120,答案 33)访问 2 177 7042\,177\,704 个状态, C++ 用时约 1010 ms、峰值内存约 1313 MB;Python 用时约 0.090.09 s、峰值内存约 3434 MB。 其余九个点访问的状态数都在 1.3×1051.3 \times 10^5 以内。
  • 哈希风险:unordered_set<unsigned long long> + reserve(1 << 20) 在这个状态数下负载因子 仍在 0.50.5 以下,实测未出现明显退化;若手写哈希也不需要,直接用库表即可。

总结

  • 先离散化,再谈状态。大根堆只关心相对大小,把权值换成 0∼N−10 \sim N-1 的序号是本题的 第一个关键点:它不仅让"判堆"变成一次下标比较,还顺手把状态编码按到 4 位上。
  • 目标是一个集合,不是一个点。这类"到达某种性质"的题不要硬找唯一终点, 把性质写成判据、在 BFS 里即时检查即可。
  • N⩽16N \leqslant 16 不是偶然。16×4=6416 \times 4 = 64 位正好塞进一个 uint64, 一个整数同时承担"状态 + 哈希键 + 可比较"三重角色,这是本题写法最省事的地方。
  • 在生成时判堆能省一整层。BFS 保证状态第一次被生成时的层数就是最短距离, 因此不必等它出队再判,vis.insert 成功的瞬间就能检查;本题最坏的那个点因此 把哈希表从 217 万状态降到 7 万状态,内存从 133 MB 降到 13 MB。
  • 题面的样例解释第二组与数据不符。题面写的最优方案是 (1,2),(1,3),(1,2),(2,4),(2,5),(2,4)(1,2),(1,3),(1,2),(2,4),(2,5),(2,4),其中第 5 步 (2,5)(2,5) 有误:按这个顺序执行后 序号序列是 (3,0,2,4,1)(3,0,2,4,1),结点 2 的 00 比父亲结点 3 的 22 小,仍然不是堆。 换成 (1,2),(1,3),(1,2),(2,4),(4,5),(2,4)(1,2),(1,3),(1,2),(2,4),(4,5),(2,4) 即得到合法的 (3,4,2,1,0)(3,4,2,1,0), 步数同样是数据里答案的 66。本文的代码按数据实现,输出 66。