2018-9-18
2.4.23 # 解答 # 简单的 sink 实现 # sink 方法会在所有的 $t$ 个子结点中寻找最大的结点。 如果找到的结点比当前结点大，那么就进行交换。
否则视为结点已经下沉到了合适的位置，结束循环。
根据题意，在 $t$ 个元素中找最大值需要 $t$ 次比较。
sink 操作需要找到 $t$ 个子结点中的最大值并与当前结点相比较。
于是 sink 操作每次最多需要 $t + 1$ 次比较。
建堆过程，对 2.4.20 的证明进行推广。
设 $t$ 叉树的高度为 $h$ ，叶子结点的高度为 $0$，根结点的高度为 $h$。
根据 sink 操作的定义，高度为 $k$ 的结点最多进行 $k$ 次交换（到达叶子结点）。
于是建堆需要的总交换次数为：
$$ \begin{align*} & h+t(h-1)+t^2(h-2)+ \dots + t^h(0) \newline & =\sum_{k=0}^{h-1} t^k(h-k) \newline & =h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \newline \end {align*} $$
其中，第一个数列是等比数列，第二个数列是等差数列和等比数列之积，可以利用错位相减法求得，即：
...
2018-10-5
2.4.24 # 解答 # 链式实现，每个结点都包含一个指向父结点的指针和两个指向子结点的指针。
交换结点可以直接用交换两个结点的值来实现（与数组的实现一样），而不是对两个结点的指针进行交换。
于是 Sink() 和 Swim() 操作就比较简单，直接按照定义实现即可。
比较困难的是删除和插入结点，或者更具体的说，
如何找到按照完全二叉树定义下序号向后/向前一位的结点？
我们首先在堆里面维护两个指针，一个指向根结点（root），另一个指向当前最后一个结点（last）。
当需要插入新结点时，我们需要找到 last 的后一位的父结点，然后把新的结点插入为该结点的左子结点。
这段话可能比较绕，下面这个示意图可以帮助理解，有三种情况：
标黄的代表 last 指着的位置。
我们先从简单的说起，中间的第二种情况，新插入的结点应该放在右侧，即作为 last 的父结点的右子结点。
如果 last 已经是右子结点了，那么就考虑第三种情况。
此时应该向上回溯，直到在某一次回溯中，结点是从父结点的左侧回溯上来的 （即图中路径 A-B-B，B-B 这一步是从左子树回溯上来的）。
于是待插入的位置就在该父结点的右子树的最左侧结点（即图中根结点的右子结点 A）。
最后是图中第一种情况，整棵树已经是满二叉树了。
这种情况下会一路回溯到根结点，那么只要一路下沉到最左侧的叶子结点，把新结点插入到其左子树上即可。
删除结点同理，也是这三种情况，只是需要找前一个结点，判断条件中的左右正好相反。
如果已经是右子结点了，只需要把 last 改为其父结点的左子树即可。
如果是左子结点，就需要回溯，直到某一次回溯是从右子树回溯上来的，last 应该指向其左子树的最右侧结点。
如果删除后正好变成满二叉树，那么会一直回溯到根结点，last 应该指向整棵树的最右侧结点。
代码实现中还需要处理只有一个结点以及没有结点时的特殊情况。
根据上面的算法，插入/删除找到相应位置所需的最大耗时为 2lgN （从树的一侧回溯到根结点，再下沉到另一侧的底部）。
Sink 和 Swim 是 O(lgN) 级的，因此整个插入/删除操作是 O(lgN) 的。
代码 # public class MaxPqLinked<TKey> : IMaxPq<TKey> where TKey : IComparable<TKey> { /// <summary> /// 二叉堆的根结点。 /// </summary> private TreeNode<TKey> _root; /// <summary> /// 二叉堆的最后一个结点。 /// </summary> private TreeNode<TKey> _last; /// <summary> /// 二叉堆中的结点个数。 /// </summary> private int _nodesCount; /// <summary> /// 删除并返回最大值。 /// </summary> /// <returns>最大值。</returns> /// <remarks>如果希望获得最大值而不删除它，请使用 <see cref="Max"/>。</remarks> public TKey DelMax() { var result = _root.
...
2018-10-7
2.4.25 # 解答 # 官方实现：https://algs4.cs.princeton.edu/24pq/CubeSum.java.html
注意这道题并不是要打印所有的 $a^3+b^3$ 的结果，而是需要找到 $a^3+b^3=c^3+d^3$ 这个丢番图方程的解。
因此在官方实现的基础上，每次取出最小值之后和之前的最小值比较，如果相等则输出对应的组合。
关键代码如下：
CubeSum prev = new CubeSum(-1, -1); long pairCount = 0; while (!pq.IsEmpty()) { CubeSum s = pq.DelMin(); if (s.sum == prev.sum) // 如果与之前的数相等 { Console.WriteLine(s + " = " + prev.i + "^3 + " + prev.j + "^3"); pairCount++; } if (s.j < n) pq.Insert(new CubeSum(s.i, s.j + 1)); prev = s; } 当然，对于 n=10^6 来说结果会非常大，程序的运行时间需要以天为单位计算（约 14 天）。
...
2018-10-15
2.4.26 # 解答 # 用类似于「半交换」的方法避免频繁调用 Exch() 方法。
上浮时，先单独保存待上浮的元素，随后进行比较，
如果当前 k 值对应的父结点（即 k/2 ）小于待上浮的元素，令 pq[k]=pq[k/2]。
否则令当前 k 值等于待上浮的元素，终止循环。 下沉的过程类似。
修改后的 sink 和 swim 方法：
/// <summary> /// 使元素上浮。 /// </summary> /// <param name="k">需要上浮的元素。</param> private void Swim(int k) { var key = _pq[k]; while (k > 1 && _pq[k / 2].CompareTo(key) < 0) { _pq[k] = _pq[k / 2]; k /= 2; } _pq[k] = key; } /// <summary> /// 使元素下沉。 /// </summary> /// <param name="k">需要下沉的元素。</param> private void Sink(int k) { var key = _pq[k]; while (k * 2 <= _n) { var j = 2 * k; if (Less(j, j + 1)) j++; if (_pq[j].
...
2018-10-20
2.4.27 # 解答 # 官网有解答，只要在 MaxPQ 里面加上一个记录最小值的指针就可以了。
初始状态下这个指针为空。
每次插入新元素的时候先更新一下这个指针。 删除最后一个元素的时候把它重新置空即可。
具体实现见代码。
代码 # public class MaxPqWithMin<TKey> : IMaxPq<TKey>, IEnumerable<TKey> where TKey : class, IComparable<TKey> { /// <summary> /// 保存元素的数组。 /// </summary> /// <value>保存元素的数组。</value> private TKey[] _pq; /// <summary> /// 堆中的元素数量。 /// </summary> /// <value>堆中的元素数量。</value> private int _n; /// <summary> /// 堆中的最小元素。 /// </summary> /// <value>堆中的最小元素。</value> private TKey _min; /// <summary> /// 默认构造函数。 /// </summary> public MaxPqWithMin() : this(1) { } /// <summary> /// 建立指定容量的最大堆。 /// </summary> /// <param name="capacity">最大堆的容量。</param> public MaxPqWithMin(int capacity) { _pq = new TKey[capacity + 1]; _n = 0; _min = null; } /// <summary> /// 从已有元素建立一个最大堆。（O(n)） /// </summary> /// <param name="keys">已有元素。</param> public MaxPqWithMin(TKey[] keys) { _n = keys.
...
2018-10-22
2.4.28 # 解答 # 开始时让 N=10^5，在 M=10^4 不变的情况下令 N 不断翻倍，求出算法增长的数量级。
再根据求出的增长的数量级估计 N=10^8 时所需要的时间。
为了方便比较，需要编写一个欧几里得距离类，
构造时输入一个点的坐标，内部自动计算并保存这个点到原点的欧几里得距离。
欧几里得距离的计算公式如下：
$$ d(x,y)=\sqrt{\sum_{i=1}^{n}(x_i-y_i)^2} $$
其中，x 和 y 分别代表两个点。
在本题中，y 始终是原点，且使用三维坐标系，因此公式可以简化为：
$$ d=\sqrt {x^2+y^2+z^2} $$
同时这个类需要实现 IComparable 接口以作为最小堆的元素。
做测试时，先随机生成 N 个点，再建立一个最小堆。
随后开始计时，把开始的 m 个点插入。
剩余的 n-m 个点则是先删除最小值再插入，这样可以保证最小堆的大小不变。
最后再把堆中的所有元素输出，停止计时。
用不断倍增的的 N 值做上述测试，获得每次的耗时，进而求得算法增长的数量级。
求得的结果如下：
可以推出当 N=10^8 时耗时为 $ 398 \ ms × 1000 = 398 \ s $
代码 # 欧几里得距离类，EuclideanDistance3D
internal class EuclideanDistance3D : IComparable<EuclideanDistance3D> { private readonly int _x, _y, _z; private readonly double _distance; /// <summary> /// 计算点到原点的欧几里得距离。 /// </summary> /// <param name="x">x 轴坐标。</param> /// <param name="y">y 轴坐标。</param> /// <param name="z">z 轴坐标。</param> public EuclideanDistance3D(int x, int y, int z) { _x = x; _y = y; _z = z; _distance = Math.
...
2018-10-27
2.4.29 # 解答 # 算法思想比较简单，但在实现上会有一些复杂。
用一个最大堆和一个最小堆，每个堆中都保存了全部数组元素，且相同的元素之间有指针相连。
插入元素时需要构建两个完全相同的元素分别插入到两个堆中。
找到最小元素和找到最大元素只需要分别返回最大堆和最小堆的堆顶元素即可。
以删除最小元素为例，先对最小堆进行 DelMin() 操作，再通过指针找到对应最大堆的元素并删除。
下面介绍删除堆中任意元素的算法。
首先将待删除元素与堆中最后一个元素交换，让堆的大小减一。
随后对交换后的元素先进行 Swim 再进行 Sink，移动到正确的位置上。
下图是一个例子，当删除最大元素 14 时，最小堆中删除元素 14 需要先 Swim。
如果堆的层数更多一些，就需要先 Swim 再 Sink。
现在来考虑一下实现，我们构建一个结点类，里面存放有当前结点的值、对应数组下标和另一个结点的指针。
private sealed class MinMaxNode : IComparable<MinMaxNode> { /// <summary> /// 结点的值。 /// </summary> /// <value>结点的值。</value> public TKey Key { get; set; } /// <summary> /// 结点在当前数组中的下标。 /// </summary> /// <value>结点在当前数组中的下标。</value> public readonly int Index; /// <summary> /// 指向孪生结点的引用。 /// </summary> /// <value>指向孪生结点的引用。</value> public MinMaxNode Pair { get; set; } /// <summary> /// 这个类不能在外部实例化。 /// </summary> private MinMaxNode(TKey key, int index) { Key = key; Index = index; } /// <summary> /// 工厂方法，建立两个孪生的结点。 /// </summary> /// <param name="key">结点中的元素。</param> /// <param name="index">索引。</param> /// <param name="minNode">准备放到最小堆中的结点。</param> /// <param name="maxNode">准备放到最大堆中的结点。</param> public static void GetNodes(TKey key, int index, out MinMaxNode minNode, out MinMaxNode maxNode) { minNode = new MinMaxNode(key, index); maxNode = new MinMaxNode(key, index); minNode.
...
2018-10-28
2.4.30 # 解答 # 单独用一个变量存放中位数，然后前半部分元素放在一个最大堆中，后半部分元素放在一个最小堆中。
如下图所示，注意 Median 和两个堆并没有直接连接，这里只是方便理解元素顺序。
只要左右两个堆含有元素之差不超过 1，那么 Median 变量中存放的就是整个数组的中位数。
如果元素差大于 1，就需要进行调整，
把 Median 变量中存放的值插入到元素较少的堆，
再从元素较多的堆中取出元素放入 Median 变量，直到元素差不大于 1。
插入元素时，根据插入元素的大小插入到某一个堆中去，再做一次调整。
删除中位数时，去掉中位数，然后从元素较多的一侧堆中取元素补位，再进行一次调整。
编写代码时要注意堆中只有一个元素的情况需要特殊处理。
代码 # 面向中位数的堆（MedianPQ.cs）
public class MedianPq<TKey> where TKey : IComparable<TKey> { /// <summary> /// 最大堆（保存前半段元素）。 /// </summary> /// <value>最大堆（保存前半段元素）。</value> private readonly MaxPq<TKey> _maxPq; /// <summary> /// 最小堆（保存后半段元素）。 /// </summary> /// <value>最小堆（保存后半段元素）。</value> private readonly MinPq<TKey> _minPq; /// <summary> /// 中位数。 /// </summary> /// <value>中位数。</value> private TKey _median; /// <summary> /// 堆的大小。 /// </summary> /// <value>堆的大小。</value> private int _n; /// <summary> /// 默认构造函数，构造一个面向中位数的堆。 /// </summary> public MedianPq() { _maxPq = new MaxPq<TKey>(); _minPq = new MinPq<TKey>(); _median = default; _n = 0; } /// <summary> /// 构造一个指定容量的面向中位数的堆。 /// </summary> /// <param name="capacity">初始容量。</param> public MedianPq(int capacity) { _maxPq = new MaxPq<TKey>((capacity - 1) / 2); _minPq = new MinPq<TKey>((capacity - 1) / 2); _n = 0; _median = default; } /// <summary> /// 根据指定数组初始化面向中位数的堆。 /// </summary> /// <param name="keys">初始数组。</param> public MedianPq(TKey[] keys) { _minPq = new MinPq<TKey>(); _maxPq = new MaxPq<TKey>(); if (keys.
...
2018-11-2
2.4.31 # 解答 # 首先可以观察到堆有这样一个性质，从根结点到某一个叶子结点的路径是有序的，满足二分查找的条件。
但是， 从叶子结点到根结点的路径可以通过不断地令 k = k / 2 得到（从下往上只有一条路径）。
但从根结点到叶子结点的路径却不能简单地通过 k = k * 2 得到（从上往下会有两条分支）。
因此只通过堆本身是无法满足二分查找对于随机访问的要求的。
为了达到 ~loglogN 次比较，我们需要对 Swim() 方法做修改，
即，先通过一个数组来保存路径，再对这个数组进行二分查找，从而获得合适的祖先结点。
路径的长度是 ~logN（完全二叉树的性质），于是二分查找的比较次数即为 ~loglogN。
删除操作原本就是 ~2logN 的，不需要修改。
注意这样的方法仅仅只是减少了比较次数，
为了保持堆的有序，即使找到了结点的合适位置也不能直接插入，
仍然需要将路径上的结点依次下移，空出位置后再插入结点，复杂度仍然是 ~logN。
由于增加了保存路径等操作（建立了大量的小数组），实际算法的运行时间是增加的。
也可以用空间换时间，由于在堆中下标为 k 的结点到根结点的路径是唯一确定的。
因此可以提前计算好路径，用一个数组保存起来（数组的数组），在 Swim 中取出对应路径进行二分查找。
当然这样是很不划算的，除非元素比较的开销非常大。
代码 # 修改后的 Swim() 方法，注意输入的路径是从下往上的。
private void Swim(int k) { if (k == 1) return; // 获取路径 var path = new List<int>(); var temp = k; while (temp >= 1) { path.
...
2018-11-2
2.4.32 # 解答 # 官网解答见：https://algs4.cs.princeton.edu/24pq/
如果这样的话，堆排序的只需要 ~nloglogn 次比较即可。
根据 2.3 中的证明，基于比较的排序的下界是 ~nlogn。
因此不存在这样的最小堆。
注意上题的方法不能用于下沉操作，因为我们不能预知下沉的路径。