这是一个创建于 2598 天前的主题，其中的信息可能已经有所发展或是发生改变。
给定一个大顶堆，元素已知。求能够生成这个大顶堆的元素插入顺序中，大的元素后插的顺序。
堆是[27，12，18]，插入顺序是 12，18，27
堆是[45，24，27，2，16]， 插入顺序是 2 , 27 , 45 , 16 , 24
目前只能想到 naive 的 n!的暴力求解，但是肯定不符合要求。求高效算法
堆是[27，12，18]，插入顺序是 12，18，27
堆是[45，24，27，2，16]， 插入顺序是 2 , 27 , 45 , 16 , 24
目前只能想到 naive 的 n!的暴力求解，但是肯定不符合要求。求高效算法
 |
1
kaliu 2017-10-12 22:21:43 +08:00
没看懂问题描述。
|
 |
2
monkeymonkey 2017-10-12 23:17:30 +08:00  1
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。 依次类推求出一个解，但是有可能只是其中一个解。 |
 |
3
twistoy 2017-10-12 23:45:32 +08:00
@monkeymonkey #2 我觉得他说的 大的元素后插 应该指的是 输出的序列应该是字典序最小的那个
|
|
4
twistoy 2017-10-13 01:21:51 +08:00 1
猜测题目的描述的意思是：给定一个大根堆，求一个数列可以生成这个大根堆；如果有多个解，需求那个字典序最小的。
思路大概是：最后被 push 到堆的数，一定出现在从最后一个数到根的那条链上的，所以每次尝试在这条链上找一个深度最大的满足条件 A 的数，那么这个数就应该是当前考虑的最后一个被插入的数。 条件 A：一个在我们考虑的这条链上的 X，所有深度比 X 大（也就是在 X 下面）的数都应该没有兄弟，或者大于等于其兄弟。 我写了一个代码在 https://gist.github.com/TwIStOy/a0b0cb1317ed9bf4d9a805222edfc3e8 |
 |
5
letianqiu OP @twistoy 的确是你说的意思。但是你的条件 A 不是非常理解。比如[45，24，27，2，16]，最后插入的元素是 24，觉得不满足你说的条件 A。24 的左孩子是 2，右孩子是 16。int nxt = cur ^ 1;这个异或也不是很理解。
|
|
6
twistoy 2017-10-13 08:35:19 +08:00 via Android
@letianqiu 堆 45 24 27 2 16, 最后一个数到根的链是 45, 24, 16。16 是一定可以作为最后一个的, 24 可以作为最后一个是因为 16 比他的兄弟 2 大, 45 不能是最后一个因为 24 比他的兄弟 27 小。那个异或的意思是哪个编号的兄弟节点的编号。
|
|
7
letianqiu OP @twistoy 明白了。思路和 @monkeymonkey 说的一样。非常感谢。
|
Select Language