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 $
参考：
随笔 已经有两个多月没有更新过博客了。
有几个原因吧。一直没有找到顺手的工具。
现在使用的工具有：
Hugo+Sublime
支持的功能主要包括：markdown格式的文档，公式支持latex，图库使用gitee。
目前正在想办法自己写一个图片预览工具，本地图片生成预览，选中图片时自动复制图库连接。
[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的使用）
算法4习题 2.1.12 问题 Instrument shellsort to print the number of compares divided by the array size for each increment. Write a test client that tests the hypothesis that this number is a small constant, by sorting arrays of random Double values, using array sizes that are increasing powers of 10, starting at 100.
打印希尔排序中每个增量带来的比较次数和数组大小的比值。 验证该值是一个小常数。
思路 统计每个增量对应的比较次数。
private static boolean less(Comparable v, Comparable w) { count ++ ; return v.compareTo(w) < 0; } 解答 Extensive experiments suggest that the average number of compares per increment might be N^(1/5) 大量实验表明每个增量的比较次数约为N的1/5次方。