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

堆是否是有序的?若是无序的,怎么看堆排序?它为什么叫堆排序?

  •  
  •   twogoods · 2016-02-11 10:13:57 +08:00 · 4174 次点击
    这是一个创建于 3190 天前的主题,其中的信息可能已经有所发展或是发生改变。
    3 条回复    2016-02-11 11:31:41 +08:00
    Andiry
        1
    Andiry  
       2016-02-11 10:16:36 +08:00 via Android   ❤️ 1
    堆是层次有序的
    aheadlead
        2
    aheadlead  
       2016-02-11 10:45:43 +08:00
    比如说你有个 n 个数的大顶堆(就是任何一个节点比它的子节点要大)

    把根(也就是整个堆里面最大的数)取出来,也就是删除(删除的操作为 O(log n) )
    上面这个操作重复 n-1 次,就完成了排序
    wwttc
        3
    wwttc  
       2016-02-11 11:31:41 +08:00   ❤️ 1
    1. 堆(二叉堆)是一个数组,可以看成一个近似的完全二叉树,树中每一个结点对应数组中的一个元素。二叉堆有两种形式:最大堆和最小堆。在最大堆中,除了根结点之外的所有结点的值小于等于其父节点的值,因此,堆中最大的元素存放在根结点中,并且在任一子树中,该子树所包含的所有结点的值都不大于该子树根结点的值。最小堆的组织方式正好相反。因此,每次只是保证根结点处是当前剩余节点的最大(或最小)的。

    2. 堆排序的过程如下:
    ①利用 BUILD-MAX-HEAP 将输入数组 A[1..n]建成一个最大堆,其中 n = A.length ;
    ②将数组最大元素所在的 A[1]位置的值与 A[n]位置的值进行交换,然后从堆中去掉结点 n ;
    ③在新的根结点 1 可能会违背最大堆的性质,因此需要利用 MAX-HEAPIFY 进行调整;
    ④不断重复 2,3 步,直到堆中只剩下一个元素,此时排序完成。

    3. 因为使用了堆这个数据结构,所以就叫堆排序。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1074 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 158ms · UTC 19:01 · PVG 03:01 · LAX 11:01 · JFK 14:01
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.