构建大顶堆的时候因为元素移动造成子树混乱是否有必要再调整?大元素已经上浮,子树不调整好像也是没有关系的吧
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 )完成的结果吗? 调整和元素上浮本来就是同一操作。不调整无法保证上浮出来的是最大元素, 你怎么知道没调整的那个子树里会不会浮出来个比这个更大的元素? |