2018-11-2
2.4.33 # 解答 # 官方实现见：https://algs4.cs.princeton.edu/24pq/IndexMaxPQ.java.html
书中算法 2.6 给出的是一个最大堆的实现，但本题给出的部分解答却是最小堆的。
同时官网给出的解答是最大堆的，这里选择和官网保持一致，给出最大堆的实现。
初看起来可能会比较难理解，但其实就是以指针为元素的堆。
堆中存放的只是指向元素的指针（如果元素在数组里那就变成了下标）。
做比较的时候要先根据指针（下标）找到对应元素，再进行比较。
再来看题目中给出的要求，keys[] 数组中用于保存元素（比如 keys[0] = ‘A’;），
而 pq[] 中保存的是元素在 key[] 数组中的下标（比如 pq[1] = 0;)，
而 qp[] 中保存的是某个下标在 pq[]中 的对应位置。 （比如 qp[0] = 1）。
在这三个数组中，pq[]是一个堆，我们的堆操作都作用在这个数组上。
keys[] 数组中的元素不随着 pq[] 中下标的移动而移动，只有当删除或添加元素时才发生变化。
qp[]与pq[]中的索引一一对应，pq[]交换时也需要交换qp[]中的对应元素。
代码 # public class IndexMaxPq<TKey> : IEnumerable<int> where TKey : IComparable<TKey> { /// <summary> /// 优先队列中的元素。 /// </summary> private int _n; /// <summary> /// 索引最大堆。 /// </summary> private readonly int[] _pq; /// <summary> /// pq 的逆索引，pq[qp[i]]=qp[pq[i]]=i /// </summary> private readonly int[] _qp; /// <summary> /// 实际元素。 /// </summary> private readonly TKey[] _keys; /// <summary> /// 建立指定大小的面向索引的最大堆。 /// </summary> /// <param name="capacity">最大堆的容量。</param> public IndexMaxPq(int capacity) { if (capacity < 0) throw new ArgumentOutOfRangeException(); _n = 0; _keys = new TKey[capacity + 1]; _pq = new int[capacity + 1]; _qp = new int[capacity + 1]; for (var i = 0; i <= capacity; i++) _qp[i] = -1; } /// <summary> /// 将与索引 <paramref name="i"/> 相关联的元素换成 <paramref name="k"/>。 /// </summary> /// <param name="i">要修改关联元素的索引。</param> /// <param name="k">用于替换的新元素。</param> public void ChangeKey(int i, TKey k) { if (!
...
2018-12-27
2.4.34 # 解答 # 这里给出最大堆的实现，原因同 2.4.33。
maxIndex()：pq[1] 就是最小元素的下标。
change()：首先修改 keys 数组中对应的元素，然后对堆中该下标进行重排序。
delete()：先从堆中删除元素，再把 keys 和 qp 数组中的对应元素初始化。
代码 # /// <summary> /// 返回最大元素对应的索引。 /// </summary> /// <returns>最大元素对应的索引。</returns> /// <exception cref="ArgumentOutOfRangeException">当优先队列为空时抛出该异常。</exception> public int MaxIndex() { if (_n == 0) throw new InvalidOperationException("Priority Queue Underflow"); return _pq[1]; } /// <summary> /// 将与索引 <paramref name="i"/> 相关联的元素换成 <paramref name="k"/>。 /// </summary> /// <param name="i">要修改关联元素的索引。</param> /// <param name="k">用于替换的新元素。</param> public void ChangeKey(int i, TKey k) { if (!
...
2018-12-28
2.4.35 # 解答 # 本题有两个翻译错误。
random() ——返回索引 i 的概率是 p[i]/T，而非返回概率和索引。（return an index i with probability p[i]/T）
最后一句指的是像堆那样使用数组而非显式指针实现二叉树。（Avoid explicit pointers, as we do for heaps.）
提示已经给出了实现方案，我们用一个例子来简单说明一下。
现在给出一个分布 p，总和 T=1，如下图所示：
为了实现这样的随机分布，我们在 0~T 之间随机一个小数，然后根据结果返回不同的值。 现在我们将这个思想应用到完全二叉树上。
每次随机的过程其实构成了一棵选择树，我们把数组 p 当作一棵树，如下图：
为方便起见，我们重新排列一下之前的随机表：
每个值的概率并没有改变，只是每个值对应的区段换了一下。
经过这样的变换后，你会发现，如果从根结点的角度看：
如果随机的值小于 0.1，对应的编号就是 1。
如果随机的值大于 0.5，那么对应编号只能是 3 或 6，即根结点的右子树。
其他情况对应编号在左子树上。
扩展到一般情况，就变成了：
如果随机数小于当前结点，直接返回当前结点的编号。
如果随机数大于左子树权值总和+当前结点的权值，减去它们，移动到右子树。
其他情况减去当前结点的权值并移动到左子树。
思想理解之后，代码实现就比较容易了，做了 100000 次实验的结果如下：
代码 # internal class Sample { public double[] P; public double[] SumP; public double T; private readonly Random _random = new(); /// <summary> /// 构造一个离散取样类。 /// </summary> /// <param name="data">取样数据。</param> public Sample(double[] data) { // 复制权重 P = new double[data.
...
2018-12-28
2.4.36 # 解答 # 测试结果如下：
可以看出增长数量级约为 O(nlogn)。
代码 # var doubleTime = 5; var repeatTime = 5; var n = 100000; for (var i = 0; i < doubleTime; i++) { long totalTime = 0; Console.WriteLine("count=" + n); for (var j = 0; j < repeatTime; j++) { var pq = new MaxPq<int>(n); var time = Test(pq, n); Console.Write(time + "\t"); totalTime += time; } Console.WriteLine("平均用时：" + totalTime / repeatTime + "毫秒"); n *= 2; } long Test(MaxPq<int> pq, int count) { var random = new Random(); // 生成数据 var initData = new int[count]; var appendData = new int[count / 2]; for (var i = 0; i < count; i++) initData[i] = random.
...
2018-12-28
2.4.37 # 解答 # 建立一个全局变量 isRunning ，每次 DelMax() 之前都先确认这个值是否为 true，
设立一个 Timer 在 1 秒钟之后自动将 isRunning 置为 false。
测试结果如下：
随着 n 增大，一秒钟之内能执行的 DelMax() 次数会下降。
代码 # var doubleTime = 6; var repeatTime = 6; var n = 1000000; var isRunning = true; for (var i = 0; i < doubleTime; i++) { var totalDelCount = 0; Console.WriteLine("count=" + n); for (var j = 0; j < repeatTime; j++) { var pq = new MaxPq<int>(n); var delCount = Test(n, pq); totalDelCount += delCount; Console.
...
2018-12-28
2.4.38 # 解答 # 直接构造相应的数组测试即可。
测试结果如下：
最大堆来说顺序时会比较慢，因为每次插入都要一路上升到顶部。
逆序的时候则是删除比较慢，最后一个元素是最小的元素，交换后需要一路下沉到底部。
由于元素相同的时候我们选择不交换（less(i, j) 返回 false），较多的重复元素并不会影响性能。
代码 # var random = new Random(); var n = 200000; var repeatTimes = 5; var doubleTimes = 4; for (var i = 0; i < doubleTimes; i++) { Console.WriteLine("number=" + n); // 升序数组 long totalTime = 0; Console.Write("Ascending:\t"); for (var j = 0; j < repeatTimes; j++) { var pq = new MaxPq<int>(n); var data = GetAscending(n); var time = Test(pq, data); Console.
...
2018-12-29
2.4.39 # 解答 # 结果如下，约占总耗时的 2~5%。 代码 # var random = new Random(); Console.WriteLine("number\tBuild\tSort\tRatio"); var n = 1000; // 当数据量到达 10^9 时会需要 2G 左右的内存 var multiTen = 7; for (var i = 0; i < multiTen; i++) { var data = GetRandomArray(n); var fullSort = new Stopwatch(); var buildHeap = new Stopwatch(); fullSort.Restart(); buildHeap.Restart(); BuildHeap(data); buildHeap.Stop(); HeapSort(data); fullSort.Stop(); var buildTime = buildHeap.ElapsedMilliseconds; var fullTime = fullSort.ElapsedMilliseconds; Console.WriteLine(n + "\t" + buildTime + "\t" + fullTime + "\t" + (double)buildTime / fullTime); n *= 10; } short[] GetRandomArray(int number) { var data = new short[number]; for (var i = 0; i < number; i++) { data[i] = (short)random.
...
2018-12-29
2.4.40 # 解答 # 如同书上所说，可以节省约 50% 的比较次数。 先沉后浮的实现也很简单，将 swim 方法加入，
然后修改 sink 方法，去掉其中检查是否需要下沉的条件（if(!Less(pq, k, j))），
然后在 sink 方法的循环之后调用 swim。
为了获得比较次数，你可以添加一个静态全局变量 compareCount，
然后修改 Less 方法，在作比较的同时使 compareCount++ ，
每次执行 Sort 时先让 compareCount 置零，最后返回 compareCount。
代码 # public static class HeapFloyd { /// <summary> /// 利用堆排序对数组进行排序。 /// </summary> /// <param name="pq">需要排序的数组。</param> public static void Sort<T>(T[] pq) where T : IComparable<T> { var n = pq.Length; // 建堆 for (var k = n / 2; k >= 1; k--) { Sink(pq, k, n); } // 排序 while (n > 1) { Exch(pq, 1, n--); SinkThenSwim(pq, 1, n); } } /// <summary> /// 令堆中的元素下沉。 /// </summary> /// <param name="pq">需要执行操作的堆。</param> /// <param name="k">需要执行下沉的结点下标。</param> /// <param name="n">堆中元素的数目。</param> private static void Sink<T>(T[] pq, int k, int n) where T : IComparable<T> { while (2 * k <= n) { var j = 2 * k; if (j < n && Less(pq, j, j + 1)) j++; if (!
...
2018-12-29
2.4.41 # 解答 # 多叉堆和二叉堆的实现上并没有很大的区别，
只不过下沉（Sink）时需要比较的子结点数量变多了，上浮时父结点的下标不再是 $\lfloor k /2 \rfloor$。
于是只要能推出 $d$ 叉堆的下标换算公式即可解决整个问题。
先考虑 $d$ 叉堆的在数组中的保存方式，
第一层显然只有根结点，第二层显然有 $d$ 个结点，第三层则有 $d \times d=d^2$ 个结点，如下图所示：
不难推出第 $k$ 层有 $d^{k-1}$ 个结点。
接下来我们对其标号，根结点为 1，以此类推，如下图：
现在我们来推导某个结点的子结点的下标公式。
结点 $i$ 的第一个子结点在哪里呢？
首先要加上本层剩下的结点，再加上它前面结点的所有子结点，再下一个就是它的第一个子结点了。
以 2 号结点为例，它是第二层的第一个结点，第二层共有 $d^{2-1}=d$ 个结点，剩下 $d-1$ 个结点。
2 号结点前面没有更多兄弟结点，于是第一个子结点下标即为 $2 + d - 1 + 1= 2 + d$。
3 号结点之后剩余 $d-2$ 个结点，加上前面 2 号结点的 $d$ 个子结点，
它的第一个子结点下标为 $3+d-2+d+1= 2+2d$。
不难发现规律，结点序号加一，子结点的下标就要对应加上 $d$（要加上前一个结点的子结点），
这个规律也可以从图上（$d=3$）看出来：
1号结点的子结点范围是 $[2,d+1]$，每加一个结点子结点就要加上 $d$ 。
...
2018-12-31
2.4.42 # 解答 # 前序序列与完全二叉树 # 二叉树前序遍历的顺序是：自身，左子树，右子树。
因此对于一个前序遍历序列，第一个元素是根结点，第二个元素是左子结点。
再把左子结点找到，就可以把数组分成三部分：根结点，左子树，右子树，进而递归的构造出整个二叉树。
现在问题是，右子结点在哪，或者说，左子树有多大？
这里就要用到完全二叉树的性质了，我们先从比较简单的满二叉树入手。
就满二叉树而言，根结点的左子树和右子树是一样大的，即左右子树大小均为 $(n-1)/2$ 。
在这种情形下，右子结点的下标显然是 $(n+1)/2$ ，根结点下标为 0。 完全二叉树可以视为在满二叉树的基础上加了一层叶子结点，现在我们已知结点总数 $n$。
于是可以求得二叉树的高度 $k=\lfloor \log_2(n) \rfloor$ ，注意只有一个结点的树高度为 0。
那么最后一层的叶子结点数目为 $l=n-2^{k}+1$ 个，如下图所示：
如果把最后一层（第 $k$ 层）去掉，剩余部分即为高度为 $k-1$ 的满二叉树，结点总数为 $2^k - 1$ 。
按照之前的说明可以知道左右子树大小都等于 $(2^{k}-2)/2=2^{k-1}-1$。
现在要将第 $k$ 层的 $l$ 个结点分到左右子树里面去。
第 $k$ 层最多能有 $2^k$ 个结点，取半就是 $2^k / 2 = 2^{k-1}$ 个。
于是当 $l<=2^{k-1}$ 时，左右子树大小分别为 $2^{k-1}-1+l$ 和 $2^{k-1}-1$ 。
当 $l > 2^{k-1}$ 时，左右子树大小分别为 $2^{k} - 1$ 和 $2^{k-1} -1 +l -2^{k-1}=l-1$ 。
...