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

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

• 自顶向下堆化（下沉）。如果堆顺序被违反，因为一个节点的键变小于一个或两个子节点的键，那么我们可以通过将节点与其两个子节点中较大的一个交换来向修复违规迈进。这种交换可能导致子节点违规；我们以相同的方式修复该违规，依此类推，向下移动堆，直到到达两个子节点都较小或底部的节点。

private void sink(int k) {
   while (2*k <= N) {
      int j = 2*k;
      if (j < N && less(j, j+1)) j++;
      if (!less(k, j)) break;
      exch(k, j);
      k = j;
   }
}

基于堆的优先队列。

这些 sink() 和 swim() 操作为优先队列 API 的高效实现提供了基础，如下图所示，并在 MaxPQ.java 和 MinPQ.java 中实现。

• 插入。我们在数组末尾添加新项，增加堆的大小，然后通过该项向上游走以恢复堆的条件。
  
• 移除最大值。我们将顶部的最大项取出，将堆的末尾项放在顶部，减少堆的大小，然后通过该项向下沉入堆中以恢复堆的条件。
  

命题。 在一个包含 n 项的优先队列中，堆算法对插入最多需要 1 + lg n 次比较，对移除最大值最多需要 2 lg n 次比较。

实际考虑。

我们以几个实际考虑结束对堆优先队列 API 的研究。

• 多路堆。修改我们的代码以构建基于完整堆排序三元或d元树的数组表示并不困难。在降低树高度的较低成本和在每个节点找到三个或d个子节点中最大成本��间存在权衡。
  
• 数组调整。我们可以添加一个无参数构造函数，在insert()中添加数组加倍的代码，在delMax()中添加数组减半的代码，就像我们在第 1.3 节中为堆栈所做的那样。当优先队列的大小是任意的且数组被调整大小时，对数时间界是摊销的。
  
• 键的不可变性。优先队列包含由客户端创建的对象，但假设客户端代码不会更改键（这可能会使堆的不变性无效）。
  
• 索引优先队列。在许多应用中，允许客户端引用已经在优先队列中的项目是有意义的。一种简单的方法是为每个项目关联一个唯一的整数索引。
  IndexMinPQ.java 是这个 API 的基于堆的实现；IndexMaxPQ.java 类似，但用于面向最大的优先队列。Multiway.java 是一个客户端，将几个排序的输入流合并成一个排序的输出流。
  

堆排序。

我们可以使用任何优先队列来开发排序方法。我们将所有要排序的键插入到面向最小的优先队列中，然后重复使用删除最小值按顺序删除它们。当使用堆作为优先队列时，我们获得堆排序。

着眼于排序任务，我们放弃了隐藏优先队列的堆表示的概念，并直接使用swim()和sink()。这样做允许我们在不需要任何额外空间的情况下对数组进行排序，通过在要排序的数组内维护堆。堆排序分为两个阶段：堆构造，在这个阶段我们将原始数组重新组织成堆，和sortdown，在这个阶段我们按递减顺序从堆中取出项目以构建排序结果。

• 堆构造。我们可以在时间上按比例完成这项任务n lg n，通过从数组的左侧到右侧进行，使用swim()来确保扫描指针左侧的条目组成一个堆排序完整树，就像连续的优先队列插入一样。一个更有效的巧妙方法是从右到左进行，使用sink()来随着我们的前进制作子堆。数组中的每个位置都是一个小子堆的根；sink()也适用于这样的子堆。如果一个节点的两个子节点是堆，那么在该节点上调用sink()会使根在那里的子树成为堆。
  
• Sortdown。在堆排序期间，大部分工作是在第二阶段完成的，在这个阶段我们从堆中移除剩余的最大项目，并将其放入数组位置中，随着堆的缩小而腾出。
  

Heap.java 是堆排序的完整实现。下面是每次下沉后数组内容的跟踪。

命题。 基于 sink 的堆构造是线性时间的。

命题。 堆排序使用少于 2 n lg n 次比较和交换来对 n 个项目进行排序。

在 sortdown 期间重新插入堆中的大多数项目都会一直到底部。因此，我们可以通过避免检查项目是否已到达其位置来节省时间，简单地提升两个子节点中较大的一个，直到到达底部，然后沿着堆向上移动到正确的位置。这个想法通过增加额外的簿记来减少了比较次数。

练习

1. 假设序列

P R I O * R * * I * T * Y * * * Q U E * * * U * E

1. （其中字母表示插入，星号表示删除最大值）应用于最初为空的优先队列。给出删除最大值操作返回的值序列。
   解决方案。R R P O T Y I I U Q E U（PQ 上剩下 E）
2. 批评以下想法：为了在常数时间内实现查找最大值，为什么不跟踪迄今为止插入的最大值，然后在查找最大值时返回该值？
   解决方案。在删除最大值操作后，需要从头开始更新最大值。
   
3. 提供支持插入和删除最大值的优先队列实现，每种实现对应一个基础数据结构：无序数组、有序数组、无序链表和有序链表。给出您在上一个练习中四种实现的每个操作的最坏情况下界的表格。
   部分解决方案。OrderedArrayMaxPQ.java 和 UnorderedArrayMaxPQ.java
   
4. 排序为降序的数组是否是面向最大值的堆。
   答案。是的。
   
5. 假设您的应用程序将有大量插入操作，但只有少量删除最大值操作。您认为哪种优先队列实现最有效：堆、无序数组、有序数组？
   答案。无序数组。插入是常数时间。
   
6. 假设您的应用程序将有大量查找最大值操作，但相对较少的插入和删除最大值操作。您认为哪种优先队列实现最有效：堆、无序数组、有序数组？
   答案。有序数组。在常数时间内找到最大值。
   
7. 在一个没有重复键的大小为n的堆中，删除最大值操作期间必须交换的最小项数是多少？给出一个大小为 15 的堆，使得最小值得以实现。对连续两次和三次删除最大值操作，回答相同的问题。
   部分答案：(a) 2。
   
8. 设计一个线性时间的认证算法来检查数组pq[]是否是一个面向最小值的堆。
   解决方案。参见 MinPQ.java 中的isMinHeap()方法。
   
9. 证明基于下沉的堆构建最多使用 2n次比较和最多n次交换。解决方案。只需证明基于下沉的堆构建使用的交换次数少于n次，因为比较次数最多是交换次数的两倍。为简单起见，假设二叉堆是完美的（即每一层都完全填满的二叉树）且高度为h。我们定义树中节点的高度为以该节点为根的子树的高度。当一个高度为k的键被下沉时，它最多可以与其下面的k个键交换。由于在高度k处有 2^(h−k)个节点，总交换次数最多为：KaTeX parse error: No such environment: eqnarray* at position 8: \begin{̲e̲q̲n̲a̲r̲r̲a̲y̲*̲}̲ h + 2(h-1) + 4…第一个等式是针对非标准求和的，但通过数学归纳法很容易验证该公式成立。第二个等式成立是因为高度为h的完美二叉树有 2^(h+1) − 1 个节点。证明当二叉树不完美时结果成立需要更加小心。您可以使用以下事实来证明：在具有n个节点的二叉堆中，高度为k的节点的数量最多为 ceil(n/ 2^(k+1))。替代解决方案。我们定义树中节点的高度为以该节点为根的子树的高度。

• 首先，观察到一个具有n个节点的二叉堆有n − 1 个链接（因为每个链接是一个节点的父节点，每个节点都有一个父链接，除了根节点）。
  
• 下沉一个高度为k的节点最多需要k次交换。
  
• 我们将对每个高度为k的节点收取k个链接，但不一定是在下沉节点时所采取的路径上的链接。相反，我们对从节点沿着左-右-右-右-…路径的k个链接收费。例如，在下图中，根节点收取 4 个红色链接；蓝色节点收取 3 个蓝色链接；依此类推。
  
• 注意，没有链接会被收费超过一个节点。（仅通过从根节点向右链接获得的链接不会被收费给任何节点。）
  
• 因此，总交换次数最多为n。由于每次交换最多有 2 次比较，因此比较次数最多为 2n。
  

创意问题

1. 计算数论。 编写一个程序 CubeSum.java，打印出所有形式为(a³ + b³)的整数，其中(a)和(b)是介于 0 和(n)之间的整数，按排序顺序打印，而不使用过多的空间。也就是说，不要计算一个包含(n²)个和并对它们进行排序的数组，而是构建一个最小导向的优先队列，最初包含((0³, 0, 0), (1³ + 1³, 1, 1), (2³ + 2³, 2, 2), \ldots, (n³ + n³, n, n))。然后，在优先队列非空时，移除最小项(i³ + j³,; i, ; j))，打印它，然后，如果(j < n)，插入项((i³ + (j+1)³,; i,; j+1))。使用这个程序找到所有介于 0 和(10⁶)之间的不同整数(a, b, c)和(d)，使得(a³ + b³ = c³ + d³)，例如(1729 = 9³ + 10³ = 1³ + 12³)。
   
2. 查找最小值。 在 MaxPQ.java 中添加一个min()方法。你的实现应该使用恒定的时间和额外的空间。
   解决方案：添加一个额外的实例变量，指向最小项。在每次调用insert()后更新它。如果优先队列变为空，则将其重置为null。
   
3. 动态中位数查找。 设计一个数据类型，支持对数时间的插入，常数时间的查找中位数，以及对数时间的删除中位数。
   解决方案。 将中位数键保留在 v 中；对于小于 v 键的键，使用一个最大导向的堆；对于大于 v 键的键，使用一个最小导向的堆。要插入，将新键添加到适当的堆中，用从该堆中提取的键替换 v。
   
4. 下界。 证明不可能开发一个 MinPQ API 的实现，使得插入和删除最小值都保证使用~n log log n比较。
   解决方案。 这将产生一个n log log n比较排序算法（插入n个项目，然后重复删除最小值），违反了第 2.3 节的命题。
   
5. 索引优先队列实现。 通过修改 MaxPQ.java 来实现 IndexMaxPQ.java：将pq[]更改为保存索引，添加一个数组keys[]来保存键值，并添加一个数组qp[]，它是pq[]的逆——qp[i]给出i在pq[]中的位置（索引j，使得pq[j]是i）。然后修改代码以维护这些数据结构。使用约定，如果i不在队列中，则qp[i]为-1，并包括一个测试此条件的方法contains()。您需要修改辅助方法exch()和less()，但不需��修改sink()或swim()。
   

网络练习

1. 堆排序的最佳、平均和最差情况。 对于对长度为n的数组进行堆排序，最佳情况、平均情况和最差情况的比较次数分别是多少？
   解决方案。 如果允许重复项，最佳情况是线性时间（n个相等的键）；如果不允许重复项，最佳情况是~n lg n比较（但最佳情况输入是非平凡的）。平均情况和最差情况的比较次数是~2 n lg n比较。详细信息请参阅堆排序的分析。
   
2. 堆化的最佳和最差情况。 对于n个项目的数组进行堆化所需的最少和最多比较/交换次数是多少？
   解决方案。 对包含n个项目的数组进行降序堆化需要 0 次交换和n − 1 次比较。对包含n个项目的数组进行升序堆化需要~ n次交换和~ 2n次比较。
   
3. 出租车数。 找到可以用两种不同方式的整数立方和表示的最小整数（1,729），三种不同方式（87,539,319），四种不同方式（6,963,472,309,248），五种不同方式（48,988,659,276,962,496），以及六种不同方式（24,153,319,581,254,312,065,344）。这样的整数被命名为出租车数以纪念著名的拉马努金故事。目前尚不清楚可以用七种不同方式表示为整数立方和的最小整数。编写一个程序 Taxicab.java，该程序读取一个命令行参数 N，并打印出所有非平凡解 a³ + b³ = c³ + d³，其中 a、b、c 和 d 小于或等于 N。
   
4. 计算数论。 找到方程 a + 2b² = 3c³ + 4d⁴的所有解，其中 a、b、c 和 d 小于 100,000。提示：使用一个最小堆和一个最大堆。
   
5. 中断处理。 在编写可以被中断的实时系统时（例如，通过鼠标点击或无线连接），需要立即处理中断，然后再继续当前活动。如果中断应按照到达的顺序处理，则 FIFO 队列是适当的数据结构。然而，如果不同的中断具有不同的优先级（例如，），则需要优先级队列。
   
6. 排队网络的模拟。 M/M/1 队列用于双并行队列等。数学上难以分析复杂的排队网络。因此使用模拟来绘制等待时间分布等。需要优先级队列来确定下一个要处理的事件。
   
7. Zipf 分布。 使用前面练习的结果从具有参数 s 和n的Zipf 分布中进行抽样。该分布可以取 1 到n之间的整数值，并以概率 1/k^s / sum_(i = 1 to n) 1/i^s 取值 k。例如：莎士比亚的戏剧《哈姆雷特》中的单词，s 约等于 1。
   
8. 随机过程。 从n个箱子开始，每个箱子包含一个球。随机选择其中一个n个球，并将球随机移动到一个箱���中，使得球被放置在具有m个球的箱子中的概率为m/n。经过多次迭代后，结果是什么样的球分布？使用上述描述的随机抽样方法使模拟更有效率。
   
9. 最近邻。 给定长度为m的n个向量 x[1]、x[2]、…、x[N]和另一个相同长度的向量x，找到距离x最近的 20 个向量。
   
10. 在一张图纸上画圆。 编写一个程序来找到以原点为中心，与整数 x 和 y 坐标的 32 个点相切的圆的半径。提示：寻找一个可以用几种不同方式表示为两个平方和的数字。答案：有两个勾股三元组的斜边为 25：15² + 20² = 25²，7² + 24² = 25²，得到 20 个这样的格点；有 22 个不同的斜边为 5,525 的勾股三元组；这导致 180 个格点。27,625 是比 64 更多的最小半径。154,136,450 有 35 个勾股三元组。
    
11. 完美幂。 编写一个程序 PerfectPower.java 来打印所有可以表示为 64 位long整数的完美幂：4, 8, 9, 16, 25, 27, … 完美幂是可以写成 a^b 的数字，其中 a 和 b ≥ 2 为整数。
    
12. 浮点加法。 添加n个浮点数，避免舍入误差。删除最小的两个：将它们相加，然后重新插入。
    
13. 首次适应装箱。 17/10 OPT + 2, 11/9 OPT + 4（递减）。使用最大锦标赛树，其中选手是 N 个箱子，值=可用容量。
    
14. 具有最小/最大值的栈。 设计一个数据类型，支持推入、弹出、大小、最小值和最大值（其中最小值和最大值是栈上的最小和最大项目）。所有操作在最坏情况下应该花费常数时间。
    *提示：*将每个栈条目与当前栈上的最小和最大项目关联起来。
    
15. 具有最小/最大值的队列。 设计一个数据类型，支持入队、出队、大小、最小值和最大值（其中最小值和最大值是队列上的最小和最大项目）。所有操作应该在常摊时间内完成。
    *提示：*完成前面的练习，并模拟使用两个栈的队列。
    
16. 2^i + 5^j。 按升序打印形式为 2^i * 5^j 的数字。
    
17. 最小-最大堆。设计一个数据结构，通过将项目放入大小为n的单个数组中，支持常数时间内的最小值和最大值，以及对数时间内的插入、删除最小值和删除最大值，具有以下属性：

• 数组表示一个完全二叉树。
  
• 偶数级别节点中的键小于（或等于）其子树中的键；奇数级别节点中的键大于（或等于）其子树中的键。请注意，最大值存储在根节点，最小值存储在根节点的一个子节点中。
  

18. 解决方案。 最小-最大堆和广义优先队列
    
19. 范围最小查询。 给定一个包含n个项目的序列，从索引 i 到 j 的范围最小查询是 i 和 j 之间最小项目的索引。设计一个数据结构，在线性时间内预处理n个项目的序列，以支持对数时间内的范围最小查询。
    
20. 证明具有n个节点的完全二叉树恰好有*ceiling(n/2)*个叶节点（没有子节点的节点）。
    
21. 具有最小值的最大导向优先队列。 在最大导向的二叉堆中查找最小键的运行时间增长顺序是什么。
    *解决方案：线性—最小键可能在任何一个ceiling(n/2)*个叶节点中。
    
22. 具有最小值的最大导向优先队列。 设计一个数据类型，支持对数时间内的插入和删除最大值，以及常数时间内的最大值和最小值。
    解决方案。 创建一个最大导向的二叉堆，并存储迄今为止插入的最小键（除非此堆变为空，否则永远不会增加）。
    
23. 大于 x 的第 k 个最大项目。 给定一个最大导向的二叉堆，设计一个算法来确定第 k 个最大项目是否大于或等于 x。你的算法应该在与 k 成比例的时间内运行。
    *解决方案：*如果节点中的键大于或等于 x，则递归搜索左子树和右子树。当探索的节点数等于 k 时停止（答案是是），或者没有更多节点可探索时（否）。
    
24. 最小导向二叉堆中的第 k 个最小项目。 设计一个 k log k 算法，找到包含n个项目的最小导向二叉堆 H 中的第 k 个最小项目。
    解决方案。 构建一个新的最小导向堆 H’。我们不会修改 H。将 H 的根插入 H’中，同时插入其堆索引 1。现在，重复删除 H’中的最小项目 x，并将 x 的两个子项从 H 插入 H’。从 H’中删除的第 k 个项目是 H 中第 k 小的项目。
    
25. 随机队列。 实现一个RandomQueue，使得每个操作都保证最多花费对数时间。*提示：*不能承受数组加倍。使用链表无法以 O(1)时间定位随机元素。相反，使用具有显式链接的完全二叉树。
    
26. 具有随机删除的 FIFO 队列。 实现一个支持以下操作的数据类型：插入一个项目，删除最近添加的项目，和删除一个随机项目。每个操作在最坏情况下应该花费（最多）对数时间。
    解决方案：使用具有显式链接的完全二叉树；为添加到数据结构中的第 i 个项目分配长整型优先级i。
    
27. 两个排序数组的前 k 个和。 给定两个长度为n的排序数组 a[]和 b[]，找到形式为 a[i] + b[j]的最大 k 个和。
    提示：使用优先队列（类似于出租车问题），您可以实现一个 O(k log n)算法。令人惊讶的是，可以在 O(k)时间内完成，但是算法比较复杂。
    
28. 堆构建的实证分析。 通过实证比较线性时间的自底向上堆构建和朴素的线性对数时间的自顶向下堆构建。一定要在一系列n值上进行比较。LaMarca 和 Ladner报告称，由于缓存局部性，对于大n值（当堆不再适合缓存时），朴素算法在实践中可能表现更好，即使后者执行的比较和交换要少得多。
    
29. 多路堆的实证分析。 实证比较 2-、4-和 8 路堆的性能。LaMarca 和 Ladner提出了几种优化方法，考虑了缓存效果。
    
30. 堆排序的实证分析。 实证比较 2-、4-和 8 路堆排序的性能。LaMarca 和 Ladner提出了几种优化方法，考虑了缓存效果。他们的数据表明，经过优化（并调整内存）的 8 路堆排序可以比经典堆排序快两倍。
    
31. 通过插入堆化。 假设您通过反复将下一个键插入二叉堆来在n个键上构建二叉堆。证明总比较次数最多为~ n lg n。
    答案：比较次数最多为 lg 1 + lg 2 + … + lg n = lg (n!) ~ n lg n。
    
32. **堆化下界。（Gonnet 和 Munro）**证明任何基于比较的二叉堆构建算法在最坏情况下至少需要~1.3644 N 次比较。
    答案：使用信息论论证，类似于排序下界。对于 n 个不同键的 n!个可能堆（N 个整数的排列），但有许多堆对应于相同的排序。例如，有两个堆（c a b 和 c b a），对应于 3 个元素 a < b < c。对于完美堆（n = 2^h - 1），有 A(h) = n! / prod((2^k-1)(2^(h-k)), k=1…h)个堆对应于n个元素 a[0] < a[1] < … < a[n-1]。（参见Sloane 序列 A056971。）因此，任何算法必须能够输出 P(h) = prod((2^k-1)(2^(h-k)), k=1…h)可能的答案之一。使用一些花哨的数学，��可以证明 lg P(h) ~ 1.3644 n。
    注意：通过对手论证，下界可以改进为~ 3/2 n（Carlsson–Chen）；该问题的最佳已知算法在最坏情况下需要~ 1.625 n次比较（Gonnet 和 Munro）。
    
33. 股票交易撮合引擎。 连续限价订单簿：交易员不断发布买入或卖出股票的竞价。限价订单意味着买方（卖方）以指定价格或以下（或以上）的价格下达购买（出售）一定数量给定股票的订单。订单簿显示买单和卖单，并按价格然后按时间对其进行排名。匹配引擎匹配兼容的买家和卖家；如果存在多个可能的买家，则通过选择最早下单的买家来打破平局。为每支股票使用两个优先队列，一个用于买家，一个用于卖家。
    金融市场电子交易。
    
34. 随机二叉堆。 假设您用 1 到 n 的整数的随机排列填充长度为 n 的数组。对于 n = 5 和 6，生成的数组是最小定向二叉堆的概率是多少？
    解决方案：分别为 1/15 和 1/36。这里有一个很好的讨论。
    

2.5 排序应用

原文：algs4.cs.princeton.edu/25applications

译者：飞龙

协议：CC BY-NC-SA 4.0

排序算法和优先队列在各种应用中被广泛使用。本节的目的是简要概述其中一些应用。

对各种类型的数据进行排序。

我们的实现对Comparable对象的数组进行排序。这种 Java 约定允许我们使用 Java 的回调机制对实现了Comparable接口的任何类型的对象数组进行排序。

• 事务示例。 程序 Transaction.java 基于事务发生时间实现了事务数据类型的Comparable接口。
  
• 指针排序。 我们正在使用的方法在经典文献中被称为指针排序，因为我们处理的是对键的引用，而不是移动数据本身。
  
• 键是不可变的。 如果允许客户在排序后更改键的值，那么数组可能不会保持排序。在 Java 中，通过使用不可变键来确保键值不变是明智的。
  
• 交换成本低廉。 使用引用的另一个优点是我们避免了移动完整项的成本。引用方法使得交换的成本在一般情况下大致等于比较的成本。
  
• 备用排序。 有许多应用程序，我们希望根据情况使用两种不同的顺序对我们正在排序的对象。Java 的Comparator接口有一个名为compare()的公共方法，用于比较两个对象。如果我们有一个实现了此接口的数据类型，我们可以将Comparator传递给sort()（它传递给less()）如 Insertion.java 中所示。
  
• 具有多个键的项。 在典型应用中，项具有多个可能需要用作排序键的实例变量。在我们的事务示例中，一个客户可能需要按帐号号码对事务列表进行排序；另一个客户可能需要按地点对列表进行排序；其他客户可能需要使用其他字段作为排序键。我们可以定义多个比较器，如 Transaction.java 中所示。
  
• 具有比较器的优先队列。 使用比较器的灵活性对于优先队列也很有用。MaxPQ.java 和 MinPQ.java 包括一个以Comparator作为参数的构造函数。
  
• 稳定性。 如果排序方法在数组中保留相等键的相对顺序，则称其为稳定。例如，在我们的互联网商务应用中，我们按照事务到达的顺序将其输入到数组中，因此它们按照数组中的时间字段顺序排列。现在假设应用程序要求将事务按位置分开以进行进一步处理。一个简单的方法是按位置对数组进行排序。如果排序是不稳定的，那么每个城市的事务在排序后可能不一定按时间顺序排列。我们在本章中考虑的一些排序方法是稳定的（插入排序和归并排序）；许多排序方法则不是（选择排序、希尔排序、快速排序和堆排序）。
  

我应该使用哪种排序算法？

确定哪种算法是最佳的取决于应用和实现的细节，但我们已经研究了一些通用方法，它们在各种应用中几乎与最佳方法一样有效。下表是一个概括我们在本章中研究的排序算法的重要特征的一般指南。

性质。 快速排序是最快的通用排序方法。

在大多数实际情况下，快速排序是首选方法。如果稳定性很重要且有空间可用，则归并排序可能是最佳选择。在一些性能关键的应用中，重点可能仅仅是对数字进行排序，因此可以避免使用引用的成本，而是对原始类型进行排序。

• 排序原始类型。 我们可以通过将Comparable替换为原始类型名称，并将对less()的调用替换为类似a[i] < a[j]的代码，为原始类型开发更高效的排序代码。但是，对于浮点类型，需要注意处理-0.0 和 NaN。
  
• Java 系统排序。Java 的主要系统排序方法Arrays.sort()在java.util库中表示一组重载方法：

• 每种原始类型的不同方法。
  
• 一种用于实现Comparable的数据类型的方法。
  
• 一种使用Comparator的方法。
  

• Java 的系统程序员选择使用快速排序（带有 3 路分区）来实现原始类型方法，并使用归并排序来实现引用类型方法。这些选择的主要实际影响是在速度和内存使用（对于原始类型）与稳定性和性能保证（对于引用类型）之间进行权衡。
  

缩减。

我们可以使用排序算法来解决其他问题的想法是算法设计中一种基本技术的例子，称为缩减。缩减是一种情况，其中为一个问题开发的算法用于解决另一个问题。我们从一些排序的基本示例开始。

• 重复项。 在一个包含Comparable对象的数组中是否有重复的键？数组中有多少个不同的键？哪个值出现最频繁？通过排序，您可以在线性对数时间内回答这些问题：首先对数组进行排序，然后通过排序后的数组进行一次遍历，注意在有序数组中连续出现的重复值。
  
• 排名。 一个排列（或排名）是一个包含 N 个整数的数组，其中 0 到 N-1 之间的每个整数恰好出现一次。两个排名之间的Kendall tau 距离是在两个排名中顺序不同的对数。例如，0 3 1 6 2 5 4和1 0 3 6 4 2 5之间的 Kendall tau 距离是四，因为在两个排名中，对 0-1、3-1、2-4、5-4 的顺序不同，但所有其他对的顺序相同。
  
• 优先队列缩减。 在第 2.4 节中，我们考虑了两个问题的示例，这些问题可以简化为对优先队列的一系列操作。TopM.java 在输入流中找到具有最高键的 M 个项目。Multiway.java 将 M 个排序的输入流合并在一起，以生成一个排序的输出流。这两个问题都可以通过大小为 M 的优先队列轻松解决。
  
• 中位数和顺序统计。与排序相关的一个重要应用是找到一组键的中位数（具有一半键不大于它，一半键不小于它的值）。这个操作在统计学和其他各种数据处理应用中是一个常见的计算。找到中位数是选择的一个特殊情况：找到一组数字中第 k 小的数字。通过排序，可以很容易在线性对数时间内解决这个问题。方法select()我们描述了一种在线性时间内解决问题的方法：维护变量lo和hi来限定包含要选择的项目的索引k的子数组，并使用快速排序分区来缩小子数组的大小，如下所示：

• 如果k等于j，那么我们完成了。
  
• 否则，如果k < j，那么我们需要继续在左子数组中工作（通过将hi的值更改为j-1）
  
• 否则，如果k > j，那么我们需要继续在右子数组中工作（通过将lo更改为j+1）。
  

• 区间收缩，直到只剩下k。终止时，a[k]包含第(k+1)小的条目，a[0]到a[k-1]都小于（或等于）a[k]，而a[k+1]到数组末尾都大于（或等于）a[k]。
  select() 方法在 Quick.java 中实现了这种方法，但在客户端需要进行类型转换。QuickPedantic.java 中的select()方法是更加严谨的代码，避免了需要进行类型转换。
  

对排序应用的简要调查。

• 商业计算。 政府机构、金融机构和商业企业通过对信息进行排序来组织大部分信息。无论信息是按名称或编号排序的账户、按时间或地点排序的交易、按邮政编码或地址排序的邮件、按名称或日期排序的文件，还是其他任何信息，处理这些数据肯定会涉及到某种排序算法。
  
• 搜索信息。 将数据保持有序可以通过经典的二分搜索算法高效地搜索数据。
  
• 运筹学。 假设我们有 N 个工作要完成，其中第 j 个工作需要 t[j]秒的处理时间。我们需要完成所有工作，但希望通过最小化工作的平均完成时间来最大化客户满意度。最短处理时间优先规则，即按处理时间递增顺序安排工作，已知可以实现这一目标。另一个例子是负载平衡问题，其中我们有 M 个相同的处理器和 N 个工作要完成，我们的目标是在处理器上安排所有工作，以便最后一个工作完成的时间尽可能早。这个具体问题是 NP 难题（参见第六章），因此我们不指望找到一个实际的方法来计算最佳的安排。已知一种能够产生良好安排的方法是最长处理时间优先规则，即按处理时间递减顺序考虑工作，将每个工作分配给最先可用的处理器。
  
• 事件驱动模拟。 许多科学应用涉及模拟，计算的目的是模拟现实世界的某个方面，以便更好地理解它。进行这种模拟可能需要适当的算法和数据结构。我们在第 6.1 节中考虑了一个粒子碰撞模拟，说明了这一点。
  
• 数值计算。 科学计算通常关注准确性（我们距离真实答案有多接近？）。当我们进行数百万次计算时，准确性非常重要，特别是在使用计算机上常见的浮点数表示实数时。一些数值算法使用优先队列和排序来控制计算中的准确性。
  
• 组合搜索。 人工智能中的一个经典范例是定义一组配置，其中每个配置都有从一个配置到下一个配置的明确定义的移动和与每个移动相关联的优先级。还定义了一个起始配置和一个目标配置（对应于已解决问题）。A算法*是一个问题解决过程，其中我们将起始配置放在优先队列中，然后执行以下操作直到达到目标：移除优先级最高的配置，并将可以通过一次移动到达的所有配置添加到队列中（不包括刚刚移除的配置）���
  
• 普里姆算法和迪杰斯特拉算法是处理图的经典算法。优先队列在组织图搜索中起着基础性作用，实现高效的算法。
  
• Kruskal 算法是另一��经典的图算法，其边具有权重，取决于按权重顺序处理边。其运行时间由排序的成本主导。
  
• 赫夫曼压缩是一种经典的数据压缩算法，它依赖于通过将具有整数权重的一组项目组合起来，以产生一个新的项目，其权重是其两个组成部分的和。使用优先队列立即实现此操作。
  
• 字符串处理算法通常基于排序。例如，我们将讨论基于首先对字符串后缀进行排序的算法，用于查找一组字符串中的最长公共前缀以及给定字符串中的最长重复子字符串。
  

练习

1. 考虑String的compareTo()方法的以下实现。第三行如何提高效率？

public int compareTo(String t) {
   String s = this;
   if (s == t) return 0;  // this line
   int n = Math.min(s.length(), t.length());
   for (int i = 0; i < n; i++) {
      if      (s.charAt(i) < t.charAt(i)) return -1;
      else if (s.charAt(i) > t.charAt(i)) return +1;
   }
   return s.length() - t.length();
}

1. 解决方案：如果s和t是对同一字符串的引用，则避免直接比较单个字符。
2. 批评下面的类实现，该类旨在表示客户账户余额。为什么compareTo()是Comparable接口的一个有缺陷的实现？

public class Customer implements Comparable<Customer> {
    private String name;
    private double balance;
    public int compareTo(Customer that) {
        if (this.balance < that.balance - 0.005) return -1;
        if (this.balance > that.balance + 0.005) return +1; 
        return 0;
   }
}

1. 解决方案：它违反了Comparable合同。可能a.compareTo(b)和b.compareTo(c)都为 0，但a.compareTo(c)为正（或负）。
2. 解释为什么选择排序不稳定。
   解决方案。 它交换非相邻元素。在下面的示例中，第一个 B 被交换到第二个 B 的右侧。

1. 编写一个程序 Frequency.java，从标准输入读取字符串，并按频率降序打印每个字符串出现的次数。
   

创造性问题

1. 调度。 编写一个程序 SPT.java，从标准输入读取作业名称和处理时间，并打印一个最小化平均完成时间的调度，如文本中所述。
   
2. 负载平衡。 编写一个程序 LPT.java，将整数 M 作为命令行参数，从标准输入读取 N 个作业名称和处理时间，并打印一个调度分配作业给 M 个处理器，以近似最小化最后一个作业完成的时间，如文本中所述。
   备注。 结果解决方案保证在最佳解决方案的 33%之内（实际上为 4/3 - 1/(3N)）。
   
3. 按反向域排序。 编写一个数据类型 Domain.java，表示域名，包括一个适当的compareTo()方法，其中自然顺序是反向域名顺序。例如，cs.princeton.edu的反向域是edu.princeton.cs。这对于 Web 日志分析很有用。编写一个客户端，从标准输入读取域名，并按排序顺序打印反向域。
   
4. 垃圾邮件活动。 要发起非法的垃圾邮件活动，您有一个来自各种域的电子邮件地址列表（即在@符号后面的电子邮件地址部分）。为了更好地伪造寄件人地址，您希望从同一域的另一个用户发送电子邮件。例如，您可能想要伪造从 wayne@princeton.edu 发送到 rs@princeton.edu 的电子邮件。您将如何处理电子邮件列表以使此成为一个高效的任务？
   解决方案。 首先按照反向域排序。
   
5. 公正选举。 为了防止对字母表末尾出现的候选人产生偏见，加利福尼亚州通过以下顺序对其 2003 年州长选票上出现的候选人进行排序：

R W Q O J M V A H B S G Z X N T C I E K U P D Y F L

1. 创建一个数据类型 California.java，其中这是自然顺序。编写一个客户端，根据此顺序对字符串进行排序。假设每个字符串仅由大写字母组成。
2. 肯德尔距离。 编写一个程序 KendallTau.java，以线性对数时间计算两个排列之间的肯德尔距离。
   
3. **稳定的优先队列。**开发一个稳定的优先队列实现 StableMinPQ.java（返回以插入顺序返回重复键）。
   
4. **平面上的点。**为 Point2D.java 数据类型编写三个static静态比较器，一个按照它们的 x 坐标比较点，一个按照它们的 y 坐标比较点，一个按照它们与原点的距离比较点。为 Point2D 数据类型编写两个非静态比较器，一个按照它们到指定点的距离比较，一个按照它们相对于指定点的极角比较。
   
5. **一维区间数据类型。**为 Interval1D.java 编写三个static比较器，一个按照它们的左端点比较区间，一个按照它们的右端点比较区间，一个按照它们的长度比较区间。
   
6. **按名称对文件进行排序。**编写一个程序 FileSorter.java，该程序接受一个目录名称作为命令行输入，并按文件名打印出当前目录中的所有文件。提示：使用java.io.File数据类型。
   
7. **博纳定理。**真或假：如果对矩阵的每一列进行排序，然后对每一行进行排序，那么列仍然是有序的。解释你的答案。
   答案。正确。
   
8. **不同值。**编写一个程序 Distinct.java，它接受整数 M、N 和 T 作为命令行参数，然后使用文本中给出的代码执行以下实验的 T 次试验：生成 0 到 M-1 之间的 N 个随机整数值，并计算生成的不同值的数量。将程序运行 T = 10 和 N = 10³、10⁴、10⁵ 和 10⁶，其中 M = 1/2 N、N 和 2N。概率论表明，不同值的数量应该约为 M(1 - e^(-alpha))，其中 alpha = N/M—打印一个表格来帮助您确认您的实验验证了这个公式。
   

Web 练习

1. **计数器数据类型。**修改 Counter.java，使其实现Comparable接口，通过计数比较计数器。
   
2. **成绩数据类型。**编写一个程序 Grade.java 来表示成绩的数据类型（A、B+等）。它应该使用 GPA 对成绩进行自然排序，实现Comparable接口。
   
3. **学生数据类型。**编写一个数据类型 Student.java，表示大学课程中的学生。每个学生应该有一个登录名（String）、一个部分号（整数）和一个成绩（Grade）。
   
4. **不区分大小写的顺序。**编写一个代码片段，读取一系列字符串并按升序排序，忽略大��写。

String[] a = new String[N];
for (int i = 0; i < N. i++) {
   a[i] = StdIn.readString();
}
Arrays.sort(a, String.CASE_INSENSITIVE_ORDER);

1. **不区分大小写的比较器。**实现自己版本的比较器String.CASE_INSENSITIVE_ORDER。

public class CaseInsensitive implements Comparator<String> {
   public int compare(String a, String b) {
      return a.compareToIgnoreCase(b);
   }
}

1. **降序字符串比较器。**实现一个比较器，按降序而不是升序对字符串进行排序。

public class Descending implements Comparator<String> {
   public int compare(String a, String b) {
      return b.compareToIgnoreCase(a);
   }
}

1. 或者，您可以使用Collections.reverseOrder()。它返回一个Comparator，它施加实现Comparable接口的对象的自然顺序的反向排序。
2. **按非英语字母表排序字符串。**编写一个程序，根据非英语字母表对字符串进行排序，包括重音符号、分音符号和像西班牙语中的 ch 这样的预组合字符。
   提示：使用 Java 的java.text.Collator API。例如，在 UNICODE 中，Rico在Réal之前按字典顺序出现，但在法语中，Réal首先出现。

import java.util.Arrays;
import java.text.Collator;
...
Arrays.sort(words, Collator.getInstance(Locale.FRENCH));

1. 史密斯规则。 在供应链管理中出现了以下问题。你有一堆工作要在一台机器上安排。（给出例子。）工作 j 需要 p[j]单位的处理时间。工作 j 有一个正权重 w[j]，表示其相对重要性 - 将其视为存储原材料的库存成本为工作 j 存储 1 个时间单位。如果工作 j 在时间 t 完成处理，那么它的��本为 t * w[j]美元。目标是安排工作的顺序，以最小化每个工作的加权完成时间之和。编写一个程序SmithsRule.java，它从命令行参数 N 和由它们的处理时间 p[j]和权重 w[j]指定的 N 个工作列表中读取，并输出一个最佳的处理工作顺序。提示： 使用史密斯规则：按照处理时间与权重比率的顺序安排工作。这种贪婪规则事实证明是最优的。
   
2. 押韵的词。对于你的诗歌课程，你想要列出一张押韵词的列表。完成这个任务的一种简单方法如下：

• 将一个单词字典读入一个字符串数组中。
  
• 将每个单词的字母倒转，例如，confound变为dnuofnoc。
  
• 对结果数组中的单词进行排序。
  
• 将每个单词的字母倒转回原始状态。
  

3. 现在单词confound将会与astound和compound等单词相邻。编写一个程序 Rhymer.java，从标准输入中读取一系列单词，并按照上述指定的顺序打印它们。
   现在重复一遍，但使用一个自定义的Comparator，按从右到左的字典顺序排序。
   
4. 众数。 给出一个 O(N log N)的算法，用于计算序列 N 个整数中出现最频繁的值。
   
5. 最接近的 1 维对。 给定一个包含 N 个实数的序列，找到值最接近的整数对。给出一个 O(N log N)的算法。
   
6. 最远的 1 维对。 给定一个包含 N 个实数的序列，找到值最远的整数对。给出一个 O(N)的算法。
   
7. 具有许多重复项的排序。 假设你有一个包含 N 个元素的序列，其中最多有 log N 个不同的元素。描述如何在 O(N log log N)时间内对它们进行排序。
   
8. 几乎有序。 给定一个包含 N 个元素的数组，每个元素最多离其目标位置 k 个位置，设计一个能在 O(N log k)时间内排序的算法。
   
9. 对链表进行排序。 给定一个包含 N 个元素的单链表，如何在保证 O(N log N)时间内、稳定地、且只使用 O(1)额外空间的情况下对其进行排序？
   
10. Goofysort（Jim Huggins）。 论证 Goofy.java 按升序对数组进行排序。作为要排序的项目数量 N 的函数，最佳情况运行时间是多少？作为要排序的项目数量 N 的函数，最坏情况运行时间是多少？
    
11. 令人愉悦的区间。给定一个包含 N 个非负整数的数组（代表一个人每天的情感值），一个区间的幸福度是该区间中值的总和乘以该区间中最小的整数。设计一个 O(N log N)的分治算法来找到最幸福的区间。解决方案。这里是一个归并排序风格的解决方案。

• 将元素分为中间部分：a[l…m-1]，a[m]，a[m+1…r]
  
• 递归地计算左半部分中的最佳区间
  
• 递归地计算右半部分中的最佳区间
  
• 计算包含 a[m]的最佳区间
  
• 返回三个区间中最佳的一个为了效率的关键步骤是在线性时间内计算包含a[m]的最佳区间。这里是一个贪婪的解决方案：如果包含a[m]的最佳区间只包含一个元素，那就是a[m]。如果包含多于一个元素，那么必须包含a[m-1]和a[m+1]中较大的一个，所以将其添加到区间中。重复这个过程，以此类推。返回通过这个过程构建的任何大小的最佳区间。
  

12. Equality detector. 假设你有 N 个元素，并且想确定至少有 N/2 个元素相等。假设你只能执行相等性测试操作。设计一个算法，在 O(N log N) 次相等性测试中找到一个代表元素（如果存在的话）。提示：分治法。注意：也可以在 O(N) 次测试中完成。
    
13. Maxima. 给定平面上的 n 个点集，点 (xi, yi) 支配点 (xj, yj) 如果 xi > xj 并且 yi > yj。极大值是一个不被集合中任何其他点支配的点。设计一个 O(n log n) 的算法来找到所有极大值。应用：在 x ��上是空间效率，在 y 轴上是时间效率。极大值是有用的算法。提示：根据 x 坐标升序排序；从右到左扫描，记录迄今为止看到的最高 y 值，并将其标记为极大值。
    
14. Min and max. 给定一个包含 N 个元素的数组，尽可能少地比较找到最小值和最大值。暴力法：找到最大值（N-1 次比较），然后找到剩余元素的最小值（N-2 次比较）。
    Solution 1. 分治法：在每一半中找到最小值和最大值（2T(N/2) 次比较），返回 2 的最小值和 2 的最大值（2 次比较）。T(1) = 0，T(2) = 1，T(N) = 2T(N/2) + 2。递归解：T(N) = ceil(3N/2) - 2。
    Solution 2. 将元素分成一对一对，并比较每对中的两个元素。将最小的元素放在 A 中，最大的元素放在 B 中。如果 n 是奇数，将元素 n 放在 A 和 B 中。这需要 floor(n/2) 次比较。现在直接计算 A 中的最小值（ceil(n/2) - 1 次比较）和 B 中的最大值（ceil(N/2) - 1 次比较）。[事实上，这是最佳的解决方案。]
    
15. Sorting by reversals. [ Mihai Patrascu] 给定一个数组 a[1…n]，使用以下类型的操作进行排序：选择两个索引 i 和 j，并反转 a[i…j] 中的元素。这个操作的成本为 j-i+1。目标：O(n log² n)。
    
16. L1 norm. 平面上有 N 个电路元件。你需要沿电路运行一根特殊的导线（平行于 x 轴）。每个电路元件必须连接到特殊导线。你应该把特殊导线放在哪里？提示：中位数最小化 L1 范数。
    
17. Median given two sorted arrays. 给定大小为 N[1] 和 N[2] 的两个已排序数组，以 O(log N) 时间找到所有元素的中位数，其中 N = N[1] + N[2]。或者在 O(log k) 时间内找到第 k 大的元素。
    
18. Three nearby numbers in an array. 给定一个浮点数数组 a[]，设计一个线性对数时间复杂度的算法，找到三个不同的整数 i, j, 和 k，使得 |a[i] - a[j]| + |a[j] - a[k]| + |a[k] - a[i]| 最小。
    Hint: 如果 a[i] <= a[j] <= a[k]，那么 |a[i] - a[j]| + |a[j] - a[k]| + |a[k] - a[i]| = 2 (a[k] - a[i])。
    
19. Three nearby numbers in three arrays. 给定三个浮点数数组 a[], b[], 和 c[]，设计一个线性对数时间复杂度的算法，找到三个整数 i, j, 和 k，使得 |a[i] - b[j]| + |b[j] - c[k]| + |c[k] - a[i]| 最小。
    
20. Minimum dot product. 给定相同长度的两个向量，找到两个向量的点积尽可能小的排列。
    
21. Two-sum. 给定一个包含 N 个整数的数组，设计一个线性对数时间复杂度的算法，找到一对整数，使它们的和最接近零。
    Solution: 按绝对值排序，最佳对现在是相邻的。
    
22. 3-sum in quadratic time. 3-sum 问题是在整数数组中找到和最接近零的三元组。描述一个使用线性空间和二次时间的解决方案。
    Hint：解决以下子问题。给定 N 个整数的排序列表和目标整数 x，在线性时间内确定最接近 x 的两个整数。
    
23. Bandwidth. 给定带宽要求的区间，找到最大带宽需求（以及需要该最大带宽的区间）。
    解决方案。 按开始时间对区间进行排序；按照这个顺序将区间插入 PQ，但使用结束时间作为键。在插入下一个区间之前，比较其开始时间与 PQ 上最小区间的结束时间：如果大于，删除 PQ 上的最小区间。始终跟踪 PQ 上的累积带宽。
    
24. 时间戳。 给定 N 个时间戳，当文件从 Web 服务器请求时，找到没有文件到达的最长时间间隔。解决方案：按时间戳排序。扫描排序列表以识别最大间隙。 （与空闲时间相同。）
    
25. 票务范围。 给定一个形式为 A1、A2、A11、A10、B7、B9、B8、B3 的票务座位列表，找到最大的非空相邻座位块，例如，A3-A9。 （与空闲时间相同。）
    
26. 十进制主导。 给定一个具有 N 个可比较键的数组，设计一个算法来检查是否有一个值出现的次数超过 N/10 次。你的算法应该在期望的线性时间内运行。
    解决方案。 使用快速选择找到第 N/10 大的值；检查它是否是主导值；如果不是，在具有 9N/10 个值的子数组中递归。
    或者，使用 9 个计数器。
    
27. 局部最小和最大。 给定 N 个不同的可比较项，重新排列它们，使得每个内部项要么大于其前后两项，要么小于其前后两项。
    提示：对前半部分和后半部分进行排序和交错。
    
28. h 指数。 给定一个由 N 个正整数组成的数组，它的h 指数是最大的整数h，使得数组中至少有h个条目大于或等于h。设计一个算法来计算数组的h指数。
    提示：中位数或类似快速排序的分区和分治。
    
29. 软件版本号。 定义一个比较器，比较两个版本号（例如 1.2.32 和 1.2.5）的时间顺序。假设版本号是仅由十进制数字和.字符组成的字符串。.字符分隔字段；它不是小数点。
    
30. 稳定的选择排序。 你需要做什么修改才能使选择排序稳定？
    解决方案：首先，在找到最小剩余键时，始终选择最左边的条目；其次，不是用一次交换将最小键移动到最前面，而是将所有大于它的元素向右移动一个位置。
    
31. 最大数。 给定 n 个正整数，将它们连接起来，使它们形成最大的数。例如，如果数字是 123、12、96 和 921，则结果应该是 9692112312。
    解决方案。 定义一个比较器，通过将两个数字连接在一起（例如，对于 96 和 921，比较 96921 与 92196），看哪个字符串在字典顺序上最大。
    
32. 最大数。 给定三个长度为 n 的数组 A、B 和 C，确定有多少个三元组 a 在 A 中，b 在 B 中，c 在 C 中，使得 a < b < c？
    

3. 搜索

原文：algs4.cs.princeton.edu/30searching

译者：飞龙

协议：CC BY-NC-SA 4.0

概述。

现代计算和互联网使得大量信息变得可访问。高效搜索这些信息的能力对计算至关重要。本章描述了几十年来在众多应用中证明有效的经典搜索算法。我们使用术语符号表来描述一个抽象机制，我们可以保存信息（一个值），��后通过指定一个键进行搜索和检索。

• 3.1 基础符号表包括无序和有序的实现，使用数组或链表。
  
• 3.2 二叉查找树描述了二叉查找树。
  
• 3.3 平衡查找树描述了红黑树，这是一种保证每个符号表操作具有对数性能的数据结构。
  
• 3.4 哈希表描述了两种经典的哈希算法：分离链接和线性探测。
  
• 3.5 应用介绍了集合数据类型，并包括了符号表和集合的众多应用。
  

本章的 Java 程序。

以下是本章的 Java 程序列表。点击程序名称以访问 Java 代码；点击参考号以获取简要描述；阅读教材以获取详细讨论。

3.1 基本符号表

原文：algs4.cs.princeton.edu/31elementary

译者：飞龙

协议：CC BY-NC-SA 4.0

符号表。

符号表 的主要目的是将 值 与 键 关联起来。客户端可以将键值对插入符号表，并期望以后能够搜索与给定键关联的值。

API。

这是 API。我们考虑了几种设计选择，以使我们的实现代码一致、紧凑和有用。

• 泛型. 我们考虑在不指定正在处理的键和值类型的情况下使用泛型的方法。
  
• 重复键. 每个键只关联一个值（表中没有重复键）。当客户端将一个包含该键（和关联值）的键值对放入已经包含该键的表中时，新值将替换旧值。这些约定定义了关联数组抽象，您可以将符号表视为类似于数组的结构，其中键是索引，值是数组条目。
  
• 空值. 没有键可以与值 null 关联。这个约定直接与我们在 API 中规定的 get() 应该对不在表中的键返回 null 相关。这个约定有两个（预期的）后果：首先，我们可以通过测试 get() 是否返回 null 来测试符号表是否定义了与给定键关联的值。其次，我们可以使用调用 put() 时将 null 作为第二个（值）参数来实现删除。
  
• 删除. 符号表中的删除通常涉及两种策略之一：惰性删除，其中我们将表中的键与 null 关联，然后可能在以后的某个时间删除所有这些键，以及急切删除，其中我们立即从表中删除键。正如刚才讨论的，代码 put(key, null) 是 delete(key) 的一个简单（惰性）实现。当我们给出一个（急切）delete() 的实现时，它旨在替换此默认值。
  
• 迭代器. keys() 方法返回一个 Iterable 对象，供客户端用于遍历键。
  
• 键相等性.Java 要求所有对象实现一个equals()方法，并为标准类型（如Integer、Double和String）以及更复杂类型（如Date、File和URL）提供实现。对于涉及这些类型数据的应用程序，您可以直接使用内置实现。例如，如果x和y是String值，则x.equals(y)为true当且仅当x和y长度相同且在每个字符位置上都相同。在实践中，键可能更复杂，如 Person.java。对于这样的客户定义键，您需要重写equals()。Java 的约定是equals()必须实现一个等价关系:

• 自反性: x.equals(x) 为 true。
  
• 对称性: x.equals(y) 当且仅当 y.equals(x) 为 true 时，true。
  
• 传递性: 如果 x.equals(y) 和 y.equals(z) 为 true，那么 x.equals(z) 也是 true。
  

• 此外，equals() 必须以 Object 作为参数，并满足以下属性:
  

• 一致性: 多次调用 x.equals(y) 一致地返回相同的值，前提是没有修改任何对象
  
• 非空: x.equals(null) 返回 false。
  

• 最佳实践是使 Key 类型不可变，因为否则无法保证一致性。
  

有序符号表。

在典型应用中，键是Comparable对象，因此存在使用代码a.compareTo(b)来比较两个键a和b的选项。几个符号表实现利用Comparable暗示的键之间的顺序来提供put()和get()操作的高效实现。更重要的是，在这种实现中，我们可以将符号表视为按顺序保留键，并考虑一个定义了许多自然和有用的涉及相对键顺序的操作的显著扩展 API。对于键是Comparable的应用程序，我们实现以下 API：

• 最小值和最大值。对于一组有序键来说，可能最自然的查询是询问最小和最大的键。我们已经在第 3.4 节讨论优先队列时遇到了这些操作的需求。
  
• 下界和上界。给定一个键，通常有必要执行下界操作（找到小于或等于给定键的最大键）和上界操作（找到大于或等于给定键的最小键）。这个命名法来自于实数上定义的函数（实数 x 的下界是小于或等于 x 的最大整数，实数 x 的上界是大于或等于 x 的最小整数）。
  
• 排名和选择。确定新键在顺序中的位置的基本操作是排名操作（找到小于给定键的键数）和选择操作（找到具有给定排名的键）。我们已经在第 2.5 节讨论排序应用时遇到了这些操作的需求。
  
• 范围查询。有多少个键落在给定范围内？哪些键在给定范围内？回答这些问题的两个参数为size()和keys()方法在许多应用中非常有用，特别是在大型数据库中。
  
• 删除最小值和删除最大值。我们的有序符号表 API 添加了基本 API 方法来删除最大和最小键（及其关联的值）。
  
• 异常情况。当一个方法应该返回一个键，而表中没有符合描述的键时，我们的约定是抛出异常。
  
• 键相等性（重新审视）。在 Java 中的最佳实践是使compareTo()与所有Comparable类型中的equals()一致。也就是说，对于任何给定Comparable类型中的对象对a和b，应该满足(a.compareTo(b) == 0)和a.equals(b)具有相同的值。
  

示例客户端。

我们考虑两种客户端：一个测试客户端，用于跟踪算法在小输入上的行为，以及一个性能客户端。

• 测试客户端。我们符号表实现中的main()客户端从标准输入中读取一系列字符串，通过将值 i 与输入中的第 i 个键关联来构建符号表，然后打印表。
  
• 频率计数器。程序 FrequencyCounter.java 是一个符号表客户端，它在标准输入中找到每个字符串（至少具有给定阈值长度的字符）的出现次数，然后遍历键以找到出现最频繁的键。
  

无序链表中的顺序搜索。

程序 SequentialSearchST.java 实现了一个包含键和值的节点链表的符号表。要实现get()，我们通过列表扫描，使用equals()将搜索键与列表中每个节点中的键进行比较。如果找到匹配项，则返回相关值；如果没有，则返回null。要实现put()，我们也通过列表扫描，使用equals()将客户键与列表中每个节点中的键进行比较。如果找到匹配项，则将与该键关联的值更新为第二个参数中给定的值；如果没有，则创建一个具有给定键和值的新节点，并将其插入列表开头。这种方法称为顺序搜索。

命题 A.

在（无序）链表符号表中，不成功的搜索和插入都使用 N 次比较，在最坏情况下成功的搜索使用 N 次比较。特别是，将 N 个键插入到最初为空的链表符号表中使用 ~N²/2 次比较。

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