对heapsort的直观理解？
在学校，我们正在学习使用Java进行sortingalgorithm，而我的作业是堆sorting（Heap Sort）。 我做了自己的阅读，试图尽可能多地找出答案，但看来我无法理解这个概念。
我不是要求你给我写一个Java程序，如果你可以简单地向我解释一下堆分类是如何工作的。
正确的，所以基本上你会堆积一堆，并把堆中的第一个节点取出 – 因为根据sorting的方向，第一个节点保证是最大/最小的节点。 棘手的事情是首先重新平衡/创build堆。
我需要两个步骤来理解堆进程 – 首先把它想象成一棵树，然后把它放在一个数组中，然后把它转换成一个数组，这样可能会有用。
第二部分是基本上遍历树的宽度，从左到右将每个元素添加到数组中。 所以下面的树：
73 7 12 2 4 9 10 1 会是{73,7,12,2,4,9,10,1}
第一部分需要两个步骤：
- 确保每个节点都有两个孩子（除非你没有足够的节点来做到这一点，就像上面的树一样。
- 确保每个节点比其子节点更大（或者，如果先sorting，则更小）。
因此，为了堆积一个数字列表，您将每个数字添加到堆中，然后依次执行这两个步骤。
为了创build我的堆，我将首先添加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
sorting列表瞧。
思考堆sorting的一种方法是作为selectsorting的巧妙优化版本。 在selectsorting中，sorting通过重复查找尚未正确放置的最大元素，然后将其放入数组中的下一个正确位置。 然而，selectsorting在时间O（n 2 ）中运行，因为它必须从一堆中找出最大的元素（并且可以有多达n个不同的元素来查看）并将其放置到位。
直观地说，堆sorting的工作原理是构build一个称为二进制堆的特殊数据结构，以加速find未放置的数组元素中的最大元素。 二进制堆支持以下操作：
- 插入 ，插入一个元素到堆，和
- Delete-Max ，删除并返回堆的最大元素。
在很高的层面上，algorithm的工作原理如下：
- 将数组的每个元素插入一个新的二进制堆。
- 对于i = n降至1：
- 调用堆中的Delete-Max以获取堆的最大元素。
- 写这个元素到位置我。
这样sorting数组是因为Delete-Max返回的元素按降序排列。 一旦所有的元素都被删除，然后数组被sorting。
堆sorting非常有效，因为堆中的Insert和Delete-Max操作都在O（log n）时间运行，这意味着可以在O（n log n）时间内在堆上执行n个插入和删除操作。 更精确的分析可以用来表明，事实上，无论input数组如何，它都需要Θ（n log n）时间。
通常，堆sorting采用两个主要的优化。 首先，堆通常是通过将数组本身视为堆的压缩表示而在内部就地build立起来的。 如果你看一个堆sorting的实现，你通常会看到基于乘以二的数组索引的不寻常的用法; 这些访问工作，因为他们把数组视为一个精简的数据结构。 结果，该algorithm仅需要O（1）辅助存储空间。
其次，堆不是一次构build堆一个元素，而是通常使用运行在时间Θ（n）中的专用algorithm来构build堆，以便就地构build堆。 有趣的是，在某些情况下，这最终使得代码更容易阅读，因为代码可以被重用，但是algorithm本身变得有点棘手的理解和分析。
有时你会看到一堆三元堆 。 这样做的好处是平均速度稍微快一些，但是如果在不知道自己在看什么的情况下使用这种方法发现堆栈实现，那么阅读起来可能会相当棘手。 其他algorithm也使用相同的通用结构，但使用更复杂的堆结构。 Smoothsort使用更复杂的堆来获得O（n）最佳情况行为，同时保持O（1）空间使用情况和O（n log n）最坏情况行为。 杨树sorting类似于平滑sorting ，但具有O（log n）空间使用和稍好的性能。 人们甚至可以将经典sortingalgorithm（如插入sorting和selectsorting）看作堆sorting变体 。
一旦你对heapsort有了更好的把握，你可能需要研究introsortalgorithm，它结合了quicksort ，heapsort和插入sorting，以产生一个极快的sortingalgorithm，结合了quicksort（平均快速sorting），heapsort优秀的最坏情况行为）和插入sorting（快速sorting小arrays）。 Introsort是C ++的std::sort函数的许多实现中使用的内容，一旦你有一个工作堆栈，并不是很难实现自己。
希望这可以帮助！
假设你有一个特殊的数据结构（称为堆），它允许你存储一个数字列表，并让你检索和删除最小的一个O(lg n)时间。
你看这是如何导致一个非常简单的sortingalgorithm？
困难的部分（实际上并不那么难）正在实施堆。
我记得我的algorithm分析教授告诉我们，堆sortingalgorithm就像一堆沙砾：
想象一下，你有一个装满碎石的麻袋，你把它倒在地上：更大的石头可能会滚到底部，更小的石头（或沙子）会留在上面。
你现在把堆的顶部，并保存在你的堆的最小值。 再把剩下的堆放在你的口袋里，重复一遍。 （或者你可以得到相反的方法，并抓住你在地板上滚动的最大的石头，这个例子仍然有效）
这或多或less是我知道解释堆sorting如何工作的简单方法。
也许交互式跟踪会帮助你更好地理解algorithm。 这里是一个演示 。
我会看看我怎么回答这个问题，因为我对堆sorting的解释和堆是多less…
呃， 太可怕了 。
无论如何，首先，我们最好检查堆是什么：
正如维基百科所说，一堆是：
在计算机科学中，堆是满足堆属性的专门的基于树的数据结构：如果B是A的子节点，则密钥（A）≥密钥（B）。 这意味着具有最大密钥的元素总是在根节点中，所以这样的堆有时被称为最大堆。 （或者，如果比较结果相反，则最小的元素总是在根节点中，这导致最小堆）。
很多情况下，堆是二叉树，任何节点的所有子节点都小于该节点。
现在，堆sorting是O（ n lg（n） ）sortingalgorithm。 你可以在这里和这里读一点。 通过把所有你想要sorting的元素放到一个堆中，然后从最大的元素到最小的元素build立sorting后的数组，这个工作非常有效。 您将继续重构堆，并且由于最大的元素始终位于堆的顶部（根），因此您可以继续使用该元素并将其放在sorting后的数组的后面。 （也就是说，你会build立sorting的数组反向）
为什么这个algorithmO（ n lg（n） ）？ 由于堆上的所有操作都是O（ lg（n） ），因此您将执行n个操作，从而导致总运行时间为O（ n lg（n） ）。
我希望我可怕的咆哮帮助你！ 这有点罗嗦; 对于那个很抱歉…
堆sorting包括时间复杂度为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); } }
