对堆排序有直观的了解？

是的，所以基本上你拿一个堆，然后拉出堆中的第一个节点 - 因为第一个节点保证是最大/最小的，这取决于排序的方向。棘手的事情是首先重新平衡/创建堆。

我需要两个步骤来理解堆过程 - 首先将其视为一棵树，让我的头脑绕过它，然后将该树变成一个数组，以便它可以有用。

第二部分是首先遍历树的宽度，从左到右将每个元素添加到数组中。所以下面的树：

                                    73                          
                                 7      12          
                               2   4  9   10    
                             1          

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

第一部分需要两个步骤：

1. 确保每个节点都有两个子节点（除非您没有足够的节点来执行此操作，如上面的树所示。
2. 确保每个节点都比其子节点大（如果先排序 min，则小于该节点）。

因此，要堆出一个数字列表，请将每个数字添加到堆中，然后按顺序执行这两个步骤。

为了在上面创建我的堆，我将首先添加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

排序列表瞧。

将堆排序视为选择排序的巧妙优化版本。在选择排序中，排序的工作原理是反复查找尚未正确放置的最大元素，然后将其放入数组中的下一个正确位置。但是，选择排序在时间O（n²）中运行，因为它必须进行n轮从一堆元素中找到最大的元素（并且最多可以有n个不同的元素来查看）并将其放入到位。

直观地说，堆排序的工作原理是构建一个称为二进制堆的特殊数据结构，该结构可以加快从未放置的数组元素中查找最大元素的速度。二进制堆支持以下操作：

• 插入，将元素插入到堆中，以及
• Delete-Max，它删除并返回堆中最大的元素。

在非常高的级别上，该算法的工作原理如下：

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

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

堆排序非常有效，因为堆上的 Insert 和 Delete-Max 操作都在 O（log n） 时间内运行，这意味着 n 次插入和删除可以在 O（n log n） 时间内在堆上完成。更精确的分析可用于证明，实际上，无论输入数组如何，它都需要Θ（n log n）时间。

通常，堆排序采用两个主要优化。首先，堆通常是通过将数组本身视为堆的压缩表示形式，在数组内就地构建的。如果你看一个堆排序实现，你通常会看到数组索引的不寻常用法，基于乘以和除以二;这些访问之所以有效，是因为它们将数组视为压缩的数据结构。因此，该算法只需要O（1）辅助存储空间。

其次，堆通常使用在时间Θ（n）中运行以就地构建堆的专用算法来构建堆，而不是一次构建一个元素的堆。有趣的是，在某些情况下，这最终使代码更易于阅读，因为代码可以重用，但算法本身变得有点难以理解和分析。

您有时会看到使用三元堆完成堆排序。这具有平均速度稍快的优点，但是如果您发现使用它的堆排序实现而不知道您正在查看的内容，则阅读起来可能相当棘手。其他算法也使用相同的一般结构，但堆结构更复杂。Smoothsort 使用更复杂的堆来获取 O（n） 最佳情况行为，同时保持 O（1） 空间使用率和 O（n log n） 最坏情况行为。杨树排序类似于平滑排序，但具有O（log n）空间使用率和稍好的性能。甚至可以将经典的排序算法（如插入排序和选择排序）视为堆排序变体。

一旦您更好地掌握了堆排序，您可能希望查看 introsort 算法，该算法结合了快速排序、堆排序和插入排序，以生成一种极其快速的排序算法，该算法结合了快速排序（平均快速排序）、堆排序（出色的最坏情况行为）和插入排序（小数组的快速排序）的优点。Introsort是C++函数的许多实现中使用的方法，一旦你有了一个有效的堆排序，就不难实现自己。std::sort

希望这有帮助！