logo标签列表

堆排序的直观理解是什么？

javaalgorithmsortingheapsort
43

我在学校学习Java中的排序算法，我的作业是堆排序。我读了很多资料，尽力理解，但似乎无法掌握概念。

我不要求你为我编写Java程序，如果您能尽可能简单地向我解释堆排序如何工作，那就太好了。

1
不知道你没有理解的是什么，我只能说我可能会写出你已经读过的内容（最好的情况下）。你能解释一下你不理解的是什么吗？ - Peter Lawrey
1
请向我们解释您的理解以及您卡住的地方。 "堆是一棵具有这些和这些限制的二叉树，这意味着对于某个高度为H的树，这些事情成立，基本上意味着其他一些事情会随之而来。因此，最小堆只是每个节点的子节点与其父节点具有特定关系的堆，但我不明白如何在堆排序中执行某个特定的关键步骤。"<< 这就是编写能得到真正答案的问题的方式。 - user684934
你可以将你所阅读的内容链接并提及你不理解的部分，然后我们再讨论这些问题如何？ - CloudyMarble
7个回答
125

简单来说，你需要取出堆中的第一个节点 - 因为第一个节点保证是最大值或最小值（根据排序顺序）。但难点在于首先要重新平衡/创建堆。

要理解堆排序过程，需要两个步骤 - 首先将其视为一棵树并理解它的结构，然后将该树转换为数组以便于使用。

第二部分是以广度优先的方式遍历树，从左到右将每个元素添加到数组中。例如以下树形结构:

                                    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 - swap

          7
       4     9
    1   2

交换7和9的位置

          9
       4     7
    1   2

减去9，替换为2

          2
       4     7
    1

将2和4进行交换 - 2 < 4

          4
       2     7
    1

将 4 和 7 交换位置

          7
       2     4
    1

把7减去，替换为1

          1
       2     4

将1和4互换 - Swap them

          4
       2     1

进行第四次替换，使用一个元素代替

          1
       2

将 1 和 2 交换位置

          2
       1

采用第二种方法，替换为第一种方法

          1

第一步

排序后的列表，完成。

14
非常详尽的讲解！需要很高耐心才能如此深入地描述它！ - MajesticRa
4
谢谢 - 我刚在推特上抱怨说，简短的回答能让我得到很多分数，而冗长的回答却只能得到很少的分数，但是教授的赞扬让一切都值得 ;) - Matt Fellows
2
非常感谢您的付出，我真的很感激。 - Rok Novosel
32
一种理解堆排序的方式是将其视为选择排序的巧妙优化版本。在选择排序中，排序通过重复查找尚未正确放置的最大元素，然后将其放入数组中的下一个正确位置来完成。但是，由于它必须执行n轮查找一组中的最大元素（并且可能有多达n个不同的元素要查看），因此选择排序的运行时间为O(n²)。
直观地说，堆排序通过构建称为二叉堆的特殊数据结构来加快查找未放置的数组元素中的最大元素。二叉堆支持以下操作：
插入，将元素插入堆中；
删除最大值，移除并返回堆的最大元素。
在非常高的层次上，该算法的工作方式如下：
  • 将数组的每个元素插入新的二叉堆中。
  • 对于i等于n到1：
    • 调用堆的Delete-Max函数以获取堆中最大的元素。
    • 将该元素写入位置 i。

这样就对数组进行了排序，因为由Delete-Max返回的元素是按降序排列的。一旦所有元素都被删除，数组就会被排序。

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

通常情况下，堆排序采用两种主要优化。首先，堆通常是在数组内部原地构建的，通过将数组本身视为堆的压缩表示。如果您查看堆排序实现，通常会看到基于乘法和除法的数组索引的不寻常用法；这些访问之所以有效，是因为它们将数组视为一种压缩的数据结构。因此，该算法仅需要O(1)辅助存储空间。
其次，堆通常是使用一种专门的算法进行构建的，该算法在Θ(n)时间内就可以在原地构建堆。有趣的是，在某些情况下，这使得代码更易于阅读，因为可以重复使用代码，但算法本身变得有点棘手，需要更深入的理解和分析。
有时候你会看到堆排序使用三叉堆。这样做的优点是平均速度稍快，但如果你不知道正在查看什么，那么使用这种堆排序实现可能会相当棘手。其他算法也使用相同的一般结构，但使用更复杂的堆结构。Smoothsort使用更复杂的堆来实现O(n)最佳情况行为，同时保持O(1)空间使用和O(n log n)最坏情况行为。Poplar sort类似于smoothsort，但空间使用为O(log n)，性能略好。人们甚至可以将经典排序算法插入排序和选择排序视为堆排序变体。
一旦您更好地掌握了堆排序，您可能想研究introsort算法，它结合了快速排序、堆排序和插入排序，产生了一种极快的排序算法，结合了快速排序（平均快速排序）、堆排序（优秀的最坏情况行为）和插入排序（小数组的快速排序）。Introsort是许多C++''s std::sort函数实现中使用的算法，一旦您掌握了堆排序算法，就不难自己实现它。

希望这可以帮到您！

一年，我正在看奥运会的时候编写了一个排序算法。它首先声明每个人都是合格的选手，因为没有人比其他人优越，然后迭代地将那些被认为比最少的人优越的合格人配对，输的人暂时失去资格，并将该参赛者的“优于”计数添加到赢家的计数中。一旦只剩下一位选手，那么他就是第一名获胜者；将其从集合中删除，重新启用所有人，然后继续。第一轮需要N-1次比较；第二轮需要lgN次。以后的回合不同。 - supercat
通过计算项目值比较，我发现排序功能运行得非常好，但是我还没有分析它与堆排序的确切行为相比较，后者在概念上似乎更接近。然而，堆排序不会像我的基于锦标赛的排序那样改变后续行为。 - supercat
顺便提一下，我已经实现了平滑排序和杨树排序，但是我的基准测试结果表明，没有明显的胜者。平滑排序至少和杨树排序一样好。 - Morwenn
2
我来试着回答一下这个问题，因为我对堆排序和堆的解释可能会有点……糟糕。
首先，我们最好先了解一下堆是什么：
根据维基百科（Wikipedia）的定义，堆是一种特殊的基于树的数据结构，满足堆属性：如果B是A的子节点，则key(A) ≥ key(B)。这意味着具有最大键值的元素始终位于根节点，因此这样的堆有时被称为最大堆。 （或者，如果比较反过来，则最小元素始终位于根节点，这导致形成最小堆。）
简单来说，堆是一个二叉树，使得任何节点的所有子节点都小于该节点。
现在，堆排序是一种O（n lg（n））的排序算法。你可以在这里和这里读到一些相关信息。它基本上是通过将你要排序的所有元素放入一个堆中，然后从最大的元素到最小的元素构建排序数组。你将继续重构堆，由于最大的元素始终位于堆的顶部（根），因此你只需将该元素保留并将其放置在已排序数组的末尾即可。（也就是说，你将按相反顺序构建已排序数组）
为什么这个算法是O（n lg（n））？因为堆上的所有操作都是O（lg（n）），因此你将进行n 次操作，总运行时间为O（n lg（n））。
我希望我的糟糕解释能帮助你！有点啰嗦，对不起...
2
假设您有一种特殊的数据结构（称为堆），它允许您存储数字列表并使您能够在O(lg n)时间内检索和删除最小值。
您是否看到了这如何导致一个非常简单的排序算法？
难点（实际上并不难）是实现堆。
1
也许交互式跟踪可以帮助您更好地理解算法。这里有一个演示。
0

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

想象一下你有一个装满碎石的袋子，你把它倒在地上：大石头很可能会滚到底部，而较小的石头（或沙子）则会留在顶部。

现在你取出堆的最顶端，并将其保存在堆的最小值处。然后再把剩下的堆放回袋子里，重复这个过程。 （或者你可以采用相反的方法，拿起你在地上看到的最大的石头，这个例子仍然是有效的）

这就是我知道的解释堆排序工作原理的简单方式。

一个小问题 - 在堆排序中，你不需要在每一步重建堆。如果你这样做，最终会得到选择排序。 - templatetypedef
是的，我想用一个简单的砾石袋来解释这个可能不太容易。 :P - STT LCU
但是你确实重新平衡了堆，对吧？ - Matt Fellows
在这个例子中，当你再次将堆放入袋子中并将其倒出到地板上时，堆会自动重新平衡。无论如何，这只是一个初学者的例子，因此可能会有一些点被跳过，只是为了提供一个可理解的总体图像。 - STT LCU
0

堆排序是一种最简单的算法，时间复杂度为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);

  }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接