优先队列 当一颗二叉树的每个节点都大于等于它的两个子结点时, 它被称为堆有序, 于是从任一结点向上都能够得到一列非递减的元素. 二叉堆(以下简称堆)是一组能够用堆有序 的完全二叉树排序的元素, 并在数组中按照层级存储. 在一个堆中, 位置k的节点的父结点的位置为$ \lfloor k/2 \rfloor $, 而它的两个子节点的位置是2k和 2k+1. 对于一个含有N个元素的堆, 插入元素操作只需不超过lgN+1次比较, 删除最大元素的操作不超过2lgN次比较. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 public class MaxPQ<Key extends Comparable<Key>> { private Key[] pq; private int N = 0; @SuppressWarnings("unchecked") private Key[] cast(Object obj) { return (Key[]) obj; } private boolean less(int i, int j) { return pq[i].compareTo(pq[j]) < 0; } private void exch(int i, int j) { Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; } private void swim(int k) { while (k > 1 && less(k / 2, k)) { exch(k, k / 2); k = k / 2; } } private void sink(int k) { while (2 * k <= N) { int j = 2 * k; if (j < N && less(j, j + 1)) j++; if (!less(k, j)) break; exch(k, j); k = j; } } private void resize(int newSize) { Key[] t = cast(new Comparable[newSize]); System.arraycopy(pq, 1, t, 1, N); pq = t; } public MaxPQ() { pq = cast(new Comparable[1]); } public MaxPQ(int max) { pq = cast(new Comparable[max + 1]); } public MaxPQ(Key[] a) { } public void insert(Key v) { if (N >= pq.length - 1) resize(pq.length * 2); pq[++N] = v; swim(N); } public Key max() { return pq[1]; } public Key delMax() { if (N < (pq.length - 1) / 2) resize(pq.length / 2); Key max = pq[1]; exch(1, N); pq[N--] = null; sink(1); return max; } public boolean isEmpty() { return N == 0; } public int size() { return N; } } 索引优先队列 索引优先队列可以看成一个能够快速访问其中最小元素的数组, 事实上, 它能够快速访问数组的一个特定子集中的最小元素. ...

排序算法的目标就是将所有元素的主键按照某种方式排列. 成本模型: 计算比较和交换的次数, 对于不交换元素的算法, 计算访问数组的次数. 排序算法的额外内存开销 和运行时间是同等重要的, 排序算法可以分为原地排序算法以及需要额外内存空间来存储另一份数组副本的其他排序算法. 我们使用的算法模板如下 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 public interface Sort { static void sort(Comparable[] a) { } static boolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; } static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } static void show(Comparable[] a) { for (Comparable x : a) { StdOut.print(x + " "); StdOut.println(); } } static boolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i - 1])) return false; } return true; } static void main(String[] args) { String[] a = StdIn.readAllStrings(); sort(a); assert isSorted(a); show(a); } } 选择排序 最简单的算法是选择排序, 不断寻找数组剩下元素的最小值, 并将其放在适当的位置. 其特点在于: ...

union-find算法是一个解决动态连通性的经典算法, 具有广泛性的应用. 简单起见, 我们将对象称为触点, 将整数对称为连接, 将等价类称为连通分量, 并用0 到N-1的整数来表示N个触点. API 1 2 3 4 5 6 7 public class UF { UF(int N) // 以整数标识初始化N个触点 void union(int p, int q) // 在p和q之间添加一条连接 int find(int p) //p所在分量的标识符 boolean connected(int p, int q) // p和q之间是否存在于同一个分量中 int count() // 连通分量的数量 } 成本模型: 以数组的访问次数作为成本模型, 无论读写. 算法的关键在于find和union的设计上. quick-find算法 1 2 3 4 5 6 7 8 9 10 11 12 //quick-find算法 public int find(int p) { return id[p]; } public void union(int p, int q) { int pID = find(p), qID = find(q); // 两次读操作 if (pID != qID) { // N次读操作, 1~(N-1)次写操作 for (int i = 0; i < id.length; i++) if (id[i] == pID) id[i] = qID; count--; } } quick-find使用一个触点为索引的数组作为数据结构, 每次find()调用访问数组一次, 而union()调用访问数组(N+3)到(2N+1)次. 假设我们最后只得到 了一个连通分量, 那么至少需要调用N-1次union(), 即至少$ (N+3)(N-1) \sim N^2 $次数组访问. 意味着该算法是平方级别的, 也意味着该算法不试用于 规模更大(百万级)的场景. ...

本地操作 状态检览 1 2 $ git status -s XY PATH1 -> PATH2 PATH2只有在PATH1关联到不同的路径时才会显示(例如, 文件重命名). XY是两个状态码, 在合并冲突的时候, X和Y分别表示合并双方的修改状态; 而在一般情况下X表示暂存区域(index)的状态, Y表示工作目录的状态(work tree): ’ ’ = unmodified M = modified A = added D = deleted R = renamed C = copied U = updated but unmerged 未被追踪(untracked)的文件, XY = ??; 默认不显示忽略的文件(ignored), 除非使用--ignore选项, 此时XY = !!. 查看已暂存和未暂存的修改 1 $ git diff 用来比较工作目录中当前文件和暂存区域快照之间的差异, 使用--staged选项查看已经暂存的将要添加到下次修改的内容 提交更新 1 $ git commit 这种方式会启动shell的环境变量$EDDITOR所指定的软件, 一般是VIM或emacs, 或者使用git config --global core.editor来指定编辑器, 使用-v选项将diff的内容追加到编辑器中, 使用-m '${comment}'选项来直接添加提交信息, 而不打开编辑器. ...