时间限制： 3.0 秒 1.0 秒

空间限制： 1024 MB

题目背景

二叉树接口定义

给定以下二叉树的节点接口定义：

struct BinNode
{
    int data; // 关键码
    BinNode *lc, *rc; // 左儿子和右儿子
    BinNode *parent; // 父亲（对于根节点为 NULL）
};

同构的定义

对于两棵均由 $n$ 个节点组成的二叉树 $V$ 和 $U$，若节点分别用 $1$ 到 $n$ 之间的整数编号，我们定义两者的【弱同构】和【强同构】分别满足以下条件：

• 弱同构：每一对编号相等的节点 $v\in V$ 和 $u\in U$，均满足 v->parent 和 u->parent 编号相同或同为 NULL。
• 强同构：在弱同构的基础上，还满足 v->lc 和 u->lc 编号相同或同为 NULL，v->rc 和 u->rc 编号相同或同为 NULL。

题目描述

你需要实现 heapify 函数，传入一个规模为 $n$ 的二叉树的根节点 $x$，在时间复杂度 $O(n\log n)$ 内，将二叉树转化为与之强同构的大根堆。

根据题目对【强同构】的定义，你显然不能更改二叉树的结构（即修改任意一个节点的左右儿子或父亲）。

需要注意的是，你只能对原始的关键码更换其所在节点，不能修改关键码的具体分布。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 heapify.h。

你需要实现一个函数 void heapify(BinNode*)，传入参数为待修改二叉树的树根 $x$。你需要在规定时间内对二叉树完成修改。我们保证使用的二叉树节点接口同题目描述。

以下我们给出一个代码提交实例（不做任何修改即返回，仅作为可以通过编译的示例，不保证能得分）：

#include "heapify.h"
void heapify(BinNode* x)
{
    return;
}

你不需要，也不应该，实现主函数。

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 heapify.h。需要注意的是，该白盒交互库并非实际评测使用的交互库。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

判题方式解释

白盒与黑盒（即实际评测使用）交互库在原理上相同。

我们会分别检查以下内容：

• 二叉树结构是否和原本一致，即每个节点的左右儿子以及父亲指针均未做改动；
• 关键码分布是否和原本一致，即各关键码与最初输入的关键码在排序后逐一比对是完全一致的；
• 调整后的二叉树结构是否满足大根堆性质。

6
1 2 2 1 5
1 2 3 4 5 6

OK!

样例 1 解释

该样例遵循白盒交互库的形式。

输入的第一行为节点个数。

第二行开始为 $f_2,\cdots,f_n$，表示 $2\sim n$ 的父亲节点。

默认树上编号满足 1 号节点为根，其他节点保证 $1\le f_i<i$，传入 heapify 函数的参数即为 1 号节点的地址。

我们保证每个 $f_i$ 不会出现超过 $2$ 次（从而满足是二叉树结构）。我们约定 $f_i$ 第一次出现时，表示 $i$ 是 $f_i$ 的左儿子；$f_i$ 第二次出现时，表示 $i$ 是 $f_i$ 的右儿子。

第三行开始为 $a_1,\cdots,a_n$，表示这些节点的原始关键码是多少（对应 x->data）。

当满足上述要求时，白盒交互库会输出 OK! 并停机。需要注意的是，黑盒交互库不会采用这种方式，直接输出 OK! 并结束程序不会得分。

如果不满足上述情况，会分别返回：

• Invalid structure!：二叉树结构不满足强同构；
• Invalid data!：二叉树关键码分布和输入不一致；
• Invalid heap!：最终的二叉树不满足大根堆性质。

子任务

对于所有数据，保证节点个数 $n\le 10^6$，关键码 $1\le a_i\le 10^9$ 且互不相同，输入的树一定是一个二叉树结构。

本题无数据梯度，需要通过全部数据获得所有分数。

提示 0

邓俊辉《数据结构》中提到的完全二叉堆只是堆的一种特殊形式，并不意味着一般的堆一定是完全二叉树的形式。比如说左式堆就不是完全二叉树。

提示 1

本题除了二叉树节点上已有的信息，你可能需要遍历一遍二叉树来记录这些额外信息。以下我们给出一种书写的框架。

struct ExtraNode // 记录额外信息节点
{
    // todo : 你要维护的额外信息
    ExtraNode *lc, *rc; // 左右指针，理论上应当让 ExtraNode 生成的二叉树和原始二叉树强同构
    // 默认构造函数，如果你有额外信息，则其为空的状态也需要写在这里
    ExtraNode() { lc = nullptr, rc = nullptr; }
};

ExtraNode* get_extra(BinNode* x)
{
    if (x == nullptr) return nullptr;
    ExtraNode* ret = new ExtraNode();
    
    // 此处记录相关额外信息
  
    // 左右子树和原二叉树同步
    if (x->lc) ret->lc = get_extra(x->lc);
    if (x->rc) ret->rc = get_extra(x->rc);
    return ret;
}

提示 2

可以考虑一下完全二叉堆的上滤和下滤操作。

• 上滤是若当前节点比父节点的值要大，则需要一直与父节点交换关键码，直至不大于父节点为止（满足大根堆性质）。
• 下滤是若当前节点比子节点的值要小，则需要一直与子节点中的较大者交换关键码，直至不小于子节点值为止（满足大根堆性质）。

提示 3

上面的提示并不都是有用的捏~谨防上当受骗！

提示 4

由于交互库判题的时间较长，经过计算，实际留给选手解题的时间只有 1 秒。

来源

清华 826 考研初试 2025 - 算法大题（1）