Java/堆的路径
Heap ADT diagram!implementation
堆是一种特殊的树，它恰好是优先队列的有效实现。此图显示了本章中数据结构之间的关系。
figure=figs/heap_adt.eps
通常，我们尽量在 ADT 和其实现之间保持尽可能多的距离，但在堆的情况下，这种界限会略微失效。原因是我们对实现操作的性能感兴趣。对于每个实现，有一些操作很容易实现并且效率很高，而另一些则很笨拙且缓慢。
事实证明，树的数组实现作为堆的实现特别有效。数组执行良好的操作正是我们用来实现堆的操作。
为了理解这种关系，我们将分几步进行。首先，我们需要开发比较各种实现性能的方法。接下来，我们将看看堆执行的操作。最后，我们将比较优先队列的堆实现与其他实现（数组和列表），并了解为什么堆被认为特别高效。
performance analysis run time algorithm analysis
当我们比较算法时，我们希望有一种方法来判断一个算法何时比另一个算法快，或者占用更少的空间，或者使用更少的其他资源。很难详细回答这些问题，因为算法的时间和空间使用情况取决于算法的实现、正在解决的具体问题以及程序运行的硬件。
本节的目的是开发一种讨论性能的方式，该方式独立于所有这些因素，只取决于算法本身。首先，我们将关注运行时间；稍后我们将讨论其他资源。
我们的决定受到一系列约束的指导
枚举
首先，算法的性能取决于它运行的硬件，因此我们通常不会以秒之类的绝对值来谈论运行时间。相反，我们通常计算算法执行的抽象操作次数。
其次，性能通常取决于我们试图解决的具体问题——有些问题比其他问题更容易。为了比较算法，我们通常专注于最坏情况或平均（或常见）情况。
第三，性能取决于问题的规模（通常，但并非总是，集合中的元素数量）。我们通过将运行时间表示为问题规模的函数来明确地解决这种依赖关系。
最后，性能取决于实现的细节，例如对象分配开销和方法调用开销。我们通常会忽略这些细节，因为它们不会影响抽象操作数量随问题规模增加的速率。
枚举
为了使这个过程更具体，请考虑我们已经看到的两种用于对整数数组进行排序的算法。第一个是选择排序，我们在排序部分看到过。以下是我们在那里使用的伪代码。
逐字
selectionsort (array)
for (int i=0; i<array.length; i++)
// find the lowest item at or to the right of i
// swap the ith item and the lowest item
逐字
为了执行伪代码中指定的操作，我们编写了名为 findLowest 和 swap 的辅助方法。在伪代码中，findLowest 如下所示
逐字
// find the index of the lowest item between // i and the end of the array
findLowest (array, i)
// lowest contains the index of the lowest item so far
lowest = i;
for (int j=i+1; j<array.length; j++)
// compare the jth item to the lowest item so far
// if the jth item is lower, replace lowest with j
return lowest;
逐字
交换如下所示
逐字
swap (i, j)
// store a reference to the ith card in temp
// make the ith element of the array refer to the jth card
// make the jth element of the array refer to temp
逐字
为了分析这种算法的性能，第一步是决定要计算哪些操作。显然，程序做了很多事情：它递增 i，将它与牌组的长度进行比较，它搜索数组中最大的元素，等等。不清楚什么是正确的计算对象。
sorting selection sort
事实证明，一个不错的选择是比较两个项目的次数。许多其他选择最终会产生相同的结果，但这很容易做到，我们发现它使我们能够最容易地与其他排序算法进行比较。
下一步是定义“问题大小”。在本例中，自然选择是数组的大小，我们将其称为 n。
最后，我们希望推导出一个表达式，告诉我们必须执行多少个抽象操作（具体而言是比较），作为 n 的函数。
helper method
我们从分析辅助方法开始。swap 复制了几个引用，但它没有执行任何比较，因此我们忽略了执行交换所花费的时间。findLowest 从 i 开始遍历数组，将每个项目与 lowest 进行比较。我们查看的项目数量是 n，因此比较的总数是 n。
接下来，我们考虑 findLowest 被调用多少次以及每次调用的 i 值。最后一次被调用时，i 是 1，因此比较次数是 1。上一次迭代执行了 2 次比较，依此类推。在第一次迭代中，i 是 n，比较次数是 n。
因此比较的总数为 1+2+3+...+n。这个和等于 n(n+1)/2。为了描述这种算法，我们通常会忽略低阶项 (n) 并说工作总量与 n^2 成正比。由于主导项是二次的，我们也可能说这种算法是二次时间的。
quadratic time
mergesort analysis!mergesort sorting algorithm analysis
在归并排序部分，我声称归并排序花费的时间与 n log n 成正比，但我没有解释如何或为什么。现在我将解释。
同样，我们从查看算法的伪代码开始。对于归并排序，它是
逐字
mergeSort (array) // find the midpoint of the array // divide the array into two halves // sort the halves recursively // merge the two halves and return the result
逐字
在递归的每一层，我们将数组分成两半，进行两次递归调用，然后合并这两半。图形化地，该过程如下所示
figure=figs/mergetree.eps,width=5in
图中的每条线都是递归的一层。在顶部，单个数组分成两半。在底部，数组（每个数组包含一个元素）合并成数组（每个数组包含 2 个元素）。
recursion
表格的前两列显示了每一层数组的数量和每个数组中的项目数量。第三列显示了每一层递归发生的合并次数。下一列是最需要思考的：它显示了每个合并执行的比较次数。
pseudocode
如果您查看 merge 的伪代码（或您的实现），您应该相信自己，在最坏情况下，它需要 n 次比较，其中 n 是要合并的项目总数。
下一步是将每一层的合并次数乘以每次合并的工作量（比较次数）。结果是每一层的总工作量。此时，我们利用一个小技巧。我们知道最终我们只对结果中的主导项感兴趣，因此我们可以直接忽略比较次数中的 n 项。如果这样做，则每一层的总工作量只是 n。
接下来我们需要知道层数作为 n 的函数。好吧，我们从一个包含 n 个项目的数组开始，将其分成两半，直到它变成 1。这与从 1 开始，乘以 2 直到我们得到 n 相同。换句话说，我们想知道我们必须将 2 乘以自身多少次才能得到 n。答案是层数 k 等于 n 的以 2 为底的对数。
最后，我们将每层的总工作量 n 乘以层数 k 以获得 n log n，如承诺的那样。这种函数形式没有很好的名称；大多数时候人们只是说“n log n”。
一开始可能不明显 n log n 比 n^2 好，但对于 n 的较大值，它确实更好。作为练习，编写一个程序来打印 n^2 和 n log n
for a range of values of .
overhead
性能分析需要很多假设。首先，我们忽略了程序执行的大多数操作，只计算了比较。然后我们决定只考虑最坏情况性能。在分析过程中，我们随意舍入了一些东西，当我们完成后，我们随意丢弃了低阶项。
当我们解释这种分析的结果时，我们必须记住所有这些假设。因为归并排序是 n log n，我们认为它比选择排序好，但这并不意味着归并排序总是更快。这仅仅意味着最终，如果我们对越来越大的数组进行排序，归并排序会胜出。
这需要多长时间取决于实现的细节，包括除了我们计算的比较之外，每个算法执行的其他工作。这些额外工作有时被称为开销。它不影响性能分析，但会影响算法的运行时间。
例如，我们实现的归并排序实际上是在进行递归调用之前分配子数组，然后在子数组合并后让它们被垃圾回收。再次查看归并排序的图表，我们可以看到分配的总空间量与成正比，分配的总对象数量约为。所有这些分配都需要时间。
即便如此，一个好算法的糟糕实现往往比一个坏算法的好实现要好。原因是对于较大的值，好算法更好，而对于较小的值，它无关紧要，因为两种算法都足够好。
作为练习，编写一个程序来打印的值。
and for a range of values of . For what value of are they equal?
implementation!Priority Queue analysis!Priority Queue priority queue!sorted list implementation
在队列章节中，我们查看了基于数组的优先级队列实现。数组中的项目是无序的，因此添加新项目很容易（在末尾添加），但是删除项目比较困难，因为我们必须搜索具有最高优先级的项目。
另一种方法是基于排序列表的实现。在这种情况下，当我们插入新项目时，我们会遍历列表并将新项目放在正确的位置。这种实现利用了列表的一个特性，即很容易将新节点插入中间。类似地，删除具有最高优先级的项目很容易，前提是我们将其保留在列表的开头。
这些操作的性能分析很简单。无论项目数量如何，将项目添加到数组的末尾或从列表的开头删除节点都需要相同的时间。因此，两种操作都是常数时间。
constant time
无论何时遍历数组或列表，对每个元素执行常数时间操作，运行时间都与项目数量成正比。因此，从数组中删除某项和向列表中添加某项都是线性时间。
linear time
那么从优先级队列中插入和删除项目需要多长时间呢？对于数组实现，插入需要与成正比的时间，但删除需要更长的时间。第一次删除必须遍历所有项目；第二次必须遍历，依此类推，直到最后一次删除，只需要查看 1 个项目。因此，总时间为，即（仍然是）。因此，插入和删除的总时间是线性函数和二次函数的总和。结果的领先项是二次项。
列表实现的分析类似。第一次插入不需要任何遍历，但是此后，每次插入新项目时，我们都必须遍历列表的一部分。通常我们不知道要遍历列表的多少，因为这取决于数据以及插入的顺序，但我们可以假设平均我们需要遍历列表的一半。不幸的是，即使遍历列表的一半仍然是线性操作。
因此，再次，插入和删除项目需要与成正比的时间。因此，根据此分析，我们无法说哪种实现更好；数组和列表都产生二次运行时间。
如果我们使用堆来实现优先级队列，我们可以在与成正比的时间内执行插入和删除。因此，个项目的总时间为，这比要好。这就是为什么在本章开头我说堆是优先级队列的特别高效实现。
Heap!definition tree complete tree tree!complete heap property
堆是一种特殊的树。它有两个属性，这些属性通常不适用于其他树
描述
[完整性：] 这棵树是完整的，这意味着节点是从上到下，从左到右添加的，没有留下任何空隙。
[堆性：] 树中具有最高优先级的项目位于树的顶部，并且每个子树也是如此。
描述
这两个属性都需要一些解释。此图显示了一些被认为是完整或不完整的树
figure=figs/tree4.eps,width=4in
空树也被认为是完整的。我们可以通过比较子树的高度来更严格地定义完整性。回想一下，树的高度是级别数。
height
从根节点开始，如果树是完整的，那么左子树的高度和右子树的高度应该相等，或者左子树可能高出一级。在任何其他情况下，树都不能是完整的。
此外，如果树是完整的，那么子树之间的高度关系必须对树中的每个节点都成立。
将这些规则写成递归方法是很自然的
逐字
public static boolean isComplete (Tree tree)
// the null tree is complete
if (tree == null) return true;
int leftHeight = height (tree.left);
int rightHeight = height (tree.right);
int diff = leftHeight - rightHeight;
// check the root node
if (diff < 0 diff > 1) return false;
// check the children
if (!isComplete (tree.left)) return false;
return isComplete (tree.right);
逐字
对于这个例子，我使用了树的链接实现。作为练习，为数组实现编写相同的方法。同样作为练习，编写 height 方法。空树的高度为 0，叶子节点的高度为 1。
recursive definition
堆属性也类似于递归。为了使树成为堆，树中最大的值必须位于根节点，并且每个子树也必须如此。作为另一个练习，编写一个方法来检查树是否具有堆属性。
reheapify
在插入任何项目之前，我们要从堆中删除项目可能看起来很奇怪，但我认为删除更容易解释。
乍一看，我们可能会认为从堆中删除一个项目是一个常数时间操作，因为具有最高优先级的项目始终位于根节点。问题是，一旦我们删除了根节点，我们剩下的东西就不再是堆了。在我们返回结果之前，我们必须恢复堆属性。我们称此操作为重新堆化。
情况如下图所示
figure=figs/tree5.eps,height=2in
根节点的优先级为 r，有两个子树 A 和 B。子树 A 的根节点的值为 a，子树 B 的根节点的值为 b。
我们假设在我们从树中删除 r 之前，树是一个堆。这意味着 r 是堆中最大的值，a 和 b 是它们各自子树中最大的值。
一旦我们删除了 r，我们就必须将生成的树重新变成堆。换句话说，我们需要确保它具有完整性和堆性。[检查拼写]。
确保完整性的最佳方法是删除最底层的，最右边的节点，我们将其称为 c，并将它的值放在根节点。在一般的树实现中，我们必须遍历树才能找到这个节点，但在数组实现中，我们可以在常数时间内找到它，因为它始终是数组中的最后一个（非空）元素。
当然，最后一个值可能不是最大的，所以将其放在根节点会破坏堆性。[检查拼写] 属性。幸运的是，它很容易恢复。我们知道堆中最大的值是 a 或 b。因此，我们可以选择较大的一个并将其与根节点的值交换。
随意，假设 b 较大。因为我们知道它是堆中剩下的最高值，所以我们可以将其放在根节点并将 c 放在子树 B 的顶部。现在情况如下
figure=figs/tree6.eps,height=2in
再次，c 是我们从数组中最后一个条目复制的值，b 是堆中剩下的最高值。由于我们没有更改子树 A，我们知道它仍然是一个堆。唯一的问题是我们不知道子树 B 是否是一个堆，因为我们只是在它的根节点放了一个（可能是低）值。
recursion
如果我们有一个方法可以重新堆化子树 B 会不会很好？等等…我们有！
在堆中插入新项目是一个类似的操作，只不过我们不是从顶部向下传递值，而是从底部向上传递值。
同样，为了保证完整性，我们将新元素添加到树中最底层的，最右边的位置，即数组中的下一个可用空间。
然后，为了恢复堆属性，我们将新值与其邻居进行比较。情况如下
figure=figs/tree7.eps,height=2in
新值为 c。我们可以通过将 c 与 a 进行比较来恢复此子树的堆属性。如果 c 更小，则堆属性就满足了。如果 c 更大，则交换 c 和 a。交换满足堆属性，因为我们知道 c 也必须大于 b，因为 c > a 且 a > b。
现在子树已经重新堆化了，我们可以向上遍历树，直到到达根节点。
Heap!analysis analysis!Heap
对于插入和删除，我们执行一个常数时间操作来完成实际的插入和删除，但之后我们必须重新堆化树。在一种情况下，我们从根节点开始，向下遍历，比较项目，然后递归地重新堆化一个子树。在另一种情况下，我们从叶子节点开始，向上遍历，同样在树的每一层比较元素。
像往常一样，我们可能需要统计几个操作，例如比较和交换。任何选择都有效；真正的问题是我们检查的树的层数以及我们在每一层做了多少工作。在这两种情况下，我们都会继续检查树的层数，直到恢复堆属性，这意味着我们可能只访问一层，或者在最坏情况下，我们可能必须访问所有层。让我们考虑最坏的情况。
在每一层，我们只执行常数时间操作，例如比较和交换。因此，总工作量与树的层数成正比，也就是高度。
所以我们可以说这些操作相对于树的高度是线性的，但是我们感兴趣的“问题大小”不是高度，而是堆中的项目数量。
作为n的函数，树的高度是log₂(n+1)。这并不适用于所有树，但对于完全树而言是正确的。要了解原因，请考虑树中每一层节点的数量。第一层包含 1 个，第二层包含 2 个，第三层包含 4 个，依此类推。第k层包含
nodes, and the total number in all levels up to is
2^(k-1) 个节点。换句话说，n = 2^(k-1) - 1，这意味着 k = log₂(n+1)。
logarithmic time
因此，插入和删除都花费对数时间。插入和删除项目需要与log₂(n+1)成正比的时间。
heapsort sorting analysis!heapsort
上一节的结果表明了另一种排序算法。给定n个项目，我们将它们插入到一个堆中，然后将它们移除。由于堆语义，它们按顺序输出。我们已经证明了这种算法，称为堆排序，需要与n*log₂(n+1)成正比的时间，这比选择排序好，与归并排序相同。
随着n的值变大，我们期望堆排序比选择排序更快，但性能分析无法让我们知道它是否会比归并排序更快。我们会说这两种算法具有相同的增长阶，因为它们以相同的函数形式增长。另一种说法是它们属于同一个复杂度类。
big-O notation complexity class order of growth constant time linear time quadratic time logarithmic time
复杂度类有时用“大O符号”表示。例如，O(n²)（读作“n平方阶”）是所有增长速度不快于n²的大型n值函数的集合。说一个算法是O(n²)等同于说它是二次的。我们已经看到其他复杂度类，按性能递减的顺序排列：
0.2in tabularll
& constant time
& logarithmic
& linear
& ``en log en
& quadratic
& exponential
tabular 0.2in
到目前为止，我们查看过的算法中没有一个是指数级的。对于较大的n值，这些算法很快变得不切实际。然而，“指数增长”这个词在非技术语言中也经常出现。它经常被误用，所以我希望包含它的技术含义。
人们经常使用“指数级”来描述任何增加且加速的曲线（即具有正斜率和曲率的曲线）。当然，还有许多其他曲线符合这种描述，包括二次函数（和更高阶的多项式），甚至像n²这样的温和函数。大多数这些曲线都没有指数的（通常是有害的）爆炸性行为。
作为一个练习，比较2^n和n²的行为，随着n的值增加。
selection sort mergesort heapsort complexity class order of growth overhead
描述
[选择排序:] 排序部分中的简单排序算法。
[归并排序:] 归并排序部分中的更高级排序算法。
[堆排序:] 另一种排序算法。
[复杂度类:] 一组算法，其性能（通常是运行时间）具有相同的增长阶。
[增长阶:] 一组具有相同主导项的函数，因此对于较大的n值具有相同的定性行为。
[开销:] 在执行性能分析中考虑的抽象操作之外执行其他操作的程序消耗的额外时间或资源。