对heapsort的直观理解？

Question

在学校我们正在学习Java中的排序算法,而我的作业是Heap Sort.我做了我的阅读,我试图尽可能多地发现,但似乎我无法掌握这个概念.

我不是要求你给我写一个Java程序,如果你可以像Heap Sort那样简单地向我解释.

Answer 1

是的,所以基本上你拿堆并拉出堆中的第一个节点 - 因为第一个节点保证最大/最小,具体取决于排序方向.棘手的是首先重新平衡/创建堆.

我需要两个步骤才能理解堆进程 - 首先将其视为树,绕过它,然后将该树转换为数组,以便它可能有用.

第二部分是首先从左到右基本遍历树宽度,将每个元素添加到数组中.所以下面的树:

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

将是{73,7,12,2,4,9,10,1}

第一部分需要两个步骤:

1. 确保每个节点都有两个子节点(除非您没有足够的节点来执行此操作,如上面的树中所示.
2. 确保每个节点都比其子节点更大(如果先排序最小,则更小).

因此,要堆积一个数字列表,将每个数字添加到堆中,然后按顺序执行这两个步骤.

要在上面创建我的堆,我将首先添加10 - 它是唯一的节点,所以无所事事.在左边添加12作为孩子:

    10
  12

这满足1,但不满足2所以我会将它们换成圆形:

    12
  10

添加7 - 无所事事

    12
  10  7

加73

          12
       10     7
    73

10 <73所以需要交换那些:

          12
       73     7
    10

12 <73所以需要交换那些:

          73
       12     7
    10

加2 - 无事可做

          73
       12     7
    10   2

添加4 - 无所事事

          73
       12     7
    10   2  4

加9

          73
       12     7
    10   2  4   9

7 <9 - 交换

          73
       12     9
    10   2  4   7

添加1 - 无所事事

          73
       12     9
    10   2  4   7
  1

我们有堆:D

现在,您只需从顶部删除每个元素,每次将最后一个元素交换到树的顶部,然后重新平衡树:

取73取代1

          1
       12     9
    10   2  4   7

1 <12 - 所以交换他们

          12
        1    9
    10   2  4   7

1 <10 - 所以交换它们

          12
       10     9
     1   2  4   7

取12关 - 用7替换

          7
       10     9
     1   2  4   

7 <10 - 交换它们

          10
       7     9
     1   2  4   

取10关 - 用4替换

          4
       7     9
    1   2  

4 <7 - 交换

          7
       4     9
    1   2  

7 <9 - 交换

          9
       4     7
    1   2 

取9关 - 用2替换

          2
       4     7
    1   

2 <4 - 交换它们

          4
       2     7
    1  

4 <7 - 交换它们

          7
       2     4
    1  

取7关 - 换成1

          1
       2     4

1 <4 - 交换它们

          4
       2     1

取4 - 替换为1

          1
       2

1 <2 - 交换它们

          2
       1

取2 - 替换为1

          1

拿1

排序列表瞧.

Answer 2

考虑堆排序的一种方法是作为选择排序的巧妙优化版本.在选择排序中,排序通过重复查找尚未正确放置的最大元素,然后将其放入数组中的下一个正确位置来工作.然而,选择排序在时间O(n ²)中运行,因为它必须进行n轮寻找一堆中的最大元素(并且可以有多达n个不同的元素来查看)并将其放置到位.

直观地说,堆排序的工作原理是构建一个称为二进制堆的特殊数据结构,以加速从未放置的数组元素中找到最大的元素.二进制堆支持以下操作:

• Insert,将一个元素插入堆中,和
• Delete-Max,删除并返回堆的最大元素.

在非常高的级别,该算法的工作原理如下:

• 将数组的每个元素插入到新的二进制堆中.
• 对于i = n降至1:
  • 在堆上调用Delete-Max以获取堆的最大元素.
  • 将此元素写入位置i.

这会对数组进行排序,因为Delete-Max返回的元素按降序排列.删除所有元素后,将对数组进行排序.

堆排序是有效的,因为堆上的Insert和Delete-Max操作都在O(log n)时间运行,这意味着可以在O(n log n)时间内在堆上完成n次插入和删除. 可以使用更精确的分析来表明,无论输入数组如何,它都需要Θ(n log n)时间.

通常,堆排序采用两种主要的优化方式.首先,堆通常通过将数组本身视为堆的压缩表示形式在数组内部就地构建.如果你看一下heapsort实现,通常会看到基于乘以除以2的数组索引的异常使用; 这些访问是有效的,因为它们将数组视为压缩数据结构.结果,该算法仅需要O(1)辅助存储空间.

其次,堆不是一次构建堆一个元素,而是使用专门的算法构建堆,该算法在时间Θ(n)中运行以就地构建堆.有趣的是,在某些情况下,这最终会使代码更容易阅读,因为代码可以重复使用,但算法本身对于理解和分析来说有点棘手.

你有时会看到使用三元堆完成堆.这样做的优点是平均速度稍快一些,但是如果你发现使用它的heapsort实现而不知道你在看什么,那么阅读起来相当棘手.其他算法也使​​用相同的通用结构,但使用更复杂的堆结构. Smoothsort使用更复杂的堆来获得O(n)最佳情况行为,同时保持O(1)空间使用和O(n log n)最坏情况行为. Poplar排序类似于smoothsort,但具有O(log n)空间使用率和稍好的性能.人们甚至可以将经典排序算法(如插入排序和选择排序)视为堆排序变体.

一旦你更好地掌握了heapsort,你可能想要研究一下introsort算法,它结合了quicksort,heapsort和insert sort来产生一个极快的排序算法,结合了quicksort的强度(平均快速排序),heapsort(优秀的最坏情况行为)和插入排序(小数组的快速排序).Introsort是C++ std::sort函数的许多实现中使用的东西,并且一旦你有一个工作的heapsort就不是很难实现.

希望这可以帮助!