V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
15921742431
V2EX  ›  程序员

堆排序混乱调整是否有必要?

  •  
  •   15921742431 · 2020-01-31 13:14:04 +08:00 · 2229 次点击
    这是一个创建于 1757 天前的主题,其中的信息可能已经有所发展或是发生改变。

    构建大顶堆的时候因为元素移动造成子树混乱是否有必要再调整?大元素已经上浮,子树不调整好像也是没有关系的吧

    10 条回复    2020-02-01 21:42:10 +08:00
    creedowl
        1
    creedowl  
       2020-01-31 13:44:20 +08:00 via Android
    上浮后子树就不一定是大顶堆了啊。。建议复习数据结构堆的定义
    georgetso
        2
    georgetso  
       2020-01-31 13:48:17 +08:00
    无需调整, 堆保证的是每一次输出有序, 而不是内部有序.
    15921742431
        3
    15921742431  
    OP
       2020-01-31 14:06:27 +08:00
    @creedowl 我知道啊,但是我要的只是最大元素,而不是堆,我只是不知道这样做会不会有什么坑
    15921742431
        4
    15921742431  
    OP
       2020-01-31 14:07:16 +08:00
    @georgetso 会有坑吗?看上去好像是没什么关系的
    Licsber
        5
    Licsber  
       2020-01-31 14:11:16 +08:00
    不用调整,堆只保证顶是最大 /最小的,每次更新操作都按完全二叉树的次序(层序)来,然后再做调整。
    georgetso
        6
    georgetso  
       2020-01-31 14:27:05 +08:00
    有啥坑, 你要的是输出有序, 堆能保证输出有序, 这不就结了
    maggch
        7
    maggch  
       2020-02-01 00:21:20 +08:00 via Android
    你只要最大元素你干嘛不直接遍历一下
    crclz
        8
    crclz  
       2020-02-01 10:33:52 +08:00
    有必要。
    “构建大顶堆”你指的应该是第一次构建的时候(求出最大值)。

    你参照这个页面: https://baike.baidu.com/item/%E5%A0%86%E6%8E%92%E5%BA%8F
    crclz
        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。

    这是纯逻辑的推理。
    eastphoton
        10
    eastphoton  
       2020-02-01 21:42:10 +08:00
    有必要。

    大元素的上浮,不正是 对其子树进行调整( heapify )完成的结果吗?

    调整和元素上浮本来就是同一操作。不调整无法保证上浮出来的是最大元素,
    你怎么知道没调整的那个子树里会不会浮出来个比这个更大的元素?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2297 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 16:06 · PVG 00:06 · LAX 08:06 · JFK 11:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.