对堆排序有一个直观的理解吗？

在学校，我们目前正在学习 Java 排序算法，我的作业是堆排序。我读了书，试图尽可能多地了解，但似乎我无法理解这个概念。

我并不是要求您为我编写一个 Java 程序，只要您能尽可能简单地向我解释堆排序的工作原理即可。

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

我需要两个步骤来理解堆过程 - 首先将其视为一棵树，了解它，然后将该树转换为一个数组，以便它有用。

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

                                    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

Add 73

          12
       10     7
    73

10

          12
       73     7
    10

12

          73
       12     7
    10

添加 2 - 无事可做

          73
       12     7
    10   2

添加 4 - 无事可做

          73
       12     7
    10   2  4

Add 9

          73
       12     7
    10   2  4   9

7

          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
        1    9
    10   2  4   7

1

          12
       10     9
     1   2  4   7

去掉 12 - 替换为 7

          7
       10     9
     1   2  4   

7

          10
       7     9
     1   2  4   

去掉 10 个 - 替换为 4 个

          4
       7     9
    1   2  

4

          7
       4     9
    1   2  

7

          9
       4     7
    1   2 

去掉 9 - 替换为 2

          2
       4     7
    1   

2

          4
       2     7
    1  

4

          7
       2     4
    1  

去掉 7 - 替换为 1

          1
       2     4

1

          4
       2     1

取 4 - 替换为 1

          1
       2

1

          2
       1

取 2 - 替换为 1

          1

Take 1

排序列表瞧。