一些笔记

考虑到中间继承有几堂课摸鱼了，导致有的知识点没有呈现在代码里，这里先写一点。

implements & extends

1. 先理解「类（Class）」和「接口（Interface）」

类（Class）

是什么：类的本质是 “一种具体事物的模板”。
- 比如：Dog（狗）、Car（汽车）、Student（学生）。
特点：
- 类可以 直接创建对象（例如：Dog myDog = new Dog();）。
- 类中可以包含 属性（数据） 和 方法（行为） 的具体实现。

接口（Interface）

是什么：接口的本质是 “一类行为的规范”。
- 比如：Runnable（可跑的）、Swimmable（可游泳的）、Serializable（可序列化的）。
特点：
- 接口 不能直接创建对象（比如不能直接 new Runnable()）。
- 接口只定义 方法的签名（方法名、参数、返回值），但不写具体实现。
- 接口更像一种“合同”：谁实现了这个接口，就必须履行这个合同（实现所有方法）。

2. 什么是「超类型（Hypernym）」和「子类型（Hyponym）」？

这两个术语是语言学和计算机科学中的概念，用来描述 “一般与特殊” 的关系。

超类型（Hypernym）

广义上的类别，代表更抽象、更通用的概念。
- 例如：
  - 动物（Animal）是狗（Dog）的超类型。
  - 交通工具（Vehicle）是汽车（Car）的超类型。
  - 列表（List）是动态数组（ArrayList）的超类型。

子类型（Hyponym）

具体化的类别，代表更具体、更特殊的概念。
- 例如：
  - 狗（Dog）是动物（Animal）的子类型。
  - 汽车（Car）是交通工具（Vehicle）的子类型。
  - 动态数组（ArrayList）是列表（List）的子类型。
简而言之，implements用于继承方法，extends用于继承类

super

当子类不得不访问父类的方法时，可以用super.function()来直接调用父类方法（此时便可以访问父类私有的一些成员变量），此处的super有点像this。

在调用父类方法前可以写一行super(x);增加代码可读性。x为下面调用方法中需要传入的参数。

如果不写，会自动调用默认的函数（多个重载函数中选无参数传入的）。

@Override

在重写父类方法前标记，没有实际用处，相当于注释，但是可以检查下方的拼写错误。

编译的静态检查

简而言之，编译的时候会根据对象的静态类型进行检查，比如：(maxDog返回值为Dog类，Poodle为Dog子类，意为贵宾犬，下面的两个参数均为贵宾犬的种类)

Dog largerdog = maxDog(frank,franJr);

Poodle largerPoddle = maxDog(frank,franJr);

虽然我们知道frank和franJr都是属于Poodle的，但是在定义maxDog的时候编译器只知道他们是Dog类的，因此会报错。

这里可以通过添加(Poodle)进行强制的类型转换避免报错。

数据结构

并查集 Disjoint Sets

一种数据结构，最终导出的简化版本为树。通过多次查找可以实现路径压缩，进一步简化结构。

二叉搜索树 BST

对无序集合进行有序排列来简化查找操作。

特殊地，树的高度决定了最坏情况的运行情况。即当树高度为N时(spindly tree)，运行时间为θ(N)，其余情况(bushy tree)为θ(logN)。

TODO: 理解渐进分析、大O记法

分裂树 B-Tree

为了防止BST过于spindly，允许多个节点（有序的）合并为同一个节点，同时设定一个临界值。当节点内含有节点数目超过临界值后，取中间的节点上升到其父节点位置，大于和小于它的再分开排，最后其父节点将有三个子节点。上限临界值为3时分裂树又叫2-3 树。

红黑树 Red Black Trees

用标准的BST来实现B-tree，方法为通过创建一个red虚拟链接把B-tree中同集合的两个节点链接起来。虚拟链接不是真实的链接，只是用来表示连接的两个点本应该在一起。

LLRB tree（左偏红黑树，红色虚拟链接总向左偏，这样的规定方便算法实现）表现为一个普通的BST，可以和一个2-3 tree一一对应（其实就是一种结构的两种表现形式，2-3 tree虽然直观，但是代码上实现难度或许比较大）。LLRB高度容易高于对应的2-3 tree，但不会超过其二倍.渐近分析表明这样的倍数关系对运行效率没有影响。

插入时：使用红色链接。
如果有一个右倾的“3节点”，左倾违规。
- 向左旋转相应的节点以修复。
如果有两个连续的左链接，不正确的4节点违规。
- 向右旋转相应的节点以修复。
如果有任何节点有两个红色子节点，临时4节点。
- 颜色翻转节点以模拟分裂操作。

最后一个细节：级联操作。

旋转或翻转操作可能会导致需要修复的额外违规。

哈希表

通过哈希函数把字符串映射到整型变量。举个例子，ASCII码共有128位，可以通过127进制把任意单词转化为数字。

二叉最小堆

用于解决优先队列（PQ）问题
表现为完全二叉树，即缺失的节点仅存在于最底层，存在的节点尽可能靠左
节点允许重复
每个节点必定小于等于其任意子节点
值得注意的是，一对兄弟节点之间的大小关系没有要求，不要在实现算法时出现思维惯性

Name	Storage Operation(s)	Primary Retrieval Operation	Retrieve By:
List	`add(key)` `insert(key, index)`	`get(index)`	index
Map	`put(key, value)`	`get(key)`	key identity
Set	`add(key)`	`containsKey(key)`	key identity
PQ	`add(key)`	`getSmallest()`	key order (a.k.a. key size)
Disjoint Sets	`connect(int1, int2)`	`isConnected(int1, int2)`	two int values

树的先序、中序、后序遍历

高中学过，此处不再赘述，仅介绍一种新学到的技法。从根节点出发逆时针绕着树的每个节点紧贴着走直至回到根节点，在先序/中序/后序的情况下，在穿过节点左边/底部/右边的时候即视为访问了该节点。

图

可以认为图是树的父类，树是一种更严格化的图。典型的例子，四个节点呈棱形状相连不是树但是可以是图；同一对节点可以有两个直接相连的边；节点可以和自己相连。

简单图

“同一对节点可以有两个直接相连的边；节点可以和自己相连。”去掉这两种情况即可得到简单图。简单图可以分为有向图和无向图，取决于在建模什么，可以在链接的边上添加Edge Labels。

深度优先搜索(DFS)：从起始点出发优先探索完子图，再尝试回溯到上一节点探索下一个子图，可以用递归实现。可以帮助我们找到通往每一个顶点的路径。
广度优先搜索(BFS)：基于队列实现，将即将探索的节点放到队列尾部，优先探索前面的节点。

最短路径问题

显然地，在最短路径中不可能出现循环现象，由此可以推导出结论：最短路径的集合对应的数据结构为树，我们称之为最短路径树。

迪杰斯特拉算法(Dijkstra)

基于BFS进行检索，优先检索未被检索过的最近节点，将当前距离和当前最短路径树中该节点对应距离（必须是非负数）进行比较，放弃较长的距离，完成对图的遍历后即可得到最短路径树。

值得注意的是，迪杰斯特拉算法的操作本身耗时为O(N)，而优先队列复杂度为O(logN)。

下面是伪代码：

Dijkstra's:
PQ.add(source, 0)
For other vertices v, PQ.add(v, infinity)
While PQ is not empty:
p=PQ.removeSmallest()
Relax all edges from p
Relaxing an edge p -> q with weight w:
if distTol[p] + w < distTol[q]:
distTol[q] = distTol[p] + w
edgeTo[q] = p
PQ.changePriority(q, distTo[q])

A*算法
在计算优先级的时候将路径成本和惩罚量（提前给出，又叫启发式评估）相加，减少不必要的探索。

最小生成树(MST)

最小（包含最少边/权重最小）的可以接触每个节点、没有循环的树。

割边属性：把图的所有节点随机分成两组，可以连接两不同组节点的边中权重最小的边一定在最小生成树中。经过足够多次数的上述操作，可以得到最小生成树。
Prim’s算法：随机选一个起点，将接触过的点和未接触的点分成两组，按照割边属性对最小权重的割边进行探索。循环至找到所有节点。

值得注意的是，Prim’s算法中的Relax操作的评估权重为指定节点和当前节点的边权重，无需像Dijkstra算法一样添加当前节点到初始节点的距离权重。即只根据到正在构建的树的距离寻找最近边。

public class PrimMST {
    public PrimMST(EdgeWeightedGraph G) {
        edgeTo = new Edge[G.V()];
        distTo = new double[G.V()];
        marked = new boolean[G.V()];
        fringe = new specialPQ<Double>(G.V());

        distTo[s] = 0.0;
        setDistancesToInfinityExceptS(s);
        insertAllVertices(fringe);

        /* Get vertices in order of distance from tree. */
        while (!fringe.isEmpty()) {
            int v = fringe.delMin();
            scan(G, v);
        }
    }
}