普林斯顿算法讲义（二）（1）

2.2 归并排序

原文：algs4.cs.princeton.edu/22mergesort

译者：飞龙

协议：CC BY-NC-SA 4.0

我们在本节中考虑的算法基于一种简单的操作，称为合并：将两个有序数组组合成一个更大的有序数组。这个操作立即适用于一种简单的递归排序方法，称为归并排序：将数组分成两半，对这两半进行排序（递归），然后合并结果。

归并排序保证以与 N log N 成正比的时间对 N 个项目的数组进行排序���无论输入是什么。它的主要缺点是它使用与 N 成正比的额外空间。

抽象原地归并。

Merge.java 中的方法merge(a, lo, mid, hi)将子数组a[lo..mid]与a[mid+1..hi]的归并结果放入一个有序数组中，将结果留在a[lo..hi]中。虽然希望实现这种方法而不使用大量额外空间，但这样的解决方案非常复杂。相反，merge()将所有内容复制到辅助数组，然后再次归并到原始数组。

自顶向下的归并排序。

Merge.java 是基于这种抽象原地归并的递归归并排序实现。这是利用分治范式进行高效算法设计的最著名的例子之一。

命题。

自顶向下的归并排序使用 1/2 N lg N 和 N lg N 比较，并且最多需要 6 N lg N 次数组访问来对长度为 N 的任何数组进行排序。

改进。

通过对实现进行一些经过深思熟虑的修改，我们可以大大减少归并排序的运行时间。

• 对小子数组使用插入排序。 通过对待处理的小情况进行不同处理，我们可以改进大多数递归算法。对小子数组使用插入排序将使典型归并排序实现的运行时间提高 10 到 15％。
  
• 测试数组是否已经有序。 通过添加一个测试来跳过对merge()的调用，如果a[mid]小于或等于a[mid+1]，我们可以将已经有序的数组的运行时间减少为线性。通过这种改变，我们仍然执行所有递归调用，但对于任何已排序的子数组，运行时间是线性的。
  
• 消除对辅助数组的复制。 可以消除用于归并的辅助数组的复制时间（但不是空间）。为此，我们使用两次调用排序方法，一次从给定数组中获取输入并将排序后的输出放入辅助数组；另一次从辅助数组中获取输入并将排序后的输出放入给定数组。通过这种方法，在一些令人费解的递归技巧中，我们可以安排递归调用，使计算在每个级别切换输入数组和辅助数组的角色。
  

MergeX.java 实现了这些改进。

可视化。

MergeBars.java 提供了带有小子数组截止的归并排序可视化。

自底向上的归并排序。

即使我们考虑将两个大子数组合并在一起，事实上大多数合并都是将微小的子数组合并在一起。 另一种实现归并排序的方法是组织合并，使我们在一次遍历中执行所有微小数组的合并，然后进行第二次遍历以成对合并这些数组，依此类推，直到进行涵盖整个数组的合并。 这种方法比标准递归实现需要更少的代码。 我们首先进行 1 对 1 的合并（将单个项目视为大小为 1 的子数组），然后进行 2 对 2 的合并（合并大小为 2 的子数组以生成大小为 4 的子数组），然后进行 4 对 4 的合并，依此类推。 MergeBU.java 是底部向上归并排序的实现。

命题。

底部向上的归并排序使用了介于 1/2 N lg N 和 N lg N 次比较，以及最多 6 N lg N 次数组访问来对长度为 N 的任意数组进行排序。

命题。

没有基于比较的排序算法可以保证使用少于 lg(N!) ~ N lg N 次比较对 N 个项目进行排序。

命题。

归并排序是一种渐进最优的基于比较的排序算法。 也就是说，归并排序在最坏情况下使用的比较次数以及任何基于比较的排序算法可以保证的最小比较次数都是~N lg N。

练习

1. 给出追踪，展示如何使用自顶向下的归并排序和自底向上的归并排序对键E A S Y Q U E S T I O N进行排序的方式。
   解决方案。

1. 回答底部向上归并排序的练习 2.2.2。
   解决方案。

1. 如果抽象的原地合并仅在两个输入子数组按排序顺序排列时才产生正确的输出，那么是否正确？ 证明你的答案，或提供一个反例。
   解决方案。 是的。如果子数组按排序顺序排列，那么原地合并会产生正确的输出。 如果一个子数组未按排序顺序排列，则其条目将按照它们在输入中出现的顺序出现在输出中（与另一个子数组的条目交错）。
   
2. 给出自顶向下和自底向上归并排序算法在 n = 39 时每次合并后的子数组大小序列。解决方案。

• 自顶向下的归并排序：2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 3, 2, 5, 10, 20, 2, 3, 2, 5, 2, 3, 2, 5, 10, 2, 3, 2, 5, 2, 2, 4, 9, 19, 39。
  
• 底部向上的归并排序：2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 8, 8, 8, 8, 7, 16, 16, 32, 39。查看代码 MergeSizes.java。
  

3. 假设自顶向下的归并排序修改为在a[mid] <= a[mid+1]时跳过对merge()的调用。 证明对于已排序顺序的数组，使用的比较次数是线性的。
   解决方案。 由于数组已经排序，不会调用merge()。 当 N 是 2 的幂时，比较次数将满足递归 T(N) = 2 T(N/2) + 1，其中 T(1) = 0。
   
4. 在库软件中使用类似 aux[]的静态数组是不明智的，因为多个客户端可能同时使用该类。给出一个不使用静态数组的 Merge.java 实现。
   

创造性问题

1. 更快的合并。 实现一个merge()的版本，将a[]的后半部分以递减顺序复制到aux[]，然后将其合并回a[]。 这个改变允许你从内部循环中删除测试每个半部分是否已耗尽的代码。 注意：结果排序不是稳定的。

private static void merge(Comparable[] a, int lo, int mid, int hi) { 
   for (int i = lo; i <= mid; i++)
      aux[i] = a[i]; 
   for (int j = mid+1; j <= hi; j++)
      aux[j] = a[hi-j+mid+1];
   int i = lo, j = hi; 
   for (int k = lo; k <= hi; k++) 
      if (less(aux[j], aux[i])) a[k] = aux[j--];
      else                      a[k] = aux[i++];
} 

1. 改进。 编写一个程序 MergeX.java，实现文本中描述的三个归并排序改进：添加对小子数组的截止，测试数组是否已经有序，通过在递归代码中切换参数来避免复制。
   
2. 逆序数。 开发并实现一个线性对数算法 Inversions.java，用于计算给定数组中的逆序数（插入排序为该数组执行的交换次数—参见第 2.1 节）。这个数量与 Kendall tau 距离 有关；参见第 2.5 节。
   
3. 索引排序。 开发一个版本的 Merge.java，该版本不重新排列数组，而是返回一个 int[] perm，使得 perm[i] 是数组中第 i 小的条目的索引。
   

实验

网络练习

1. 每个项最多进行 log N 次比较的归并。 设计一个合并算法，使得每个项最多比较对数次数。 （在标准合并算法中，当合并大小为 N/2 的两个子数组时，一个项可以比较 N/2 次。）
   参考链接
   
2. 对于排序 Young 表格的下界。 一个 Young 表格 是一个 N×N 矩阵，使得条目在列和行上都是有序的。证明对于排序 N² 个条目（只能通过成对比较访问数据）需要 Theta(N² log N) 次比较。
   解决方案概述。如果条目 (i, j) 在 i + j 的 1/2 范围内，则所有 2N-1 个网格对角线彼此独立。对对角线进行排序需要 N² log N 次比较。
   
3. 给定一个大小为 2N 的数组 a，其中前 N 个项按升序排列在位置 0 到 N-1，以及一个大小为 N 的数组 b，其中 N 个项按升序排列，将数组 b 合并到数组 a 中，使得 a 包含所有项按升序排列。使用 O(1) 额外内存。
   提示：从右向左合并。
   
4. k-近排序。 假设你有一个包含 N 个不同项的数组 a[]，几乎是有序的：每个项最多离其在排序顺序中的位置不超过 k 个位置。设计一个算法，在时间复杂度为 N log k 的情况下对数组进行排序。
   提示：首先，对从 0 到 2k 的子数组进行排序；最小的 k 个项将处于正确的位置。接下来，对从 k 到 3k 的子数组进行排序；最小的 2k 个项现在将处于正确的位置。
   
5. 找到一组输入，对于这组输入，归并排序比对包含 N 个不同键的数组进行排序时的比较次数严格少于 1/2 N lg N。
   解决方案：一个 N = 2^k + 1 个键的逆序排序数组使用大约 1/2 N lg N - (k/2 - 1) 次比较。
   
6. 最坏情况的输入数组。 编写一个程序 MergeWorstCase.java，该程序接受一个命令行参数 n，并创建一个长度为 n 的输入数组，使得归并排序进行最大数量的比较。
   
7. 编写一个程序 SecureShuffle.java，从标准输入中读取一系列字符串并进行安全洗牌。使用以下算法：将每张卡片与一个介于 0 和 1 之间的随机实数关联起来。根据其关联的实数对值进行排序。使用 java.security.SecureRandom 生成随机实数。使用 Merge.indexSort() 获取随机排列。
   
8. 合并两个不同���度的数组。 给定大小为 M 和 N 的两个有序数组 a[] 和 b[]，其中 M ≥ N，设计一个算法将它们合并成一个新的有序数组 c[]，使用 ~ N lg M 次比较。
   提示：使用二分查找。
   注意：存在一个 下界 为 Omega(N log (1 + M/N)) 次比较。这是因为有 M+N 个 N 个可能的合并结果。决策树论证表明，这至少需要 lg (M+N 个 N) 次比较。我们注意到 n 个 r 个选择 >= (n/r)^r。
   
9. 合并三个数组。 给定大小为 N 的三个有序数组 a[]、b[] 和 c[]，设计一个算法将它们合并成一个新的有序数组 d[]，在最坏情况下最多使用 ~ 6 N 次比较（或者，更好地说，~ 5 N 次比较）。
   
10. 合并三个数组。 给定三个大小为 N 的排序数组 a[]、b[] 和 c[]，证明没有基于比较的算法可以在最坏情况下使用少于 ~ 4.754887503 N 次比较将它们合并成一个新的排序数组 d[]。
    
11. 具有 N^(3/2)逆序对的数组。 证明任何基于比较的算法，可以对具有 N^(3/2)或更少逆序对的数组进行排序，在最坏情况下必须进行 ~ 1/2 N lg N 次比较。
    证明概要：将数组分成 sqrt(N) 个连续的子数组，每个子数组有 sqrt(N) 个项目，使得不同子数组之间没有逆序对，但每个子数组内的项目顺序是任意的。这样的数组最多有 N^(3/2) 个逆序对——每个 sqrt(N) 子数组中最多有 ~N/2 个逆序对。根据排序的下界，对每个子数组进行排序需要 ~ sqrt(N) lg sqrt(N) 次比较，总共需要 ~ 1/2 N lg N 次比较。
    
12. 最优非遗忘排序。 设计算法，使用最少的比较次数（在最坏情况下）对长度为 3、4、5、6、7 和 8 的数组进行排序。
    解决方案。 已知最优解使用 3、5、7、10、13 和 16 次比较，分别。已知 Ford-Johnson 合并插入算法对于 n <= 13 是最优的。在最坏情况下，它需要进行 sum(ceil(log2), k=1…n) 次比较。
    

2.3 快速排序

原文：algs4.cs.princeton.edu/23quicksort

译者：飞龙

协议：CC BY-NC-SA 4.0

快速排序很受欢迎，因为它不难实现，适用于各种不同类型的输入数据，并且在典型应用中比任何其他排序方法都要快得多。它是原地排序（仅使用一个小型辅助栈），平均需要时间与 N log N 成正比来对 N 个项进行排序，并且具有极短的内部循环。

基本算法。

快速排序是一种分而治之的排序方法。它通过分区数组为两部分，然后独立对这两部分进行排序。方法的关键在于分区过程，该过程重新排列数组以满足以下三个条件：

• 条目a[j]在数组中处于最终位置，对于某个j。
  
• a[lo]到a[j-1]中没有任何条目大于a[j]。
  
• a[j+1]到a[hi]中没有任何条目小于a[j]。
  

我们通过分区实现完整排序，然后递归地将该方法应用于子数组。这是一种随机化算法，因为它在对数组进行排序之前对数组进行随机洗牌。

分区。

要完成实现，我们需要实现分区方法。我们采用以下一般策略：首先，我们任意选择a[lo]作为分区项—即将进入最终位置的项。接下来，我们从数组的左端开始扫描，直到找到一个大于（或等于）分区项的条目，然后我们从数组的右端开始扫描，直到找到一个小于（或等于）分区项的条目。停止扫描的两个条目在最终分区数组中是不正确的，因此我们交换它们。当扫描索引交叉时，为了完成分区过程，我们只需将分区项a[lo]与左子数组的最右边的条目（a[j]）交换并返回其索引j。

快速排序。

Quick.java 是一个使用上述分区方法的快速排序实现。

实现细节。

在实现快速排序方面存在一些微妙的问题，这些问题反映在这段代码中，并值得一提。

• 原地分区。 如果我们使用额外的数组，分区就很容易实现，但并不比将分区版本复���回原始数组的额外成本值得。
  
• 保持边界。 如果数组中最小项或最大项是分区项，我们必须注意指针不要跑到数组的左端或右端。
  
• 保持随机性。 随机洗牌使数组处于随机顺序。由于它均匀对待子数组中的所有项，Quick.java 具有其两个子数组也处于随机顺序的特性。这一事实对算法的可预测性至关重要。保持随机性的另一种方法是在partition()中选择一个随机项进行分区。
  
• 终止循环。 正确测试指针是否交叉比起初看起来要棘手一些。一个常见的错误是忽略了数组可能包含其他与分区项相同值的键。
  
• 处理具有与划分项目键相等的键的项目。 最好停止扫描具有大于或等于划分项目键的键的项目的左扫描，以及停止扫描具有小于或等于划分项目键的键的项目的右扫描。尽管这种策略似乎会导致涉及具有与划分项目键相等的键的项目的不必要的交换，但这对于避免在某些典型应用程序中出现二次运行时间至关重要。
  
• 终止递归。 在实现快速排序时的一个常见错误是没有确保始终将一个项目放在正确位置，然后当划分项目恰好是数组中最大或最小的项目时，陷入无限递归循环。
  

命题。

快速排序平均使用~2 N ln N 次比较（和其中六分之一的交换）来对具有不同键的长度为 N 的数组进行排序。

命题。

快速排序在最坏情况下使用~N²/2 次比较，但随机洗牌可以防止这种情况发生。

运行时间的标准偏差约为 0.65 N，因此随着 N 的增长，运行时间趋于平均值，并且不太可能远离平均值。在您的计算机上对大数组进行排序时，快速排序使用二次比较的概率远小于您的计算机被闪电击中的概率！

改进。

快速排序是由 C. A. R. Hoare 于 1960 年发明的，并自那时以来一直被许多人研究和完善。

• 切换到插入排序。 与归并排序一样，对于微小数组，切换到插入排序是值得的。截断的最佳值取决于系统，但在大多数情况下，任何值在 5 到 15 之间可能都能很好地工作。
  
• 三取样划分。 改进快速排序性能的另一种简单方法是使用从数组中取出的一小部分项目的中位数作为划分项目。这样做将给出一个稍微更好的划分，但需要计算中位数的成本。事实证明，大部分可用的改进来自选择大小为 3 的样本（然后在中间项目上进行划分）。
  

可视化。

QuickBars.java 使用三取样划分和对小子数组进行截断的快速排序进行可视化。

熵最优排序。

在应用程序中经常出现具有大量重复排序键的数组。在这种应用程序中，有可能将排序时间从线性对数减少到线性。

一个直接的想法是将数组划分为三部分，分别用于具有小于、等于和大于划分项目键的项目。完成这种划分是一个经典的编程练习，由 E. W. Dijkstra 推广为荷兰国旗问题，因为它类似于对具有三种可能键值的数组进行排序，这可能对应于国旗上的三种颜色。

Dijkstra 的解决方案基于数组的单向左到右遍历，维护指针lt，使得a[lo..lt-1]小于v，指针gt，使得a[gt+1..hi]大于v，指针i，使得a[lt..i-1]等于 v，a[i..gt]尚未检查。

从i等于lo开始，我们使用Comparable接口给出的 3 路比较来处理a[i]，以处理三种可能的情况：

• a[i]小于v：交换a[lt]和a[i]，并同时增加lt和i
  
• a[i]大于v：交换a[i]和a[gt]，并减少gt
  
• a[i]等于v：增加i
  

Quick3way.java 是这种方法的一个实现。

命题。

三路划分的快速排序是熵最优的。

可视化。

Quick3wayBars.java 可视化了使用三向切分的快速排序。

练习

1. 展示partition()如何以E A S Y Q U E S T I O N数组进行划分的跟踪风格。

1. 展示快速排序如何对数组E A S Y Q U E S T I O N进行排序的快速排序跟踪风格。（在这个练习中，忽略初始洗牌。）

1. 编写一个程序 Sort2distinct.java，对已知只包含两个不同关键值的数组进行排序。
   
2. 当对一个包含 N 个相同项的数组进行排序时，Quick.sort()会进行多少次比较？
   解决方案。 〜 N lg N 次比较。每个划分将数组分成两半，加上或减去一个。
   
3. 展示熵最优排序如何首先对数组B A B A B A B A C A D A B R A进行划分的跟踪风格。

创造性问题

1. 螺母和螺栓。（G. J. E. Rawlins）。你有一堆混合的 N 个螺母和 N 个螺栓，需要快速找到相应的螺母和螺栓配对。每个螺母恰好匹配一个螺栓，每个螺栓恰好匹配一个螺母。通过将螺母和螺栓配对，你可以看出哪个更大。但不能直接比较两个螺母或两个螺栓。给出一个解决问题的高效方法。
   提示：根据问题定制快速排序。顺便说一句：对于这个问题，已知只有一个非常复杂的确定性 O(N log N)算法。
   
2. 最佳情况。 编写一个程序 QuickBest.java，为Quick.sort()生成一个最佳情况数组（无重复项）：一个包含 N 个不同键的数组，具有每个划分产生的子数组大小最多相差 1 的特性（与 N 个相等键的数组产生相同子数组大小的情况相同）。在这个练习中，忽略初始洗牌。

1. 快速三向切分。（J. Bentley 和 D. McIlroy）。实现一个基于保持相等键在子数组的左右两端的熵最优排序 QuickBentleyMcIlroy.java。维护索引 p 和 q，使得 a[lo…p-1]和 a[q+1…hi]都等于 a[lo]，一个索引 i，使得 a[p…i-1]都小于 a[lo]，一个索引 j，使得 a[j+1…q]都大于 a[lo]。在内部划分循环代码中添加代码，如果 a[i]等于 v，则交换 a[i]和 a[p]（并增加 p），如果 a[j]等于 v，则交换 a[j]和 a[q]（并减少 q），然后再进行通常的 a[i]和 a[j]与 v 的比较。在划分循环结束后，添加代码将相等的键交换到正确位置。
   

网络练习

1. QuickKR.java 是最简单的快速排序实现之一，并出现在 K+R 中。说服自己它是正确的。它将如何执行？所有相等的键呢？
   
2. 随机化快速排序。 修改partition()，使其总是从数组中均匀随机选择划分项（而不是最初对数组进行洗牌）。与 Quick.java 比较性能。
   
3. Antiquicksort. Java 6 中用于对原始类型进行排序的算法是由 Bentley 和 McIlroy 开发的 3 路快速排序的变体。对于实践中出现的大多数输入，包括已经排序的输入，它非常高效。然而，使用 M. D. McIlroy 在 A Killer Adversary for Quicksort 中描述的巧妙技术，可以构造使系统排序在二次时间内运行的病态输入。更糟糕的是，它会溢出函数调用堆栈。要看到 Java 6 中的排序库崩溃，请尝试一些不同大小的致命输入：10,000, 20,000, 50,000, 100,000, 250,000, 500,000, 和 1,000,000。您可以使用程序 IntegerSort.java 进行测试，该程序接受一个命令行输入 N，从标准输入读取 N 个整数，并使用系统排序对它们进行排序。
   
4. 糟糕的分区。 当所有键相等时，不停止在相等键上会使快速排序变为二次的原因是什么？
   解决方案。 这是在我们在相等键上停止时对 AAAAAAAAAAAAAAA 进行分区的结果。它将数组不均匀地分成了一个大小为 0 的子问题和一个大小为 14 的子问题。

1. 这是在我们在相等键上停止时对 AAAAAAAAAAAAAAA 进行分区的结果。它将数组均匀地分成了两个大小为 7 的子问题。

1. 将项目与自身进行比较。 展示我们的快速排序实现可以将项目与自身进行比较，即对某个索引 i 调用 less(i, i)。修改我们的实现，使其永远不会将项目与自身进行比较。
   
2. 霍尔原始快速排序。 实现霍尔原始快速排序算法的一个版本。它类似于我们的两路分区算法，只是枢轴不会交换到其最终位置。相反，枢轴留在两个子数组中的一个，没有元素固定在其最终位置，指针交叉的两个子数组会递归排序。
   解决方案。 HoareQuick.java。我们注意到，虽然这个版本非常优雅，但它不会保留子数组中的随机性。根据 Sedgewick 的博士论文，“这种偏差不仅使方法的分析几乎不可能，而且还会显著减慢排序过程。”
   
3. 双轴快速排序。 实现 Yaroslavskiy 的双轴快速排序的版本。
   解决方案。 QuickDualPivot.java 是一个非常类似于 Quick3way.java 的实现。
   
4. 三轴快速排序。 实现类似 Kushagra-Ortiz-Qiao-Munro 的三轴快速排序的版本。
   
5. 比较次数。 给出一个长度为 n 的数组族，使得标准快速排序分区算法进行 (i) n + 1 次比较，(ii) n 次比较，(iii) n - 1 次比较，或者证明不存在这样的数组族。
   解决方案：升序；降序；无。
   

2.4 优先队列

原文：algs4.cs.princeton.edu/24pq

译者：飞龙

协议：CC BY-NC-SA 4.0

许多应用程序要求我们按顺序处理具有键的项目，但不一定是完全排序的顺序，也不一定一次处理所有项目。通常，我们收集一组项目，然后处理具有最大键的项目，然后可能收集更多项目，然后处理具有当前最大键的项目，依此类推。在这种环境中，一个适当的数据类型支持两个操作：删除最大和插入。这样的数据类型称为优先队列。

API。

优先队列的特点是删除最大和插入操作。按照惯例，我们将仅使用less()方法比较键，就像我们对排序所做的那样。因此，如果记录可以具有重复的键，最大意味着具有最大键值的任何记录。为了完善 API，我们还需要添加构造函数和测试是否为空操作。为了灵活性，我们使用一个实现了Comparable的通用类型Key的通用实现。

程序 TopM.java 是一个优先队列客户端，它接受一个命令行参数M，从标准输入读取交易，并打印出M个最大的交易。

基本实现。

我们在第 1.3 节中讨论的基本数据结构为我们提供了四个立即的实现优先队列的起点。

• 数组表示（无序）。 也许最简单的优先队列实现是基于我们的推入栈代码。优先队列中插入的代码与栈中的推入相同。要实现删除最大，我们可以添加类似于选择排序的内部循环的代码，将最大项与末尾的项交换，然后删除那个，就像我们对栈的pop()所做的那样。程序 UnorderedArrayMaxPQ.java 使用这种方法实现了一个优先队列。
  
• 数组表示（有序）。 另一种方法是添加插入的代码，将较大的条目向右移动一个位置，从而保持数组中的条目有序（就像插入排序一样）。因此，最大的项始终在末尾，优先队列中删除最大的代码与栈中的弹出相同。程序 OrderedArrayMaxPQ.java 使用这种方法实现了一个优先队列。
  
• 链表表示（无序和反向有序）。 类似地，我们可以从我们的推入栈的链表代码开始，修改pop()的代码以找到并返回最大值，或者修改push()的代码以保持项目以相反顺序，并修改pop()的代码以取消链接并返回列表中的第一个（最大）项目。
  

所有刚讨论的基本实现都具有插入或删除最大操作在最坏情况下需要线性时间的特性。找到一个保证两个操作都快速的实现是一个更有趣的任务，也是本节的主要内容。

堆定义。

二叉堆是一种数据结构，可以高效支持基本的优先队列操作。在二叉堆中，项目存储在一个数组中，使得每个键都保证大于（或等于）另外两个特定位置的键。反过来，这两个键中的每一个必须大于另外两个键，依此类推。如果我们将键视为在具有从每个键到已知较小键的两个键的边的二叉树结构中，这种排序是很容易看到的。

定义。 如果每个节点中的键大于（或等于）该节点的两个子节点（如果有的话）中的键，则二叉树是堆有序的。

命题。 堆有序二叉树中最大的键位于根节点。

我们可以对任何二叉树施加堆排序限制。然而，使用像下面这样的完全二叉树特别方便。

我们通过层级顺序在数组中顺序表示完全二叉树，根位于位置 1，其子节点位于位置 2 和 3，它们的子节点位于位置 4、5、6 和 7，依此类推。

定义。 二叉堆是一组按照完全堆排序的二叉树中的键排列的节点集合，在数组中按层级顺序表示（不使用第一个条目）。

在堆中，位置为 k 的节点的父节点在位置 k/2；反之，位置为 k 的节点的两个子节点在位置 2k 和 2k + 1。我们可以通过对数组索引进行简单算术来上下移动：从 a[k] 向上移动树，我们将 k 设置为 k/2；向下移动树，我们将 k 设置为 2k 或 2k+1。

堆上的算法。

我们在长度为 n + 1 的私有数组 pq[] 中表示大小为 n 的堆，其中 pq[0] 未使用，堆在 pq[1] 到 pq[n] 中。我们仅通过私有辅助函数 less() 和 exch() 访问键。我们考虑的堆操作通过首先进行可能违反堆条件的简单修改，然后通���遍历堆，根据需要修改堆以确保堆条件在任何地方都得到满足来工作。我们将这个过程称为重新堆化，或恢复堆顺序。

• 自底向上重新堆化（上浮）。如果堆顺序被违反，因为一个节点的键变大于该节点的父节点的键，那么我们可以通过将节点与其父节点交换来向修复违规迈进。交换后，节点比其两个子节点都大（一个是旧父节点，另一个比旧父节点小，因为它是该节点的子节点），但节点可能仍然比其父节点大。我们可以以相同的方式修复该违规，依此类推，向上移动堆，直到到达具有较大键的节点，或根节点。

private void swim(int k) {
   while (k > 1 && less(k/2, k)) {
      exch(k, k/2);
      k = k/2;
   }
}

普林斯顿算法讲义（二）（2）https://developer.aliyun.com/article/1484173