这是一个创建于 1791 天前的主题，其中的信息可能已经有所发展或是发生改变。
构建大顶堆的时候因为元素移动造成子树混乱是否有必要再调整？大元素已经上浮，子树不调整好像也是没有关系的吧
 |
1
creedowl 2020-01-31 13:44:20 +08:00 via Android
上浮后子树就不一定是大顶堆了啊。。建议复习数据结构堆的定义
|
 |
2
georgetso 2020-01-31 13:48:17 +08:00
无需调整, 堆保证的是每一次输出有序, 而不是内部有序.
|
 |
3
15921742431 OP @creedowl 我知道啊，但是我要的只是最大元素，而不是堆，我只是不知道这样做会不会有什么坑
|
|
4
15921742431 OP @georgetso 会有坑吗？看上去好像是没什么关系的
|
 |
5
Licsber 2020-01-31 14:11:16 +08:00
不用调整，堆只保证顶是最大 /最小的，每次更新操作都按完全二叉树的次序（层序）来，然后再做调整。
|
|
6
georgetso 2020-01-31 14:27:05 +08:00
有啥坑, 你要的是输出有序, 堆能保证输出有序, 这不就结了
|
 |
7
maggch 2020-02-01 00:21:20 +08:00 via Android
你只要最大元素你干嘛不直接遍历一下
|
 |
8
crclz 2020-02-01 10:33:52 +08:00
|
|
9
crclz 2020-02-01 10:40:49 +08:00
有必要。
“构建大顶堆”你指的应该是第一次构建的时候（求出最大值）。 你参照这个页面： https://🐎baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F 看到 c 语言代码。 我们记“条件 A”为“二叉树的每一个节点都是大于其左右子节点”。 max_heapify 方法的功能，是：若 T 的左右子树满足条件 A，那么 max_heapify 能将 T 调整为一个最大堆。 max_heapify 所需要的前提条件，就是条件 A。 所以第一次构建的时候，不断调用 max_heapify 方法的原因，就是让整个树满足条件 A。 这是纯逻辑的推理。 |
 |
10
eastphoton 2020-02-01 21:42:10 +08:00
有必要。
大元素的上浮，不正是 对其子树进行调整（ heapify ）完成的结果吗？ 调整和元素上浮本来就是同一操作。不调整无法保证上浮出来的是最大元素， 你怎么知道没调整的那个子树里会不会浮出来个比这个更大的元素？ |
Select Language