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

Question

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

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

Answer 1

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

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

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

                                    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

Add 2 - 无所事事

          73
       12     7
    10   2

Add 4 - 无所事事

          73
       12     7
    10   2  4

Add 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

Take 2 - 替换为 1

          1

Take 1

排序列表瞧。

Answer 2

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

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

• Insert，将元素插入堆中；
• Delete-Max，删除并返回堆中最大的元素。

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

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

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

堆排序是高效的，因为堆上的 Insert 和 Delete-Max 操作都在 O(log n) 时间内运行，这意味着可以在堆上完成 n 次插入和删除堆的时间复杂度为 O(n log n)。 更精确的分析可以表明，事实上，无论输入数组。

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

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

有时您会看到使用三元堆完成堆排序。这样做的优点是平均速度稍快，但如果您发现使用此方法的堆排序实现而不知道您正在查看的内容，那么阅读起来可能会相当困难。其他算法也使​​用相同的通用结构，但使用更复杂的堆结构。 Smoothsort 使用更复杂的堆来获得 O(n) 最佳情况行为，同时保持 O( 1) 空间使用和 O(n log n) 最坏情况行为。 Poplar排序与smoothsort类似，但空间使用量为O(log n)并且性能稍好一些。人们甚至可以将诸如插入排序和选择排序等经典排序算法视为堆排序变体 。

一旦您更好地掌握了堆排序，您可能需要研究 introsort 算法，该算法结合了快速排序、堆排序和插入排序，产生了一种极快的排序算法，该算法结合了快速排序（平均快速排序）、堆排序（出色的最坏情况行为）和插入排序（对小数据进行快速排序）的优势。数组）。 Introsort 是 C++ 的 std::sort 函数的许多实现中使用的方法，一旦您拥有一个可用的堆排序，那么您自己实现它并不难。

希望这有帮助！

Answer 3

我会看看我如何回答这个问题，因为我对堆排序和堆是什么的解释会有点......

呃，可怕。

无论如何，首先，我们最好检查一下堆是什么：

取自 Wikipedia，堆是：

在计算机科学中，堆是一种专门的基于树的数据结构，它满足堆属性：如果 B 是 A 的子节点，则 key(A) ≥ key(B)。这意味着具有最大键的元素始终位于根节点中，因此这样的堆有时称为最大堆。 （或者，如果比较相反，则最小元素始终位于根节点中，从而产生最小堆。）

则最小元素始终位于根节点中，这会产生最小堆。）几乎，堆是一棵二叉树，任何节点的所有子节点都小于该节点。

现在，堆排序是一种 O(n lg(n)) 排序算法。您可以在此处阅读一些相关内容和< a href="http://en.wikipedia.org/wiki/Heapsort" rel="nofollow">此处。它的工作原理是将要排序的所有元素放入堆中，然后从最大元素到最小元素构建排序数组。您将继续重组堆，并且由于最大的元素始终位于堆的顶部（根），因此您可以继续获取该元素并将其放在排序数组的后面。 （也就是说，您将反向构建排序数组）

为什么这个算法是 O(n lg(n))？因为堆上的所有操作都是 O(lg(n))，因此，您将执行 n 次操作，导致总运行时间为 O( n lg(n))。

我希望我的可怕咆哮对你有帮助！有点啰嗦；对此感到抱歉...

Answer 4

假设您有一个特殊的数据结构（称为堆），它允许您存储数字列表，并让您在 O(lg n) 时间内检索和删除最小的数字。

您是否明白这如何导致一个非常简单的排序算法？

困难的部分（实际上并不难）是实现堆。

Answer 5

也许交互式跟踪将帮助您更好地理解算法。这是一个演示。

Answer 6

我记得我的算法分析教授告诉我们，堆排序算法的工作原理就像一堆砾石：

想象一下，你有一个装满砾石的袋子，然后你把它倒在地板上：较大的石头可能会滚到底部，而较小的石头（或沙子）将留在上面。

现在，您取出堆的最顶部并将其保存为堆的最小值。再次将剩余的堆放入袋子中，然后重复。
（或者你可以采取相反的方法，抓住你看到在地板上滚动的最大的石头，这个例子仍然有效）

这或多或少是我所知道的解释堆排序如何工作的简单方法。

Answer 7

堆排序包括最简单的逻辑，时间复杂度为 O(nlogn)，空间复杂度为 O(1)

 public class HeapSort {

public static void main(String[] args) {
     Integer [] a={12,32,33,8,54,34,35,26,43,88,45};

     HeapS(a,a.length-1);

    System.out.println(Arrays.asList(a));

}

private static void HeapS(Integer[] a, int l) {


    if(l<=0)
        return;

    for (int i = l/2-1; i >=0 ; i--) {

        int index=a[2*i+1]>a[2*i+2]?2*i+1:2*i+2;
        if(a[index]>a[i]){
            int temp=a[index];
            a[index]=a[i];
            a[i]=temp;
        }

    }
    int temp=a[l];
    a[l]=a[0];
    a[0]=temp;

    HeapS(a,l-1);

  }
}