算法题求思路

[letianqiu]

给定一个大顶堆，元素已知。求能够生成这个大顶堆的元素插入顺序中，大的元素后插的顺序。
堆是[27，12，18]，插入顺序是 12，18，27
堆是[45，24，27，2，16]， 插入顺序是 2 , 27 , 45 , 16 , 24
目前只能想到 naive 的 n!的暴力求解，但是肯定不符合要求。求高效算法

[kaliu]

没看懂问题描述。

[monkeymonkey]

LZ 的题目确实描述不清楚。
猜测是有一个空的大顶堆，按顺序插入一系列数字，最后形成一个堆（题目给出），求能够生成题目所给堆的数字插入顺序。
比如[27,12,18],
1. 先有空堆[]
2. 插入 12， 变成[12]
3. 插入 18，sift up 18，变成[18,12]
4. 插入 27，sift up 27，变成[27,12,18]
所以 12,18,27 是一个解
但是 18,12,27 也是一个解。
由此可知，解可能不唯一。

提供一个思路：
比如[45，24，27，2，16]
既然是最大堆，那我们从最顶上，也就是最大的数 45 开始，假设 45 是最后一个插入的数。
由 siftup 的性质可知，最后一个数从下往上走过的路径只能是 16->24->45.
把 45 与 24 交换，发现 24 比 27 小，大顶堆不成立，所以不是 45。

然后测试这条路上的 24，与 16 交换，并且从堆中移除，发现得到的新堆[45,16,27,2]是一个合格的大顶堆。
所以最后一个数是 24。

同理得到倒数第二个数是 16。
依次类推求出一个解，但是有可能只是其中一个解。

[twistoy]

@monkeymonkey #2 我觉得他说的 大的元素后插 应该指的是 输出的序列应该是字典序最小的那个

[twistoy]

猜测题目的描述的意思是：给定一个大根堆，求一个数列可以生成这个大根堆；如果有多个解，需求那个字典序最小的。
思路大概是：最后被 push 到堆的数，一定出现在从最后一个数到根的那条链上的，所以每次尝试在这条链上找一个深度最大的满足条件 A 的数，那么这个数就应该是当前考虑的最后一个被插入的数。
条件 A：一个在我们考虑的这条链上的 X，所有深度比 X 大（也就是在 X 下面）的数都应该没有兄弟，或者大于等于其兄弟。
我写了一个代码在 https://gist.github.com/TwIStOy/a0b0cb1317ed9bf4d9a805222edfc3e8

[letianqiu]

@twistoy 的确是你说的意思。但是你的条件 A 不是非常理解。比如[45，24，27，2，16]，最后插入的元素是 24，觉得不满足你说的条件 A。24 的左孩子是 2，右孩子是 16。int nxt = cur ^ 1;这个异或也不是很理解。

[twistoy]

@letianqiu 堆 45 24 27 2 16, 最后一个数到根的链是 45, 24, 16。16 是一定可以作为最后一个的, 24 可以作为最后一个是因为 16 比他的兄弟 2 大, 45 不能是最后一个因为 24 比他的兄弟 27 小。那个异或的意思是哪个编号的兄弟节点的编号。

[letianqiu]

@twistoy 明白了。思路和 @monkeymonkey 说的一样。非常感谢。