5.1.2 问题： 给出使用地位优先的字符串排序算法处理下面这些键的轨迹
no is th ti fo al go pe to co to th ai of th pa
Give a trace for LSD string sort for the keys:
no is th ti fo al go pe to co to th ai of th pa
分析： LSD 适用于字符等长的数组排序。
从右往左，依次数组中每个元素对位置d的字符使用key-indexed counting排序。
平均数组访问次数7WN+3WR。额外空间N+R。 N 对应aux数组，R对应count数组。 对于一般的应用LSD线性时间复杂度。
public static void sort(String[] a, int w) { int N = a.length; int R = 256; String[] aux = new String[N]; for (int d = w - 1; d >= 0; d--) { // sort by key-indexed counting on dth char show(a); int[] count = new int[R + 1]; for (int i = 0; i < N; i++) { count[a[i].
2.4.24 问题： Priority queue with explicit links. Implement a priority queue using a heap- ordered binary tree, but use a triply linked structure instead of an array. You will need three links per node: two to traverse down the tree and one to traverse up the tree. Your implementation should guarantee logarithmic running time per operation, even if no maximum priority-queue size is known ahead of time.
使用链表的优先队列。使用二叉树实现一个优先队列。每个结点都需要三个链接：两个向下，一个向上。你的实现需要保证在无法预知队列大小的情况下也能保证优先队列的基本操作所需要的时间为对数级别。
分析： 插入\删除 ：
2.4.2 问题： 2.4.22 Array resizing. Add array resizing to MaxPQ, and prove bounds like those of Proposition Q for array accesses, in an amortized sense.
调整数组的大小。在MaxPQ中加入调整数组大小的代码，并和命题Q一样证明对于一般性长度为N的队列数组访问的上限。
分析： 在MaxHeap类中新增方法 resize(int max)，当堆的中元素个数等于key数组容量满的时候，key数组增大两倍，当堆的元素个数等于key数组长度的1/4时，key数组长度变为原来的1/2.
public _MaxMQ(){ this(1); } private void resize(int max){ assert max > N; Comparable[] temp = new Comparable[max]; for(int i=1; i<=N; i++){ temp[i] = pq[i]; } pq = (Key[]) temp; } public Key delMax(){ Key max = pq[1]; pq[1] = pq[N--]; // 使用 pq[N] 作为哨兵 sink(1); pq[N + 1] = null; if(N==(pq.
2.4.21 问题： 2.4.21 Elementary data structures. Explain how to use a priority queue to implement the stack, queue, and randomized queue data types from Chapter 1
分析： 题目要求使一个优先队列。
假设使用MaxPQ优先队列的操作有 insert delMax isEmpty size
Stack：
那么对于Stack LIFO 的实现我们需要指定被后插入的元素的priority比之前插入的元素priority大。
Queue:
对于Queue FIFO 的实现，需要后插入元素的priority小于之前插入元素的priority。
randomized queue：
随机队列需要指定一个随机的priority，其余实现和处理Queue的方法一样。
问题是怎么样生成一个不重复的随机数呢？我的思路是使用一个Set保存随机数。
public int random() { int num = 0; while (!numSet.contains(num)) { num = StdRandom.uniform(1, Integer.MAX_VALUE); numSet.add(num); break; } return num; } 另外要提到的是对于使用MaxPQ实现的Stack和Queue，插入删除元素的时间复杂度都是lgN。
class IKey implements Comparable<IKey>{ Key value; int priority; @Override public int compareTo(IKey another) { return compare(this.
2.4.20 问题： Prove that sink-based heap construction uses fewer than 2N compares and fewer than N exchanges.
证明基于下沉方法建立堆使用少于2N次的比较和N次交换。
分析： 官方网站解答：https://algs4.cs.princeton.edu/24pq/
假设为堆是完美的。
我们将树中节点的高度定义为以该节点为根的子树的高度。
一个高度为k的节点，下沉最多交换k次，对于每一层，有：
$$ \begin{eqnarray} h + 2(h-1) + 4(h-2) + 8(h-3) + \ldots + 2^h (0) & = & 2^{h+1} - h - 2 \
& = & n - (h+1) \
& \le & n \end{eqnarray} $$
第一项使用等比数列求和公式，第二项错位相减法。
参考： 沈星繁
2.4.19 问题： 2.4.19 Implement the constructor for MaxPQ that takes an array of items as argument, using the bottom-up heap construction method described on page 323 in the text.
实现一个MaxPQ的构造函数，接受一个数组做为参数，使用323页中描述的自底向上的方法构建堆。
分析： 将数组做为参数构建堆，可以选择从左到右扫描，使用swim()方法。 但更明智的方法是使用从右往左扫描的方式，sink()。 这个方法的想法是如果一个结点的两个子结点的树都是堆的话，sink(k)之后，两个子树就合并成了以k为根结点的子树
public MaxPQ(Key[] a){ N = a.length; pq = (Key[]) new Comparable[N+1]; for(int i=0; i<a.length; i++){ pq[i+1] = a[i]; } int k = N / 2; while (k >= 1){ sink(k); k --; } assert isMaxHeap(); show(); } 参考： 课本官网的实现MaxPQ
2.4.18 问题： 2.4.18 In MaxPQ, suppose that a client calls insert() with an item that is larger than all items in the queue, and then immediately calls delMax(). Assume that there are no duplicate keys. Is the resulting heap identical to the heap as it was before these op- erations? Answer the same question for two insert() operations (the first with a key larger than all keys in the queue and the second for a key larger than that one) followed by two delMax() operations.
2.4.17 问题： 2.4.17 Prove that building a minimum-oriented priority queue of size k then doing N - k replace the minimum (insert followed by remove the minimum) operations leaves the k largest of the N items in the priority queue.
分析： 题意是insert followed by remove the minimum，先插入后删除。
例如
N=10, 元素为：0,2,4,6,8,1,3,5,7,9 k=3， qp = 0 2 4 N-k = 10 - 3 = 7，将要进行7次操作 pq = 0 2 4 count = 1 insert 6, pq = 0 2 4 6 remove 0, pq = 2 4 6 count = 2 insert 8, pq = 2 4 6 8 remove 2, pq = 4 6 8 count =3 insert 1, pq = 1 4 6 8 remove 1, pq = 4 6 8 .
2.4.10 问题： 2.4.10 Suppose that we wish to avoid wasting one position in a heap-ordered array pq[], putting the largest value in pq[0], its children in pq[1] and pq[2], and so forth, proceeding in level order. Where are the parents and children of pq[k]?
分析： 略
答案： 子节点：$ 2k+1, 2k+2 $，父节点： $ \lfloor \frac{k-1}{2} \rfloor $
参考：
[TOC]
里程碑 今天是一个里程碑，断断续续一年多，自己搭建的博客遇到的各种问题基本得到解决。
现在整理一下解决问题的思路：
博客用到的东西：Github(托管静态网页)、Hugo、Sublime、Markdown、MathJax、免费图床(gitee)、留言(需要翻墙)
遇到的问题主要有： 图床问题： 使用免费图床是个大问题：目前的解决方案是将图片上床到gitee上，这样国内访问图片速度较快。
图片链接插入问题： 之前我写了自动生成链接的脚本，但是结果输出到了文本文件中，对于图片预览实时性的要求就无法满足。
平台不通用问题： 通用性的问题一直没有解决：对于Latex公式的支持，图床的支持
以前由于各个平台不通用的问题，导致我们一直只能在一个平台上写作。而各大平台又各有优缺点，总有令人不满意的地方。
这样下来在本地写的Markdown，不需要做修改可以支持CSDN博客（或者简书）了，直接复制过去就可以。
在未来不久印象笔记windows版本也会支持Markdown，真是个令人振奋的消息。
甚至我还使用过马克飞象，但是它只能配合印象笔记使用，对于跨平台的需求无法满足。
我的github 页面托管到了github上，有兴趣的话可以试着自己搭建一个静态博客。
https://gdhucoder.github.io/
图片本地预览、链接 大家都知道Markdown使用图片需要插入图片链接。
我们使用python写了个脚本，生成文件的缩略图，自动上传gitee，点击图片缩略图，获取链接到剪切板。
接下来我又添加的每次打开Helper时，自动提交git，得到最新的图片
然后点击图片缩略图，图片的git地址（可供外网访问的地址）就被拷贝到了剪切板中，在使用的时候我们直接Ctrl+V就可以复制地址到Markdown文档中。
这个脚本还支持子目录的打开预览。
因为如果我们只用一个文件夹管理所有的博客图片势必会没有层级结构，导致最后图片混乱。
我们可以建立子文件夹，存放各个主题的图片文件。
Picture Helper使用方法： upload your pictures to github or gitee this script can generate latest 100 picture links click the thumb picture, then the link is clipped into you clipboard then use Ctrl+V in your own Markdown Enjoy! 另附代码 主要参考了PP4E的pyphoto的代码。
各位改改可以用到的地方： 1、自动提交git脚本 2、生成缩略图（PIL的使用）