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的使用）
算法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次方。
1.1.1 7, 200.0000002, true
1.1.2 a. double 1.618 b. double 10.0 c. boolean true d. String “33”
执行Java 采用输入命令的形式：
目录：
E:\GDUT\Dropbox\Alg4\algs4\target\classes
执行：
java edu.princeton.cs.myalg.u1.Ex_1_1_3 1 1 2
$ab=bc$ $$ab=cd$$ [ x = {-b \pm \sqrt{b^2-4ac} \over 2a} \]