Dijkstra 双栈算术表达式求值算法
原目录：算法（第四版） / 算法合集
Dijkstra双栈算术表达式求值算法
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Evaluate {
public static void main(String[] args){
ResizingArrayStack<String> ops = new ResizingArrayStack<>();
ResizingArrayStack<Double> vals = new ResizingArrayStack<>();
while (!StdIn.isEmpty()){
String s = StdIn.readString();
if(s.equals("("));
else if(s.equals("+")) ops.push(s);
else if(s.equals("-")) ops.push(s);
else if(s.equals("*")) ops.push(s);
else if(s.equals("/")) ops.push(s);
else if(s.equals("sqrt")) ops.push(s);
else if(s.equals(")")){
String op = ops.pop();
double val = vals.pop();
if(op.equals("+")) val += vals.pop();
else if(op.equals("-")) val -= vals.pop();
else if(op.equals("*")) val *= vals.pop();
else if(op.equals("/")) val = vals.pop() / val;
else if(op.equals("sqrt")) val = Math.sqrt(val);
vals.push(val);
}
else {
vals.push(Double.parseDouble(s));
}
}
StdOut.println(vals.pop());
}
}
要点
- 准备两个栈:运算符栈,操作数栈
- 忽略左括号,将操作数和运算符分别压入对应栈内
- 遇到右括号,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的结果压入操作数栈
- 方法局限性:最多只能有两个操作数在括号内运算且算式必须有左括号和右括号
注意事项
所有的字符间都要以空格隔开,在控制台下StdIn.isEmpty()需要接收ctrl+z才能结束输入,在idea中同理接收ctrl+d才能结束输入
二分查找 BinarySearch
原目录：算法（第四版） / 算法合集
要求：程序接受一个白名单文件（一列整数）作为参数，过滤名单中存在的条目，将其余条目打印
1.寻常实现（利用书中管道和重定向接收输入）
public class BinarySearch{
public static int rank(int key, int[] a){
int low = 0;
int high = a.length - 1;
while(low <= high){
int mid = (low + high)/2;
if(a[mid] < key) low = mid + 1;
else if(a[mid] > key) high = mid - 1;
else return a[mid];
}
return -1;//无键值，返回-1
}
pubilc static void main(String[] args){
int[] whitelist = In.readInts(args[0]);
Arrays.sort(whitelist);
while(!StdIn.isEmpty()){
int key = StdIn.readInt();
if(rank(key, whitelist) < 0)
StdOut.println(key);
}
}
要点
1.high = a.length - 1；
2.low <= high: 当a[] = {1,3,5},查找5时,当条件只是low < high,无法找到5；
3.mid ± 1： 若没有±1操作，当无键值时，无法有low <= high跳出循环
2.递归实现
public int rank(int low, int high, int key, int[] a){
int mid = (low + high)/2;
while(low <= high){
if(a[mid] == key) return a[mid];
else if(a[mid] < key) return rank(mid+1, high, key, a);
else return rank(low, mid-1, key, a);
}
return -1;
}3.运行注意
在存放java文件的文件夹中运行PowerShell，输入cmd命令后执行java BinarySearch tinyW.txt < tinyT.txt,此时tinyW.txt即参数args[0],tinyT.txt中的数由StdIn读取
算法1.1-1.2 下压栈(LIFO)
原目录：算法（第四版） / 算法合集
下压栈(LIFO)
算法1.1 可动态调整数组大小的实现
public class ResizingArrayStack<Item> implements Iterable<Item> {
private Item[] a = (Item []) new Object[1];//元素栈
private int N;//元素个数
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void resize(int max) {
Item[] temp = (Item []) new Object[max];
for(int i = 0; i < max; i++) {
temp[i] = a[i];
}
a = temp;
}//调整数组大小
public void push(Item item) {
if(N == a.length) resize(2*a.length);
a[N++] = item;
}//添加元素到栈顶
public Item pop() {
Item item = a[--N];
a[N] = null;//防止对象游离
if(N > 0 && N == a.length/4) resize(a.length/2);
return item;
}//从栈顶删除元素
@Override
public Iterator<Item> iterator() {
return new ReverseArrayIterator;
}
private class ReverseArrayIterator implements Iterator<Item> {
private i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
@Override
public void remove() {}
}
}
要点
- 可变数组下压栈的主类和内部类需要分别实现Iterable,Iterator接口,从而实现LIFO逆序迭代,否则会按照数组FIFO迭代;
- algs4书中对于remove()总为空,避免在迭代中穿插修改数据结构的操作
- 为保证数组缩减后有一半的空间利用率,判断条件应该是N == a.length/4
- 删除栈顶元素时,实际上被弹出元素的引用仍保存在数组中,但该元素永远不会被访问,直到下次push()后,原有引用指向新元素.Java垃圾收集器才会回收空间,期间造成空间浪费,使用a[N] = null避免元素游离.
特点
- 算法1.1的每项操作用时与集合大小无关:操作始终只针对栈顶元素;
- 空间需求总是不超过集合大小乘一个常数;
- 栈永远不会溢出,使用率也不会低于四分之一,除非栈为空时,数组大小为1;
算法1.2 链表实现
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> {
private Node first;
private int N;
private class Node {
Item item;
Node next;
}
public boolean isEmpty(){ return N == 0;}
public int size(){ return N; }
public void push(Item item){
Node oldFirst = first ;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
public Item pop(){
Item item;
item = first.item;
first = first.next;
N--;
return item;
}
@Override
public Iterator<Item> iterator(){
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext(){ return current != null;}
@Override
public Item next(){
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove(){}
}
}
要点
- 实例变量:头结点first
- 完成内部类Node;
- isEmpty()可以判断N == 0或first == null;
- 迭代实现同上
特点
- 可以处理任意类型数据;
- 所需空间总是和集合大小成正比;
- 操作所需时间和集合大小无关(链式结构);
关于内部类实现泛型接口*
算法内部类
private class ListIterator implements Iterator<Item>{}
//不是private class ListIterator<Item> implements Iterator<Item>算法外部类
public class Stack<Item> implements Iterable<Item>当类实现泛型接口时，不能确定接口中的泛型,这时就要求这个类也必须定义泛型，而且泛型名称要一致,因此主类Stack后也要定义泛型;当内部类实现和主类泛型类型一致的接口(本算法中),此时泛型已经可以由主类的定义判断,则内部类的泛型无需在定义泛型,如果重复定义会提示错误.
算法1.3 队列(FIFO)
原目录：算法（第四版） / 算法合集
先进先出队列
数组实现(Ex1_3_14)
import java.util.Iterator;
public class ArrayQueue<Item> implements Iterable<Item> {
private Item[] a = (Item[]) new Object[1];
private int N = 0;
private int head = 0;//出队元素索引
private int tail = 0;//入队元素索引
public boolean isEmpty() {
return N > 0;
}
public int size() {
return N;
}
public void resize(int max) {
Item[] temp = (Item[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
public void enqueue(Item item) {
if (N == a.length) resize(2 * a.length);
a[N++] = item;
tail++;
}//从队尾插入
public Item dequeue() {
Item item = a[--N];
if (N == a.length / 4) resize(a.length / 2);
head++;
return item;
}//从队首离开
@Override
public Iterator<Item> iterator() { return new ArrayIterator(); }
private class ArrayIterator implements Iterator<Item> {
private int i = head;
@Override
public boolean hasNext() { return i <= tail; }
@Override
public Item next() { return a[i++]; }
@Override
public void remove() { }
}
}
要点
- 两个int变量,head和tail作为索引,当元素入列,进入队尾,tail++;当元素出列,离开队首,head++,通过这种方法保证只有head和tail间的元素可以被操作
算法1.3 先进先出队列(链表实现)
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item>{
private Node first;
private Node last;
private int N;
private class Node{
Item item;
Node next;
}
public boolean isEmpty(){ return N == 0 ;}
public int size(){ return N;}
public void enqueue(Item item){
Node oldLast = last;
last = new Node();
last.item = item;
last.next = null;
if(isEmpty()) first = last ;//链表为空,first,last同时指向新节点
else oldLast.next = last;
N++;
}
public Item dequeue(){
Item item = first.item;
first = first.next;
if(isEmpty()) last = null;//链表为空,更新last
N--;
return item;
}
@Override
public Iterator<Item> iterator(){ return new QueueIterator(); }
private class QueueIterator implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext(){ return current != null;}
@Override
public Item next(){
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove(){}
}
}
要点
- 定义内部类Node
- Node型的实例变量first和last分别指向最早和最晚添加进的节点
- enqueue()中,创建节点后,链表为空时,first和last同时指向新节点
- dequeue()中,删除节点后,链表为空时,last为null
特点
- 可以处理任何类型的数据
- 所需空间和集合大小成正比
- 操作所需时间和集合大小无关
算法1.4 背包(FIFO)
原目录：算法（第四版） / 算法合集
算法1.4 背包(Bag)
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item>{
private class Node{
Item item;
Node next;
}
private Node first;
private int N;
public boolean isEmpty(){ return N == 0; }
public int size(){ return N; }
public void add(Item item){
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}//和Stack的push()相同
@Override
public Iterator<Item> iterator(){
return new ListIterator();
}
private class ListIterator implements Iterator<Item>{
private Node current = first;
@Override
public boolean hasNext(){ return current != null;}
@Override
public Item next(){
Item item = current.item;
current = current.next;
return item;
}
@Override
public void remove(){}
}
}
要点
- 背包也是FIFO策略,即一个没有pop()的Stack,将push()改名为add();
特点
- 可以处理任何类型的数据
- 所需空间和集合大小成正比
- 操作所需时间和集合大小无关
算法1.5 union-find并查集算法
原目录：算法（第四版） / 算法合集
算法1.5 union-find并查集
场景
当程序从输入中读取整数对(p,q)时,如果已知所有整数对都不能说明(p,q)是相连的,则输出整数对,否则忽略当前整数对,读取下一对.
1.5.1 union-find算法
API
| 返回类型 | 方法参数 | 说明 |
| UnionFind(int N) | 以整数标识初始化N个触点 | |
| void | union(int p, int q) | 在p和q之间添加一条连接 |
| int | find(int p) | p所在分量的标识符 |
| boolean | connected(int p, int q) | 如果p和q存在于同一个分量中返回true |
| int | count() | 已经连通的分量 |
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class UnionFind {
private int[] id;//以触点为索引
private int count;//分量个数
public UnionFind(int N){
count = N;
id = new int[N];
for(int i = 0; i<N; i++) id[i] = i;//开始每个分量只有一个触点
}
public int count(){ return count;}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int find(int p){
return id[p];
}
//归并方法
public void union(int p ,int q){
int pID = find(p);
int qID = find(q);
if(pID == qID) return;
for(int i = 0; i<id.length; i++){
if(id[i] == pID) id[i] = qID;
}
}//union方法使得连通的触点对于的id[]值相同
public static void main(String[] args){
int N = StdIn.readInt();
UnionFind uf = new UnionFind(N);
while (!StdIn.isEmpty()){
int p = StdIn.readInt();
int q = StdIn.readInt();
if(uf.connected(p,q)) continue;
uf.union(p,q);
StdOut.println(p + " " + q);
}
StdOut.println(uf.count + " components");
}
}
要点
- 主要实现在于维护一个整型数组id[],开始每个id[i]即代表一个连通的分量,元素值即索引值,共有N个,之后每union()两个触点p q,就让两个触点元素值都为q,最终一个分量中的元素id值都相等
特点
- 无法处理大型问题:每一对输入union()都需要扫面整个id[]数组,算法增长级别为平方级别.
1.5.2 quick-union算法
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class QuickUnion {
private int[] id;//以触点为索引
private int count;//分量个数
public QuickUnion(int N){
count = N;
id = new int[N];
for(int i = 0; i<N; i++) id[i] = i;//开始每个分量只有一个触点
}
public int count(){ return count;}
public boolean connected(int p, int q){
return find(p) == find(q);
}
//回溯到根节点
public int find(int p){
while (id[p] != p) p = id[p];
return p;
}
//归并方法
public void union(int p ,int q){
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot) return;
id[pRoot] = qRoot;
count--;
}//union方法使得连通的触点拥有相同的根节点
}
对比1.5.1
- 基于同一组数据结构--以触点为索引的id[]数组
- find()中,从给定触点开始,不断回溯到上一节点,直至初值的根节点pRoot,union()直接将另一节点的根节点qRoot赋值给id[pRoot]使得两个分量归并为一棵树
要点
- union()的实现只用了一条语句就将一个根节点变为另一个根节点的父节点
特点
- quick-union算法的成本依赖于输入,如果最坏情况:不断输入0-i整数对,此时为平方级别,而最佳情况可能是现象级别,不能保证quick-union算法始终快于quick-find
1.5.3 加权quick-union算法
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class WeightedQuickUnionUF {
private int[] id;//父链接数组
private int[] sz;//各个根节点对应分量大小
private int count;//连通分量个数
public WeightedQuickUnionUF(int N){
count = N;
id = new int[N];
for(int i = 0; i < N; i++) id[i] = i;
sz = new int[N];
for(int i = 0; i < N; i++) sz[i] = 1;
}
public int count(){ return count;}
public boolean connected(int p, int q){
return find(p) == find(q);
}
public int find(int p){
while (p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int i = find(p);
int j = find(q);
if(i == j) return;
if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i];}
else{ id[j] = i; sz[i] += sz[j];}
count--;
}
}
对比1.5.2
- 多了int[] sz用来保存各个根节点对应分量大小(不同树的大小)
- union通过比较sz[find(p)]和sz[(q)]将小树连接到大树上
要点
- sz[i]开始都初始化为1,一个触点
- 将小树连接到大树上
特点
- 加权算法中远离根节点的节点较少,只有一个节点被归并到大树中的情况很常见
- 加权算法构造的森林中任意节点最多深度lgN,且最坏情况下find(),connected()和union()成本增长数量级为logN
1.5.4 路径压缩的加权quick-union算法(最优算法)
//压缩路径算法区别只在find()
public int find(int p){
int root = p;
while (root != id[root]) root = id[root];//找到根节点
while (root != p) {
int temp = id[p];//temp暂存父节点作为下次循环的索引
id[p] = root;//将当前节点直接连接到根节点
p = temp;//还原索引
}
return root;
}同未压缩路径方法的联系区别
- 只需要未find()增加一个循环,顺路将路径上遇到的节点都直接链接到根节点,最终可以得到几乎完全扁平化的树
特点
- 理性状态下,我们希望每个节点都直接链接到它的根节点上,但又不想像quick-find一样修改大量链接,于是在检查节点的同时将它们直接链接到根节点
四种算法比较
(最坏情况下存在N个触点时成本的增长数量级)
| 算法 | 构造函数 | union() | find() |
| quick-find算法 | N | N | 1 |
| quick-union算法 | N | 树的高度 | 树的高度 |
| 加权quick-union算法 | N | lgN | lgN |
| 路径压缩的加权quick-union算法 | N | 非常接近但没有达到一 | 同理 |
| 理想情况 | N | 1 | 1 |
算法2.1-2.3 初级排序算法
原目录：算法（第四版） / 算法合集
初级排序算法
算法2.1 选择排序(升序)
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Selection {
public static void sort(Comparable[] a){
for(int i = 0; i < a.length; i++){
int min = i;
for(int j = i + 1; j < a.length; j++){
if(less(a[j],a[min])) min = j;
}
exch(a,i,min);
}
}//升序选择排序
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}//比较v是否小于w
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}//元素交换
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}//单行打印
public static boolean isSorted(Comparable[] a){
for(int i = 1; i < a.length; i++){
if(less(a[i],a[i-1])) return false;
}
return true;
}//判断是否有序
public static void main(String[] args){
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
要点
- 选择排序外循环负责移动当前位置,内循环比较当前元素和已知最小元素,选择剩余元素中最小者安排在当前位置,选择排序不会访问索引左侧的元素
- 核心变量:i:控制索引,j:负责与索引元素比较的位置,min:时刻标记剩余元素中最小的索引
特点
- 对于长度为N的数组:选择排序需要大约N²/2次比较(调用less())和N次交换(调用exch())
证明:
public static void sort(Comparable[] a){
for(int i = 0; i < a.length; i++){
int min = i;
for(int j = i + 1; j < a.length; j++){
if(less(a[j],a[min])) min = j;
}
exch(a,i,min);
}
}根据sort(),j范围[1,N-1],则比较次数(N-1)+(N-2)+...+1 == N(N-1)/2 ~ N²/2,i范围[0,N-1]则交换N次
2. 运行时间和输入(初始状态)无关:为了找出最小元素而扫描一遍数组并不能为下一遍扫描提供信息,一个有序数组和一个完全随机的数组排序时间是一样的
3. 数据移动是最少的:N次交换--交换次数和数组大小时线性关系,书中其他算法都不具有此特征,大部分增长级都是线性对数或平方级别.
算法2.2 插入排序(升序)
//只有sort()不同
public static void sort(Comparable[] a){
for(int i = 1; i < a.length; i++){
for(int j = i; j > 0 && less(a[j],a[j-1]); j--){
exch(a,j,j-1);
}
}
}//升序插入排序要点
- 插入排序外循环从a[1]开始,设定当前索引左侧元素都是有序的,内循环只需把索引元素插入到前面的合适位置,插入排序不会访问索引右侧的元素
- 低级错误:for(a;b;c){d}循环中b满足时,执行d再执行c,若b不满足,直接跳出循环;
特点
- 对于长度为N的数组:插入排序需要~N²/4次比较和~N²/4次交换.最坏情况下(完全倒序)需要~N²/2次比较和~N²/2次交换,最好情况下(已排好序)需要N-1次比较和0次交换
证明:
public static void sort(Comparable[] a){
for(int i = 1; i < a.length; i++){
for(int j = i; j > 0 && less(a[j],a[j-1]); j--){
exch(a,j,j-1);
}
}
}假设倒序:则比较次数1+2+...+(N-1) == N(N-1)/2 ~ N²/2,倒序下每次比较后都需要交换,次数相同;假设排好序: 内层for循环(j > 0 && less(a[j],a[j-1]))限制只用比较(N-1)次,且不用进入循环内部交换,则交换0次
2.
倒置: 数组中两个顺序颠倒的元素,如4,3,7,5,1中如果要求升序则倒置为4-1,4-3,3-1,7-5,7-1,5-1共6对
部分有序: 如果数组中倒置的数量小于数组大小的某个倍数,则该数组为部分有序的
插入排序的交换次数和倒置的对数相同,需要比较的次数>=倒置对数,<=倒置对数+(N-1)
证明: 交换一次就减少了一对倒置数,当倒置数为0,即排序完成;而每次交换一定有一次比较,且1到N-1之间的每个 i都可能需要一次额外的比较(在a[i]刚交换完,j--后确认a[i]是否到了合适的位置,这时发生额外的比较)
算法2.3 希尔排序(升序)
public class Shell {
public static void sort(Comparable[] a){
int N = a.length;
int h = 1;
while (h < N/3) h = h*3 + 1;//1,4,13,40,121,364......
while (h >=1){
for(int i = h; i < N; i++){
for(int j = i; j - h >= 0 && less(a[j],a[j-h]); j -=h)
exch(a,j,j-h);
}
h = (h-1)/3;
}
}//升序希尔排序要点
- 由插入排序可知,对于越接近有序的数组,插入排序效率越高.希尔排序即通过交换间隔h的元素,对数组局部排序,在最终h = 1时就是一般的插入排序.
- 希尔排序是使数组中任意间隔h的元素都是有序的,这样的数组被称为h有序数组,为了动态调整h达到灵活调整顺序的目的,需要通过循环实时调整或数组提前预存方式实现h的变化序列,称为增长序列,算法2.3使用序列1/2(3^k-1),h在[1,N/3)变化,可以是1,4,13,40,121,364,1093...
- 与一般插入排序对比
| 排序方式 | i初始值 | less参数 |
| 插入 | 1 | a[j],a[j-1] |
| 希尔 | h | a[j],a[j-h] |
特点
- 希尔排序的性能特征无法准确描述,但速度明显快于插入/选择排序,可以处理大型数组,目前只能说它的运行时间达不到平方级别
算法2.4 归并排序
原目录：算法（第四版） / 算法合集
归并排序
算法2.4自顶向下的归并排序(升序)
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Merge {
private static Comparable[] aux;
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}//比较v是否小于w
private static void sort(Comparable[] a){
aux = new Comparable[a.length];
sort(a, 0, a.length-1);
}
private static void merge(Comparable[] a, int lo, int mid, int hi){
int i = lo;
int j = mid + 1;
for(int k = lo; k <= hi; k++){
aux[k] = a[k];
}
for(int k = lo; k <=hi; k++){
if(i > mid) a[k] = aux[j++];
else if(j > hi) a[k] = aux[i++];
else if(less(aux[j],aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
private static void sort(Comparable[] a, int lo, int hi){
if(hi <= lo) return;
int mid = (lo + hi)/2;
sort(a, lo, mid);
sort(a, mid+1, hi);
merge(a, lo, mid, hi);
}
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}
public static void main(String[] args){
String[] a = In.readStrings();
sort(a);
show(a);
}
}
要点
- 原地归并的抽象方法:
private static void merge(Comparable[] a, int lo, int mid, int hi){
int i = lo;//左半部分索引
int j = mid + 1;//右半部分索引
for(int k = lo; k <= hi; k++){
aux[k] = a[k];//辅助数组aux
}
for(int k = lo; k <=hi; k++){//归并左右部分
if(i > mid) a[k] = aux[j++];//左半部分用完
else if(j > hi) a[k] = aux[i++];//右半部分用完
else if(less(aux[j],aux[i])) a[k] = aux[j++];//按大小插入
else a[k] = aux[i++];
}
}</code></pre>
- 对于长度为N的任意数组,自顶向下的归并排序需要1/2NlgN至NlgN次的比较
证明:令C(N)表示长度为N的数组排序所需的比较次数,通过递归的sort()可以得到C(N)≤C([N/2]+C([N/2])+N,第一项第二项分别为左右部分排序时比较次数,第三部分即归并比较次数(less调用次数),可知第三部分在[N/2]和N之间变化,当右半部分元素全部小于左边,执行N/2次j++后比较结束,当两边大小交错,最多比较N次结束.当N == 2n时,一二部分都为2n-1,则C(2n)=2C(2n-1)+2n,经过化简代换,C(N)=C(2n)=n2n=NlgN - 对于长度为N的任意数组,自顶而下归并排序最多需要访问数组6NlgN次
证明:每次归并,2N次复制(aux[i]=a[i]),2N次移回排好序元素(a[i]=aux[i]),加上最多比较时访问数组2N次(less(aux[j],aux[i]))
- compareTo的特殊性,导致只能按照字符串排序,因此数字排序有漏洞,如3 < 12;
自底向上的归并排序
public static void sort(Comparable[] a){
int N = a.length;
aux = new Comparable[N];
for(int sz = 1; sz < N; sz = sz*2){
for(int lo = 0; lo < N-sz; lo += 2*sz){
merge(a,lo,lo+sz-1, Math.min(lo+2*sz-1, N-1));
}//sz为子数组大小,lo为子数组索引,min()方法防止越界
}
}//一一归并,二二归并,四四归并,八八归并...
要点
- 算法2.4的2,3条同样适用
排序算法的复杂度
没有任何基于比较的算法能够保证长度为N的数组使用少于lg(N!)~NlgN次比较将长度为N的数组排序
证明:假设没有重复的主键,使用二叉树表示所有比较,树中的结点是一片叶子[i0,i1,i2...],表示排序完成且输入顺序就是0,1,2...,要么是一个内部结点[i:j]表示a[i]和a[j]之间进行了一次比较操作,左子树为a[i]<a[j]后的操作,右子树表示a[i]>a[j]后的操作.首先一棵树至少有N!个叶子节点,因为N个不同的逐渐一定有N!种排列;又由高度为h的树最多只可能有2h个叶节点,因此N!≤叶子节点数量≤2h,h即为最坏情况的比较次数,两侧取对数可得h至少为lgN!,而lgN!~NlgN
归并排序是一种渐进最优的基于比较的排序算法
已知算法2.4最坏情况下比较次数NlgN和任意基于比较的排序算法的最少比较次数增长级相同
归并排序的局限性
- 归并排序的空间复杂度不是最优的
- 实践中不一定会遇到最坏情况
- 除了比较,算法的其他操作(如访问数组)也可能很重要
- 不进行比较也可以进行某些数据排序
答疑
- 归并和希尔排序比较:
实际应用中,归并排序较快,但允许时间之间的差距在常数级别之内;
- 为什么不把aux[]声明为merge()的局部变量:
为了避免每次归并时,即使归并很小的数组也要创建一个新的数组,这样创建新数组会成为运行时间的主要部分,更好的方案是将aux[]变为sort的局部变量,作为参数传递给merge();
- 数组中存在重复元素时归并排序表现如何:
当所有元素都相同,加上一个判断a[mid]<=a[mid+1]就可以任务数组已经有序跳过merge(),从而使得任意有序的数组算法运行时间变为线性的;但当有多个不同重复值时,比如奇数为为a,偶数位为b,运行时间又回归线性对数(刚好满足所有的循环条件)
Review
- 自顶向下归并
sort(src, 0, src.length-1 )即hi = src.lenght-1
- 自底向上归并
N=src.length, 外层循环sz取值[1,N),内层lo取值[0,N-sz], min = lo, mid = lo + sz-1, hi = min(lo + 2*sz -1, N-1)
- 内循环lo每次改变2*sz
算法2.5 快速排序
原目录：算法（第四版） / 算法合集
快速排序
算法2.5 快速排序
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
public class Quick {
public static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a, int lo, int hi){
//if(lo >= hi + M) {Insertion(a,lo,hi); return; }//改进,小数组采用插入排序
if(lo >= hi) return;
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(Comparable[] a, int lo, int hi){
int i = lo;
int j = hi + 1;
Comparable v = a[lo];//默认a[lo]为切分元素
while (true){
while (less(a[++i],v)) if(i == hi) break;//从左到右直到有大于切分元素的元素
while (less(v,a[--j])) if(j == lo) break;//从右到左直到有小于切分元素的元素
if (i >= j) break;
exch(a,i,j);//只要i，j未相遇，则交换两处元素
}
exch(a,lo,j);//最终把切分元素与左子数组最后元素交换位置
return j;
}
//...
}
要点
- 快速排序是一种分治的排序算法,和归并互补:归并把数组分成两个子数组分别排序,然后归并两个有序的子数组使整体有序;快排是当两个子数组都有序时整个数组自然也有序了.归并时,递归sort发生在归并merge之前,快排中,归并sort发生在分切partition后
- 切分的一般策略:随意取a[lo]作为切分元素,然后从左到右直到找到>=它的元素,再从右到左找到<=它的元素,然后在两个指针未相遇时就可以交换两元素,指针相遇时,只需把a[lo]和左子数组最右侧元素交换,最终切分元素左侧的元素都比它小,右侧元素都比它大,再各自排序.
- sort中有StdRandom.shuffle方法,为了保证元素的随机性,避免切分时出现极大子数组和极小子数组的不均衡情况.
- 对于有大量重复值的情况,一般的快排不可避免会发生等值元素继续交换位置的现象.
特点
- 快排切分的内循环会用一个递增的索引(i++,j++)将数组元素和一个定值(v)比较,没有移动数据,而归并和希尔一般比快排慢,在于它们在内循环中移动数据
算法改进
- 小数组使用插入排序
if(lo >= hi + M) {Insertion(a,lo,hi); return; }//改进,小数组采用插入排序
- 取消while的边界测试--三取样切分:见Ex2_3_18
- 应对大量重复元素--三向切分:如下
三向切分
public class Quick3Way {
public static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a, int lo, int hi){
if(lo >= hi) return;
int lt = lo, i = lo+1, gt = hi;
Comparable v = a[lo];
while (i <= gt){
int cmp = a[i].compareTo(v);
if(cmp < 0) exch(a,lt++,i++);
else if(cmp > 0) exch(a,i,gt--);
else i++;
}
sort(a,lo,lt-1);//[lo,lt-1]间元素都小于v
sort(a,gt+1,hi);//[gt+1,hi]间元素都大于v
}
//...
}
分析
三项切分快速排序:从左到右遍历数组,指针lt使得a[lo...lt-1]中元素<v,gt使a[gt+1...hi]元素>v,a[lt,gt]元素都==v,这样只需要为a[lo...lt-1],a[gt+1...hi]两个子数组排序,忽略重复部分
- a[i] < v,交换a[lt]和a[i],lt++,i++;
- a[i] > v,交换a[gt]和a[i],gt--;
- a[i] == v, i++;
Review
- 一般快速排序：
- partition()中i从lo开始,j从hi+1开始,巧妙配合while中的++i和--j,保证从lo+1处开始扫描完全
- exch(a,lo,j)最后是j不是i,因为++i和--j的缘故,循环最后一步,i指向右子数组左侧,j指向左子数组右侧
- int j = partition(a,lo,hi);j即是分切元素,已经确定好了位置,无需排序,所以sort(a,lo,j-1);sort(a,j+1,hi);
- 三项切分快排：
- 无partition()，切分直接在sort()中完成;
- 三个变量,lt是"三项"的中间项起点,gt为中间项终点;
while (i <= gt){
int cmp = a[i].compareTo(v);
if(cmp < 0) exch(a,lt++,i++);
else if(cmp > 0) exch(a,i,gt--);
else i++;
}
- i与否问题:
while中,因为每次i都会变化,cmp需要每次重新计算.
(cmp<0)时,lt且i++,若此处i不变,第一次交换后a[i]=a[lo],cmp=0,依旧i++,所以exch()中直接执行;(cmp>0)时,gt--,i不变,因为第一次交换后,需再次比较换下来的a[gt]否小于v;
- while()循环条件之所以为(i<=gt):
原因与第三点最后相同:
若换下一个a[gt]后gt--,i == gt,即此时到了中项和右项交界,必须再判断一次换下的元素是否还小于等于v,甚至大于v,当小于等于v后i++,i > gt,跳出循环,当大于v后gt--, gt < i,跳出循环.
算法2.6 基于堆的优先队列
原目录：算法（第四版） / 算法合集
算法2.6 基于堆的优先队列
public class MaxPQ<Key extends Comparable<Key>> {
private Key[] pq;
private int N = 0;
public MaxPQ(int maxN){
pq = (Key[])new Comparable[maxN+1];//pq[0]未使用,数组容量加一
}
public boolean isEmpty(){ return N == 0;}
public int size(){ return N;}
public void insert(Key v){
if(N == pq.length - 1) resize(2*pq.length);
pq[++N] = v;
swim(N);
}
private boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}
private void exch(int i, int j){
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
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 (k*2 <= N){
int j = k*2;
if (less(j, j+1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
if (! less(k,j)) break;//比较父子大小
exch(k,j);
k = j;
}
}
private Key delMax(){
Key max = pq[1];
exch(1,N--);
pq[N+1] = null;//防止对象游离
if((N > 0)&&(N <= pq.length/4)) resize(pq.length/2);
sink(1);//恢复有序
return max;
}
private void resize(int size){
if (size <= N) return;
Key[] temp = (Key[])new Comparable[size];
for (int i = 1; i <= N; i++){
temp[i] = pq[i];
}
pq = temp;
}
}
算法分析
//插入
private void insert(Key v){
pq[++N] = v;
swim(N);
}
//删除最大元素
private Key delMax(){
Key max = pq[1];
exch(1,N–);
pq[N+1] = null;//防止对象游离
sink(1);//恢复有序
return max;
}
//上浮
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 (k2 <= N){
int j = k2;
if (less(j, j+1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
if (! less(k,j)) break;//比较父子大小
exch(k,j);
k = j;
}
}
对于一个含有N个元素的基于堆的队列,插入元素操作需要比较次数(less())不超过(lgN+1)次,删除最大元素操作需要不超过2lgN次操作
证明:已知两种操作都是需要在根结点和堆底移动元素,且路径长度不超过lgN.
- 对于insert(),当插入的第(N+1)个元素最大,上浮到根结点需要不超过(lgN+1)次比较;
- 对于delMax(),除了堆底元素,删除最大元素都需要先比较找出较大子结点,再比较父子结点确定是否上浮,总共不超过2lgN次比较.
要点
- pq[0]未使用,传入大小maxN,实际创建出大小(maxN+1)的数组
- delMax()中需要
pq[N+1]=null防止对象游离
算法2.7 堆排序
原目录：算法（第四版） / 算法合集
算法2.7
可以把任意优先队列当作一种排序方法:将所有元素插入一个查找最小元素的优先队列,重复调用删除最小元素,使用基于堆的优先队列实现此算法即堆排序
堆排序可以分为两个阶段:
- 堆的构造阶段:将原始数组重新组织安排进一个堆中
对于N个给定的元素,我们可以从左到右遍历数组,用swim()保证扫描指针左侧的所有元素是一棵堆有序的完全树.但更高效的办法是从右至左用sink()构造子堆,因为数组的每一个位置都是一个子堆的根节点,sink()对于这些子堆也适用.只需要扫描数组中一半元素,因为可以跳过大小为1的堆,即完全树最后一排.
- 下沉排序阶段:从堆中按递减顺序取出所有元素并得到排序结果
下沉排序中,将堆中最大元素删除,然后放入堆缩小后空出的位置.此处的"删除"只是暂时搁置的状态,不是真的删去.
private static void sink(Comparable[] a, int k, int N){
while(2*k <= N){
int j = 2*k;
if(j < N && less(a,j,j+1)) j++;
if(!less(a, k, j)) break;
exch(a, k, j);
k = j;
}
}
public static void sort(Comparable[] a){
int N = a.length - 1;
//从右至左sink构造子堆,且可以跳过大小为1的子堆
for(int k = N/2; k >= 1; k–) sink(a, k, N);
while (N > 1){
exch(a, 1, N–);//删除最大元素,放入堆缩小后空出位置
sink(a, 1, N);//恢复顺序
}
}
算法分析
将N个元素排序,堆排序只需少于(2NlgN+2N)次比较(以及一半次数的交换)
证明:2N来自于构造堆时,依次构造3,7,15,31...的堆,2NlgN来自于每次下沉最大可能要2lgN次比较
算法特点
堆排序是所知唯一能同时最优地利用空间和时间的方法,但现在系统很多应用很少使用,因为它无法利用缓存
Review
- 关于N=a.length-1,在MaxPQ中,pq[0]无元素,insert()中++N,N和最大角标始终相等,即最末尾为元素pq[i],那N==i,类比堆排序中,调用sort()的数组长length,但最末尾元素为a[lenght-1],N应该为a.length-1
- 边界取等问题:
- sort()堆构造阶段
for(int k = N/2; k >= 1; k--) sink(a, k, N),k>=1,当k=1时就是使得sink(a[1])
- sort()下次排序阶段
while (N > 1),若取1,最后exch(a,1,1)无意义
算法3.1 顺序查找(无序链表)
原目录：算法（第四版） / 算法合集
算法3.1 无序链表中的顺序查找
实现:符号表的实现使用私有内部类Node保存键值对,get()会顺序地搜索链表查找给定的值,put()的实现会顺序搜索链表查找给定的键,找到则更新值,否则创建新结点并插在链表开头.
public class SequentialSearchST<Key, Value>{
int size = 0;
private Node first;
private class Node{
Key key;
Value value;
Node next;
public Node(Key key, Value value, Node next){
this.key = key;
this.value = value;
this.next = next;
}
}
private Value get(Key key){
for (Node x = first; x != null; x = x.next){
if (key.equals(x.key))
return x.value;//找到键值,并返回
}
return null;//无键值
}
private void put(Key key, Value value){
for (Node x = first; x != null; x = x.next){
if (key.equals(x.key)) {
x.value = value;//找到键值,并更新
return;
}
}
first = new Node(key, value, first);//无键值,则在头结点插入新键值
size++;
}
private int size(){ return size;}
private void delete(Key key){
//延时删除先将键值置空put(key, null),之后一并删除空值结点
//即时删除
for (Node x = first; x != null; x = x.next){
if (x.next.key.equals(key))
x.next = x.next.next;
}
}
}
算法分析
- 查找在最坏情况下序O(N),插入N个不同键需要~N²/2次比较(1+2+...+N)
- 基于链表实现符号表和顺序查找都是非常低效的
算法3.2 二分查找符号表(基于有序数组)
原目录：算法（第四版） / 算法合集
算法3.2 有序数组中的二分查找
实现:这种符号表使用一对平行的数组,一个存储键,一个存储值,核心是rank()方法,返回表中小于给点键的键数,对于get(),只要键存在,rank()即可指明位置,put()同理
public class BinarySearchST<Key extends Comparable<Key>, Value>{
private Key[] keys;
private Value[] values;
private int N;
public BinarySearchST(int capacity){
keys = (Key[])new Object[capacity];
values = (Value[])new Object[capacity];
}
private boolean isEmpty(){ return N==0;}
private int rank(Key key){
int lo = 0, hi = N-1;
while (lo <= hi){
int mid = lo + (hi-lo)/2;
int cmp = keys[mid].compareTo(key);
if (cmp < 0) lo = mid+1;
else if (cmp > 0) hi = mid-1;
else return mid;
}
return lo;//return保证即便没有该键也能返回小于该键的键数
}
//递归实现
private int rank(Key key, int lo, int hi){
if(lo > hi) return lo;
int mid = lo + (hi-lo)/2;
int cmp = keys[mid].compareTo(key);
if (cmp < 0) return rank(key, mid+1, hi);
else if (cmp > 0) return rank(key, lo, mid-1);
else return mid;
}
private int size(){ return N;}
private Value get(Key key){
if (isEmpty()) return null;
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0) return values[i];
else return null;
}
private void put(Key key, Value value){
int i = rank(key);
if (i < N && keys[i].compareTo(key) == 0){
values[i] = value;
return;
}
for (int j = N-1; j >= i; j--){
keys[j] = keys[j+1];
values[j] = values[j+1];
}
keys[i] = key;
values[i] = value;
N++;
}
private void delete(Key key){
if(isEmpty()) return;
int i = rank(key);
if (!(i < N && keys[i].compareTo(key) == 0)) return;
for (int j = N-1; j > i; j--){
keys[j-1] = keys[j];
values[j-1] = values[j];
}
}
}
说明
- 对于算法中递归的rank(key, 0, N-1),当表中存在该键,返回该键的位置,即排名,但即便表中不存在该键,rank()还是返回表中小于它的键的数量,当rank为迭代实现时,该性质还是满足.
算法分析
- 在N个键的有序数组中二分查找最多需要(lgN+1)次比较,无论是否成功
- 向大小N的有序数组中插入一个新元素在最坏情况下访问2N次数组,因此插入N个元素最坏要访问N²次数组
算法3.3 二叉查找树
原目录：算法（第四版） / 算法合集
算法3.3 二叉查找树
算法意义
对比链表和数组实现的符号表,要实现高效的插入,需要链式结构,但单链表无法实现二分查找,因为后者的高效来自于可以快速通过索引取得任何子数组的中间元素,而链表只能顺序查找.为了将二分查找的高效和链表的灵活性结合,需要复杂的数据结构--二叉查找树
符号表的6种实现
数据结构 实现 优点 缺点 单链表(顺序查找) SequentialSearchST 适合小型问题 对大型表很慢 有序数组(二分查找) BinarySearchST 最优的查找和空间,有序 插入操作很慢 二叉查找树 BST 实现简单,有序 没有性能上界保证,需额外空间 平衡查找树 RedBlackBST 最优的查找,插入,有序 链接需额外空间 散列表 SeparateChainHashST LinearProbingHashST 可快速查找与插入常见类型数据 需计算不同散列,无法有序操作,链接和空结点占空间
二叉查找树的描述
BST时一棵二叉树,每个结点都有一个Comparable的键(以及关联的值),且每个结点的键都大于其左子树的任意结点键而小于(有的书中包含等于)右子树的任意结点的键
API
方法 注释 ST() 创建符号表 void put(Key key, Value val) 存入键值对 Value get(Key key) 获取键key的对应值 void delete(Key key) 删去键值对key boolean contains(Key key) 判断键是否存在 boolean isEmpty() 表是否为空 int size() 表中键值对数量 Key min() 最小的键 Key max() 最大的键 Key floor(Key key) 小于等于key的最大键 Key ceiling(Key key) 大于等于key的最小键 int rank(Key key) 小于key的键个数 Key select(int k) 排名为k的键
基本实现
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class BST<Key extends Comparable<Key>, Value> {
//内部私有结点类
private class Node{
public Node(Key key, Value val, int N){}
}
//根结点指针
Node root;
//结点个数
private int size(){ return root.N; }//全部节点个数
public int size(Node x){//指定子树节点个数
if (x == null) return 0;
else return x.N;
}
//查询键所对应的值
public Value get(Key key){}
private Value gethelp(Node root, Key key){ }
//插入/更新键值对
public void put(Key key, Value val){}
private Node puthelp(Node root, Key key, Value val){ }
//或许子树上最大/最小结点
private Node getmin(Node root){}
private Node getmax(Node root){}
//删除以及相关函数
private Node deletemin(Node root){}
public Value delete(Key key){}
private Node deletehelp(Node root, Key key){}
//返回小于等于key的最大键(向下取整)
public Key floor(Key key){}
private Node floorhelp(Node root, Key key){ }
//返回大于等于key的最小件(向上取整)
public Key ceiling(Key key){ }
private Node ceilinghelp(Node root, Key key){ }
//排名:获取小于指定键的键数,即为指定键的名词,如size = 3,则最大键名词为2.
public int rank(Key key){ }
private int rankhelp(Node root, Key key){}
//选择:获取排名为k的键,即恰好有k个小于它的键
public Key select(int rank){}
private Node selecthelp(Node root, int rank){}
//中序遍历,分层次打印
private void printhelp(Node root, int level){ }
public void print(){}
//测试用例
public static void main(String[] args){
BST<String, Integer> tree = new BST<>();
while (!StdIn.isEmpty()){
tree.put(StdIn.readString(), StdIn.readInt());
}
tree.print();
}
}
数据表示
private class Node{
Key key;
Value val;
Node lc;
Node rc;
int N;
public Node(Key key, Value val, int N){
this.key = key;
this.val = val;
this.N = N;
}
}
Node root;
private int size(){ return root.N; }//全部节点个数
public int size(Node x){//指定子树节点个数
if (x == null) return 0;
else return x.N;
}
- 数据结构选择具有两个链接和一对键值对以及一个结点计数器(N)的结点类,对于结点计数器,即以该结点为根结点的子树所具有的结点个数,size()返回值即为N,对任意一个结点x,size(x) = size(x.lc)+size(x.rc)+1
- 要使用一个针对整棵BST的根结点指针root
get():查找
public Value get(Key key){ return gethelp(root, key); }
private Value gethelp(Node root, Key key){
if(root == null) return null;
int cmp = key.compareTo(root.key);
if (cmp < 0) return gethelp(root.lc, key);//小于结点键,进入左子树
else if (cmp > 0) return gethelp(root.rc, key);//大于结点键,进入右子树
else return root.val;//相等则返回值
}
- 查找:若树是空的,返回null;若查找键和根结点键相等,命中,否则就递归地进入子树查找,小于根结点键进入左子树,反之进入右子树
put():插入
public void put(Key key, Value val){
root = puthelp(root, key, val);
}
private Node puthelp(Node root, Key key, Value val){
if (root == null) return new Node(key, val, 1);
int cmp = key.compareTo(root.key);
//小于结点键,进入左子树
if (cmp < 0) root.lc = puthelp(root.lc, key, val);
//大于结点键,进入右子树
else if (cmp > 0) root.rc = puthelp(root.rc, key, val);
else root.val = val;
root.N = size(root.lc)+size(root.rc)+1;
return root;//返回插入结点后的子树(结点)
}
- 插入键值对的思想和查找类似,但注意如果发现表中已经有待插键,则直接更新值
- root.N也要随之更新, root.N = size(root.lc)+size(root.rc)+1;
有序性有关的方法和删除操作
getmin()/getmax():获得最大键和最小键
private Node getmin(Node root){
if (root.lc == null) return root;
return getmin(root.lc);
}
private Node getmax(Node root){
if (root.rc == null) return root;
return getmax(root.rc);
}</code></pre>
- 最大键沿着根结点右侧链接不断向下到右侧链接到头,最大键就是此结点的键,最小键类似
ceiling()/floor():向上取整和向下取整
//返回小于等于key的最大键(向下取整)
public Key floor(Key key){
Node floorNode = floorhelp(root, key);
if (floorNode == null) return null;
else return floorNode.key;
}
private Node floorhelp(Node root, Key key){
if (root == null) return null;
int cmp = root.key.compareTo(key);
if (cmp == 0) return root;//父结点键值恰好等于key,返回key
if (cmp < 0) return floorhelp(root.lc, key);//若key小于父结点键值,只可能出现在左子树
//只有右子树中存在小于等于key的结点,小于等于key的最大键才会出现在右子树,因为之后的cmp始终>0,不断进入右子树,最终返回null
//否则满足条件的就是根结点
Node temp = floorhelp(root.rc, key);
if (temp != null) return temp;
else return root;
}
//返回大于等于key的最小件(向上取整)
public Key ceiling(Key key){
Node ceilingNode = ceilinghelp(root, key);
if (ceilingNode == null) return null;
else return ceilingNode.key;
}
private Node ceilinghelp(Node root, Key key){
if (root == null) return null;
int cmp = key.compareTo(root.key);
if (cmp == 0) return root;
if (cmp > 0) return ceilinghelp(root.rc, key);
Node temp = ceilinghelp(root.lc, key);
if (temp != null) return temp;
else return root;
}</code></pre>
- 向下取整,给定key小于root.key,则小于等于key的最大键只能出现在左子树;当key大于root.key时,只有root的右子树中存在小于等于key的结点时,小于等于key的最大键才会出现在右子树中,否则根结点就是小于等于key的最大结点.
- 向上取整:同上
select():选择
//选择:获取排名为k的键,即恰好有k个小于它的键
public Key select(int rank){
Node selectNode = selecthelp(root, rank);
if (selectNode == null) return null;
return selectNode.key;
}
private Node selecthelp(Node root, int rank){
if (root == null) return null;
int r = size(root.lc);
if (r == rank) return root;
else if (r > rank) return selecthelp(root.lc, rank);
else return selecthelp(root.rc, rank-r-1);
}
- 当给定rank(排名,小于查找键的键个数)等与size(root.lc)时,root.key即为查找键,若小于,进入左子树,若大于进入右子树,但进入右子树时,由于size和rank的区别,rank要改变为rank-size(root.lc)-1,可以理解为砍去左子树和父结点后的select()
rank():排名
//排名:获取小于指定键的键数,即为指定键的名次,如size=3,则最大键名次为2
public int rank(Key key){ return rankhelp(root, key); }
private int rankhelp(Node root, Key key){
if (root == null) return 0;
int cmp = key.compareTo(root.key);
if (cmp == 0) return size(root.lc);
else if (cmp < 0) return rankhelp(root.lc, key);
else return (root.lc.N + 1 + rankhelp(root.rc, key));
}
- 当给定键和根结点键相等,返回左子树结点数;若给定结点小于根结点,则进入左子树递归;当大于根结点,则进入右子树,同时返回值上要加rc.lc.size()+1
delelemin():删除指定树最小键
private Node deletemin(Node root){
if (root == null) return null;
if (root.lc == null) return root.rc;
root.lc = deletemin(root.lc);
root.N--;
return root;
}
- 删除最小键,找最小键和getmin()一样,但找到后,需要将根结点的左子树设为返回值(即删除最小结点后的左子树),且N--.
delete():删除指定键值对
public Value delete(Key key){
Value temp = get(key);
//当键值对存在时再执行删除
if(temp !=null) root = deletehelp(root, key);
return temp;
}
private Node deletehelp(Node root, Key key){
if (root == null) return null;
int cmp = key.compareTo(root.key);
if (cmp < 0) root.lc = deletehelp(root.lc, key);
else if (cmp > 0) root.rc = deletehelp(root.rc, key);
else{//找到待删除结点
if (root.rc == null) root = root.lc;
if (root.lc == null) root = root.rc;//单孩子结点
Node temp = root;
root = getmin(root.rc);//用待删结点右子树最大结点作为新结点
root.rc = deletemin(root.rc);//新结点右子树即剔除原右子树最大结点后子树
root.lc = temp.lc;//新结点左子树为待删结点左子树,无改变
}
root.N--;
return root;//返回删除结点后的子树
}
删除结点需要先找到指定键值对,有三种情况:
- 结点无右子树,只需root = root.lc
- 结点无左子树,只需root = root.rc
- 结点有两个子树,这是只需要让其位置被右子树最小结点代替(选左子树最大结点在某些规定可有重复键的二叉树中,不满足左结点恒小的定义)
- 将指向待删结点root的引用保存为temp
- 将root指向getmin(root.rc)
- root.lc = t.lc
- root.rc = deletemin(t.rc)
- N--
与C++实现的对比
Node *temp = getmin(root->rc());
root->setval() = temp->val();
root->setkey() = temp->key();
root->setright() = deletemin(root->rc());
delete temp;
C++版本采用赋值法,找到右子树最小结点后将键值对赋值给root,然后删除此结点.
print():中序遍历打印
//中序遍历,分层次打印
private void printhelp(Node root, int level){
if (root == null) return;
printhelp(root.lc, level+1);
for (int i = 0; i<level ; i++) StdOut.print(" ");
StdOut.println(root.key);
printhelp(root.rc, level+1);
}
public void print(){
if (root == null) {
StdOut.println("the BST is empty");
return;
}
printhelp(root, 1);
}
- 遍历分三种:前序,中序,后序,要切换打印方式,只需要调整
printhelp(root.lc, level+1),StdOut.println(root.key),printhelp(root.rc, level+1)的顺序
- 对BST,中序遍历结果即为从小到大的顺序排列
性能分析
算法(数据结构) 最坏查找 最坏插入 平均查找 平均插入 是否有序 顺序查找(无序链表) N N N/2 N 否 二分查找(有序数组) lgN N lgN N/2 是 二叉树查找(BST) N N 1.39lgN 1.39lgN 是
- BST的基本操作性能依赖于其中的键分组足够随机(平衡)以消除长路径
算法3.4 红黑树
原目录：算法（第四版） / 算法合集
实现
红黑查找树是2-3树的具体实现
1. 替换3-结点
- 红黑树的基本思想:用标准的二叉查找树(全是2-结点)和一些额外信息(替换3-结点)来表示2-3查找树
- 结点类型:(结点的颜色指的是指向该结点的链接颜色)
- 红链接:将两个2-结点连成3-结点
- 黑链接:2-3树中的普通链接
private class Node{
Key key;
Value val;
Node left, right;
int N;
//结点颜色:指向该结点链接的颜色
boolean color;
Node(Key key, Value val, int N, boolean color){
this.key = key;
this.val = val;
this.N = N;
this.color = color;
}
}</code></pre>
2. 等价定义
- 红链接均为左链接
- 没有一个结点同时和两条红链接相连(4-结点)
- 该树是黑色平衡,即任意空链接到根结点的路径上黑链接数量相同
3. 一一对应
将红黑树中所有红链接画水平,那所有空链接到根结点的距离都将相同.再将红链接相连的结点合并,即可得到2-3树.红黑树结合了二叉树的高效查找和2-3树的平衡插入
4. 主要操作
4.1 旋转
某些操作下,可能出现红色右链接或两个连续红链接,需要旋转改变红链接指向,旋转操作保证了有序性和完美平衡性
- 左旋:避免产生右红链接
- 右旋:处理左侧两个连续红链接
Node rotateLeft(Node h){
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;//初始h的颜色不确定
h.color = RED;//旋转后左链接置红色
x.N = h.N;
h.N = 1+size(h.left)+size(h.right);
return x;
}
Node rotateRight(Node h){
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.N = h.N;
h.N = 1+size(h.left)+size(h.right);
return x;
}
4.2 插入
4.2.1 向2-结点插入新键
当只有一个2-结点时,插入一个新键后立刻旋转
- 新键<老键:增加红色结点,新树等价于3-结点
- 新键>老键:增加红色结点,但产生红右链,
root=rotateLeft(root),旋转修正
4.2.2 向双键树(3-结点)插入新键
- 新键>原数中两个键:最简单的情况,直接连接到3-结点右链接.此时树是平衡的,将两个链接的颜色由黑变红,即得到一棵由三个结点组成的,高为2的平衡树,真好对于2-3树
- 新键<原数中两个键:连接到最左边的空链接,形成了连续两条红链接(4-结点),只需把上层红链接右旋转即可回到情况一
- 新键介于二者之间:连接到左结点的右链(红色),有形成两条连续红链接,将右链左旋,回到情况二
4.2.3 颜色转换
在上述向双键树插入新键操作后,子结点都由红变黑,父结点变红,这是局部变换,不会影响整棵树的黑色平衡性
private void flipColors(Node h){
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
4.2.4 根结点总为黑色
红色结点说明结点是3-结点的一部分,但根结点并不满足,则每次插入后根结点都设为黑,且每当根结点由红变黑,树高加1
4.2.5 红链接向上传递
在2-3树中,在一个3-结点下插入新键->临时创建4-结点->分解,传递中间值到父结点->父结点是一个2-结点或为根结点->若为后者,则分解根结点.
对应到红黑树中就是红链接向上传递,插入->旋转->颜色转换->红链接转移至中结点->重复(和新插入结点效果一样)->直到非红右链接/非连续红链接/非根结点
4.2.6 插入算法
- 插入操作只有以下三种:
- 左子结点黑色,右子结点红色->左旋
- 左子结点和左子结点的左子结点都为红色->右旋
- 左右子结点都为红色->颜色转换
- 红黑树平衡性的调整是自下而上的,所以在put()递归插入语句后,再用if判断以上三种情况,并且,三条语句有顺序(根据4.2.2分析)
public class RedBlackBST<Key extends Comparable<Key>, Value > {
private Node root;
private static final boolean RED = true;
private static final boolean BLACK = false;
private class Node{}
private boolean isRed(Node x){
if (x == null) return false;
return x.color == RED;
}
private Node rotateLeft(Node h){}
private Node rotateRight(Node h){}
private void flipColors(Node h){}
public int size(){ return size(root);}
private int size(Node h){
if (h == null) return 0;
else return h.N;
}
public void put(Key key, Value val){
root = put(root,key,val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val){
if (h == null){
//新建结点都用红链接
return new Node(key, val, 1, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) h.left = put(h.left, key, val);//小于key,进入左子树
else if(cmp > 0) h.right = put(h.right, key, val);//大于key,进入右子树
else h.val = val;//已存在,则更新val
//处理右侧红链接
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
//处理连续红链接
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
//颜色转换
if (isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.right)+size(h.left)+1;
return h;
}
}
示例
4.3 删除
4.3.1 自顶向下的2-3-4树
2-3-4树中允许存在4-结点,它的插入算法和2-3数的删除算法类似,因此作为引导
- 插入: 沿着路径向下进行变换,始终保持当前结点非4-结点(这样树底才有空间插入新键),沿查找路径向上进行变换是为了将之前创建的4-结点配平
- 向下变换:
- 根结点是4-结点,分解为三个2-结点,树高加一
- 父结点为2-结点的4-结点,将中间结点上移构成3-结点,剩下拆分为两个2-结点
- 父结点为3-结点的4-结点,将中间结点上移构成4-结点,剩下拆分为两个2-结点
- 不会构建出出现父结点和子结点同时为4-结点的情况
- 树底部只可能为2-/3-结点,插入扩大一个即可
- 向上变换:即put()中的递归后rotate()处理
- 红黑树实现2-3-4插入:
- 4-结点由三个2-结点表示
- 向下时分解4-结点,进行颜色转换
- 向上时旋转配平4-结点
- 只需要将colorFlip()语句及其if语句放在null测试和比较操作之间,就可以实现上述算法
- 允许4-结点存在,即允许连续两个左红链接存在,所以语句提前在比较执行put()前,再下次put()时前在调整颜色(分解4-结点)--向下
- 两个方向rotate()依旧在put()后,则在向上过程中配平4-结点--向上
4.3.2 删除最小键
- 考虑:在树底部删除3-结点删除最小键容易实现,但若从2-结点删除一个结点,会留下一个空链接,破坏平衡性
- 因此:删除最小键时,沿着左链接向下变换,确保当前结点非2-结点(可能是3-结点或者临时4-结点)
- 根结点的两种可能:
- 根结点是2-结点且两个子结点也是2-结点:将三个结点合并为一个4-结点
- 否则需要保证根结点的左子结点非2-结点,必要时从其右兄弟结点取一个键
- 沿着左链接向下时:
if(!isRed(h.left) && !isRed(h.left.left))
- 若当前结点左子结点非2-结点(h.left或h.left.left中一个为红色,则h.left就在一个3-结点中),完成,继续左下深入
- 若当前结点左子结点是2-结点而亲兄弟非2-结点,将右子结点的兄弟结点中一个键移动到左子结点中
- 若当前结点左子结点和兄弟结点都是2-结点,将左子结点,父结点中的最小键,左子结点最近兄弟结点合并为一个4-结点,则父结点从3-变为2-或4-变为3-
- 最终:得到一个含有最小键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
//配平4-结点函数,只有第一句话不同,其余和put最后五句一致
private Node balance(Node h){
if (isRed(h.right)) h = rotateLeft(h);
if(!isRed(h.left) && isRed(h.right)) rotateLeft(h);
if(isRed(h.left) && isRed(h.left.left)) rotateRight(h);
if(isRed(h.left) && isRed(h.right)) flipColors(h);
h.N = size(h.right) + size(h.left)+1;
return h;
}
//删除时的颜色转换与插入时刚好相反
private void delFlipColors(Node h){
h.color = BLACK;
h.left.color = RED;
h.right.color = RED;
}
public void deleteMin(){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
deleteMin(root.left);
if(!isEmpty()) root.color = BLACK;//根结点始终为黑色
}
private Node deleteMin(Node h){
if (h.left == null) return null;//找到左链最底,返回null
if(!isRed(h.left) && !isRed(h.left.left))//h.left是2-结点
h = moveRedLeft(h);//借助兄弟结点
h.left = deleteMin(h.left);
return balance(h);
}
private Node moveRedLeft(Node h){
delFlipColors(h);//Min:默认形成4-结点
if (isRed(h.right.left)){//Min:当右兄弟非2-结点,借出一个键给左兄弟
h.right = rotateRight(h.right);
h = rotateLeft(h);
}
return h;
}
示例
4.3.3 删除最大键
- 删除最大键的思想和删除最小键一样
- 对根结点的处理:同上
- 沿着右链接向下时:
- 若当前结点的左子结点非2-结点,则左旋转左子结点,成为父结点,新的右子结点一定非2-结点,为后续删除创造条件
if(!isRed(h.left) && !isRed(h.left.left))
- 若当前结点右子结点非2-结点(h.right或h.right.left中一个为红色,则h.left就在一个3-结点中),完成,继续右下深入
- 若当前结点右子结点是2-结点而左兄弟非2-结点,将右子结点,父结点中的最大键,最近左兄弟结点合并为一个4-结点
- 若当前结点右子结点和兄弟结点都是2-结点,则将左子结点旋转,即移动一个键到右子结点
- 最终:得到一个含有最大键的3-结点或者4-结点,将其删除,在回头向上分解4-结点(递归)
//删除最大键
public void deleteMax(){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
root = deleteMax(root);
if (!isEmpty()) root.color = BLACK;
}
private Node deleteMax(Node h){
if (isRed(h.left)) h = rotateRight(h);//左侧非2-结点右旋转
if(h.right == null) return null;//找到右链底部,返回null
if (!isRed(h.right) && !isRed(h.right.left))
h = moveRedRight(h);//从左链借来键
h.right = deleteMax(h.right);
return balance(h);
}
private Node moveRedRight(Node h){
//delMin与delMax这两步含义不同
delFlipColors(h);//Max:默认右子结点变为非2-结点
if (!isRed(h.left.left))//Max:当左兄弟是2-结点,则形成4-结点
h = rotateRight(h);
return h;
}
示例
4.3.4 删除操作
- 删除和delMin/delMax都要保证当前结点非2-结点,若最终找到结点在底部(左链接/右链接),则直接删除,否则就用右子树最小结点键值与其他交换,再删除右子树最小键
public void delete(Key key){
if(!isRed(root.left) && !isRed(root.right))//根结点三个2-结点
root.color = RED;//为后续颜色变换准备
root = delete(root, key);
if (!isEmpty()) root.color = BLACK;
}
private Node delete(Node h, Key key){
if(key.compareTo(h.key) < 0){//cmp < 0,类比delMin
if(!isRed(h.left) && !isRed(h.left.left))
h = moveRedLeft(h);
h.left = delete(h.left, key);
}
else{//cmp >= 0,类比delMax
if(isRed(h.left)) h = rotateRight(h);
if(key.compareTo(h.key) == 0 && (h.right == null)) return null;//找到结点,且无右子树,直接删除
if(!isRed(h.right) && !isRed(h.right.left)) h = moveRedRight(h);
if(key.compareTo(h.key) == 0){//找到结点,且有后续结点,则用右子树最小结点键值替换父结点,再删去右子树最小结点
h.val = get(h.right, min(h.right).key);
h.key = min(h.right).key;
h.right = deleteMin(h.right);
}
else h.right = delete(h.right, key);
}
return balance(h);
}
示例
5. 红黑树性质
5.1 性能分析
- 大小为N的红黑树高度不超过2lgN
最坏情况是对应2-3树最左边路径全是3-结点而其余都为2-结点
- 大小为N的红黑树,根结点到任意结点的平均路径长度为~1.00lgN
- 红黑树中,以下操作在最坏情况下是对数级别的:
get(),put(),min(),max(),floor(),ceiling(),rank(),select(),deleteMin(),deleteMax(),delete(),range()
红黑树是第一个可以保证对数级别插入和查找的符号表实现
5.2 各种符号表实现性能总结
算法 最坏查找 最坏插入 最优查找 最坏插入 支持有序操作 顺序查询(无序链表) N N N/2 N 否 二分查找(有序数组) lgN N lgN N/2 是 BST N N 1.39lgN 1.39lgN 是 红黑树 2lgN 2lgN 1.00lgN 1.00lgN 是
算法3.5 基于拉链法的散列表
原目录：算法（第四版） / 算法合集
算法3.5 基于拉链法的散列表
- 概述:将大小为M的数组中每个元素指向一条链表,链表中每个结点存储了散列值为该元素索引的键值对
- 基本思想:选择足够大的M,使所有链表都尽可能短,且发生冲突的元素都在链表中
- 查找:
- 根据散列值找到对应链表
- 沿着链表找到对应键
实现
使用了一般的链式类型SequentialSearchST扩展成散列表
//拉链法
public class SeparateChainHashST<Key, Value> {
private int N;//键值对总数
private int M;//散列表大小
private SeparateSearchST<Key, Value>[] st;
public SeparateChainHashST(){
this(997);//默认使用997条链表
}
public SeparateChainHashST(int M){
this.M = M;
st = (SeparateSearchST<Key, Value>[]) new SeparateSearchST[M];
for (int i = 0; i < M; i++)
st[i] = new SeparateSearchST();//需要给对象数组元素创建实例
}
private int hash(Key key){ return (key.hashCode()&0x7fffffff)%M; }
public Value get(Key key){ return (Value)st[hash(key)].get(key); }
public void put(Key key, Value val){ st[hash(key)].put(key, val);}
}
算法分析
- 链表的平均长度永远为N/M
- 命题:在M个链表,N个键的散列表中,(均匀散列假设成立时)任意一条链表中键的数量均在N/M的常数因子范围内的概率无限趋向于1
- 性质:M个链表,N个键的散列表中,未命中查找和插入操作所需的比较次数为~N/M
散列表的大小
- 选择适当的数组大小M,既不会浪费大量内存,也不会因为链表过长而增加查找时间
有序性操作
- 散列的目的在于均匀分布键值,因此顺序信息无法保存,一切有序性操作(最大最小键,范围查找等)都需要线性级别时间开销,但在顺序不重要的符号表中,散列表是最快,最广泛使用的
算法3.6 基于线性探测的散列表
原目录：算法（第四版） / 算法合集
算法3.6 基于线性探测法的散列表
- 概述:另一种散列表用大小M的数组保存N个键值对,M>N,依靠数组的空位解决碰撞冲突,这种方法叫做开放地址散列表
- 线性探测法:碰撞发生时(某个散列值已经被占用),直接检查散列表下一位置,产生三种结果:
- 命中:该位置键和被查找键相同
- 未命中,键值为空
- 继续查找,该位置键和被查找键不同
- 核心思想:与其将内存用作链表,不如作为散列表的空元素
实现
键与值分别在两个数组中
public class LinearProbingHashST<Key, Value> {
private int N;//键值对总数
private int M;//散列表大小
private Key[] keys;//键
private Value[] vals;//值
public LinearProbingHashST(int M){
this.M = M;
keys = (Key[]) new Object[M];
vals = (Value[]) new Object[M];
}
private int hash(Key key){ return (key.hashCode()&0x7fffffff)%M;}
//可变长数组
private void resize(int cap){}
private boolean contains(Key key){
for (int i = hash(key); keys[i] != null; i = (i+1)%M){
if (keys[i].equals(key)) return true;
}
return false;
}
public Value get(Key key){
for (int i = hash(key); keys != null; i = (i+1)&M){
if (keys[i].equals(key)) return vals[i];
}
return null;
}
public void put(Key key, Value val){
if (N == M/2) resize(2*M);
for (int i = hash(key); keys[i] != null; i = (i+1)%M){//以键簇头开始,找到键簇末尾空元素
if (keys[i].equals(key)){ vals[i] = val;return; }//已存在,更新
keys[i] = key;
vals[i] = val;
N++;
}
}
public void delete(Key key){}
}
- 键和值分别在两个数组中,连续的键值叫做一簇,null为一簇的结束
- 一个新键的散列值是null,则保存在该位置
- 如果不是,则往后找到一个空位置
resize():变长函数
//可变长数组
private void resize(int cap){
LinearProbingHashST<Key, Value> t;
t = new LinearProbingHashST<>(cap);
for (int i = 0; i < M; i++)//读出所有非空键重新插入t
if (keys[i] != null)
put(keys[i], vals[i]);
keys = t.keys;
vals = t.vals;
}
- 开放地址散列表的N/M叫做散列表使用率,和拉链法意义完全不同,此时比值不被允许达到1(散列表满),因为散列表满会导致未命中的查找无限循环,需要动态调整使用率在1/8~1/2之间
delete():删除函数
public void delete(Key key){
if (!contains(key)) return;
int i = hash(key);
//找到待删键值对
while (!keys[i].equals(key)){
i = (i+1)%M;
}
keys[i] = null;
vals[i] = null;
i = (i+1)%M;
//避免丢失同键簇的元素,需要依次删除再put()
while (keys[i] != null){
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i+1)%M;
}
N--;
if (N > 0 && N == M/8) resize(M/2);
}
- 直接删除某个元素是错误的,会导致同一簇后面的元素无法再被访问,需要将被删除键右侧所有键值重新插入散列表
算法分析
- 键簇:短小的键簇才能保证较高的效率
- 命题:在大小M含有N=αM个键的线性探测散列表中,基于假设,命中和未命中查找所需探测次数分别为1/2(1+1/(1-α))和1/2(1+1/(1-α)²),当α为1/2时,分别为1.5次和2.5次,因此要动态调整大小
两种散列表对比
- 大小调整:
- 拉链法:调整不是必须的,只需要根据和(1+N/M)成正比选合适M
- 线性探测法:必须调整,否则可能无限循环
- 内存使用:
- 拉链法:为每个键值都分配了一小块内存
- 线性探测法: 整张表使用了两个很大的数组
算法4.1 深度优先搜索
原目录：算法（第四版） / 算法合集
4.1.1 走迷宫:Tremaux搜索
- 选择一条没有标记过(marked)的通道,在走过的路上铺一条绳子
- 标记所有第一次走过的路口和通道
- 当来到一个已经被标记过的路口,则回退到上个路口
- 回退到的路口无路可走时,继续回退
4.1.2 深度优先搜索DFS
- 描述:DFS是一种搜索连通图的递归算法,只需一个递归就可以遍历所有结点,当到达某个结点时
- 将它标记为已访问
- 继续递归访问它没有标记过的邻居结点
实现
public class DepthFirstSearch {
private boolean[] marked;//记录已标记结点
private int count;//连通结点个数
public DepthFirstSearch(Graph G, int s){
marked = new boolean[G.V()];
dfs(G, s);
}
private void dfs(Graph G, int v){
if (marked[v]) return;//若已被标记,则返回上一路口
marked[v] = true;
count++;
for (int w: G.adj(v)){
dfs(G, w);
}
}
public boolean marked(int w){
return marked[w];
}
public int count(){
return count;
}
}
算法分析
- DFS标记与顶点s相连通所有顶点的时间和∑deg(v)成正比:DFS中每条边都会被访问两次,且第二次总会发现已被访问过
4.1.4 寻找路径
- 问题:给定一幅图和一个起点s,问"s到给定的目的结点v之间是否有一条路径,如果有请找出",此类问题即为寻找路径
路径API:public class Paths
返回类型 方法 描述 Paths(Graph G, int s) 在G中找出所有起点s的路径 boolean hasPathTo(int v) 是否存在s到v的路径 Iterable pathTo(int v) s到v的路径,不存在返回null
实现
public class Paths {
private boolean[] marked;//该顶点上是否调用dfs()
private int[] edgeTo;//起点到上一顶点路径上的最后一个顶点
private final int s;//起点
public Paths(Graph G, int s){
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s);
}
//深度优先遍历(递归/隐式栈)
private void dfs(Graph G, int v){
marked[v] = true;
for (int w: G.adj(v)){
if (!marked[w]){
edgeTo[w] = v;//到w的上一个结点为v
dfs(G, w);
}
}
}
//是否有入度
private boolean hasPathTo(int v){ return marked[v]; }
//返回s到v的路径(Stack形式)
public Iterable<Integer> pathTo(int v){
if (!hasPathTo(v)) return null;//没有调用过dfs(),则v一定是孤立结点,直接返回null
Stack<Integer> path = new Stack<>();
for (int i = v; i != s; i = edgeTo[i])
path.push(i);//上一个结点压入栈中
path.push(s);//压入起点
return path;
}
}
- edgeTo[w] = v表示到w的上一个结点为v,即起点s到v的最后一条已知边为v-w
edgeTo[2] = 0;
edgeTo[1] = 2;
edgeTo[3] = 2;
edgeTo[5] = 3;
edgeTo[4] = 3;
- 最终路径Path由Stack/Bag实现
算法分析
- DFS标记起连通的所有顶点耗时和∑deg(v)成正比
- 使用DFS得到的从给定点s到任意点v的path所需时间和路径长度成正比
算法4.3 DFS找出连通分量
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class CC {
private boolean[] marked;
private int[] id;//已知边最后顶点
private int count;//连通分量数
public CC(Graph G) {
marked = new boolean[G.V()];
id = new int[G.V()];
for(int i = 0; i < G.V(); i++){
if (!marked[i]){
dfs(G,i);//深度搜索一个节点后,分量加一
count++;
}
}
}
private void dfs(Graph G, int v){
marked[v] = true;
id[v] = count;
for (int w:G.adj(v))
if (!marked[w])
dfs(G,w);
}
public boolean connected(int v, int w) { return id[v] == id[w];}
public int count(){ return count;}
public int id(int v){ return id[v];}
public static void main(String[] args){
Graph G = new Graph(new In(args[0]));
CC cc = new CC(G);
int M = cc.count();
StdOut.println(M + " components");
Bag<Integer>[] components;//Bag对象数组(邻接表)
components = (Bag<Integer>[]) new Bag[M];
for (int i = 0; i < M; i++)
components[i] = new Bag();//初始化分量数组
for (int v = 0; v < G.V(); v++)
components[cc.id(v)].add(v);//添加元素
for (int i = 0; i < M; i++){
for (int v: components[i])
StdOut.print(v + " ");
StdOut.println();
}
}
}
算法分析
- DFS的与处理时间和空间与V+E成正比且可以在常数时间内处理关于图的连通性查询:每个邻接表元素只会被检查一次
对比union-find
- DFS可以保证所需时间是常数,而UF不行,但实际中UF更快,后者不需要完整构造一幅图,可以在任何时候检查两点是否连通,但前者必须对图进行预处理
算法4.2 广度优先搜索
原目录：算法（第四版） / 算法合集
4.2.1 单点最短路径
- 问题:给定一幅图和一个起点s,问从s到给定顶点v是否存在一条路径?如果有,找出其中最短的一条
- 思路:要找到s到v的最短路径,从s开始,在所有的距离为1的点中找v,如果没有,则到距离为2的点中找v,如此反复
广度优先搜索(BFS)和深度优先搜索(DFS)
- DFS:选用递归(隐式栈),使用LIFO规则从有带搜索的通道中选择最晚遇到的那条往下走
- BFS:按照与起点的距离顺序来遍历所有顶点,使用(FIFO)队列实现,从有带搜索的通道中选择最早遇到的那条
实现
public class BreadthFirstPaths {
private boolean[] marked;//是否之前已有更短路径到达
private int[] edgeTo;//到达该结点已知路径上的最后顶点
private final int s;
public BreadthFirstPaths(Graph G, int s){
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G,s);
}
(队列)
public void bfs(Graph G, int s){
Queue<Integer> queue = new Queue<>();
marked[s] = true;
queue.enqueue(s);
while (! queue.isEmpty()){
int v = queue.dequeue();
for (int w: G.adj(v)){
if (!marked[w]){
edgeTo[w] = v;//保存已知路径最后一个顶点
marked[w] = true;//标记为已达点
queue.enqueue(w);//添加至队列
}
}
}
}
private boolean hasPathTo(int v){ return marked[v]; }
//返回s到v的最短路径
public Iterable<Integer> pathTo(int v){
if (!hasPathTo(v)) return null;
Stack<Integer> path = new Stack<>();
for (int i = v; i != s; i = edgeTo[i])
path.push(i);
path.push(v);
return path;
}
}
- 虽然和DFS的pathTo()实现方法一样但BFS会给出s到v的一段最短路径
算法分析
- 对于从s可达的任意顶点v,BFS都可以找到一条从s到v的最短路径
- BFS搜索时间在最坏情况下和V+E成正比
BFS和DFS对比
- 相同点:
- 搜索时都会先将起点存入数据结构中,然后重复一下操作指导数据结构被清空
- 取下一个顶点并标记
- 将v的所有相邻而又未被标记的顶点继续加入数据结构
- 不同点:
- DFS选取递归/隐式栈,每次将最晚一个加入的结点当作下一个顶点
- BFS选取队列,每次将最早一个加入的结点当作下一个顶点
算法4.4 有向图可达性
原目录：算法（第四版） / 算法合集
算法4.4 有向图可达性
- 单点可达性:给定G和起点s,问:是否存在一条从s到给定顶点v的有向路径
- 和Graph的DFS方法完全一致
- 多点可达性:是否存在一条从集合中任意顶点(顶点集sources)到给定顶点v的有向路径
有向图可达性API:public class DirectedDFS
返回类型 方法 描述 DirectedDFS(Digraph G, int s) 在G中找从s可达的所有结点 DirectedDFS(Digraph G, Iterable sources) G中找点集source可达的所有结点 boolean marked(int v) v是否可达
实现
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class DirectedDFS {
private boolean[] marked;//是否可达
private int count;//连通分量数字
public DirectedDFS(Digraph G, int s){
marked = new boolean[G.V()];
dfs(G, s);
}
//多点连通性,搜索给定点集可有向连通的点
public DirectedDFS(Digraph G, Iterable<Integer> sources){
for (int s: sources){
marked = new boolean[G.V()];
if (!marked(s)) dfs(G, s);
}
}
private void dfs(Digraph G, int v){
marked[v] = true;
count++;
for (int w: G.adj(v))
if (!marked(w))
dfs(G, w);
}
public int count(){ return count;}
private boolean marked(int v){ return marked[v];}
public static void main(String[] args){
Digraph G = new Digraph(new In(args[0]));
Bag<Integer> source = new Bag();
for (int i = 0; i < args.length; i++)
source.add(Integer.parseInt(args[i]));
DirectedDFS reachable = new DirectedDFS(G, source);
for (int i = 0; i < G.V(); i++)
if (reachable.marked(i)) StdOut.print(i + " ");
StdOut.println();
}
}
算法分析
- 命题:在有向图中,DFS标记由一个集合的顶点可达的所有顶点所需时间与被标记的所有顶点出度之和成正比
算法应用
- 垃圾回收算法:内存管理系统(如Java实现)标记-清楚的垃圾回收策略会为每个对象保留一个位做垃圾收集之用:周期性的运行一个DirectedDFS有向图可达性算法标记可达对象,清理未被标记的对象.
- 有向图的寻路
- 单点有向路径:即DFPath,只需用Digraph替换Graph
- 单点最短有向路径:即BFPath,同上
算法4.5 环,有向无环图,拓扑排序
原目录：算法（第四版） / 算法合集
4.5.1 算法:有向环寻找
调度问题
优先级限制下的调度问题: 给定一组任务,以及一组任务完成先后次序的优先级限制,如何在满足限制的情况下完成所有任务
建立模型:建立有向图,任务作为结点,有向边对于优先级顺序
问题转化:拓扑排序,给定有向图,将所有顶点排序,使得所有有向边均从排在前的元素指向排在后的元素
有向图中的环
- 如果一个优先级限制问题中存在环,问题无解(无论从哪个开始都不满足优先级顺序)
- 有向环检测:确定图是有向无环图(DAG)才能解决优先级问题
- 思路:使用DFS算法时,递归过程作为隐式栈表示当前正遍历的路径,一旦在找到v->w后发现w已经在栈中,说明是一个环
有向环API:public class DirectedCycle
返回类型 方法 描述 DirectedCycle(Digraph G) 构造函数 boolean hasCycle() G是否含有环 Iterable cycle() 环中所有顶点
实现
public class DirectedCycle{
private boolean[] marked;
private int[] edgeTo;
private Stack<Integer> cycle;//有向环中所有结点
private boolean[] onStack;//栈,当为true表示当前隐式栈中已经有结点w
public DirectedCycle(Digraph G){
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
onStack = new boolean[G.V()];
for(int v = 0; v < G.V(); v++){
if(!marked[v]) dfs(G,v);
}
}
private void dfs(Digraph G, int v){
onStack[v] = true;
marked[v] = true;
for(int w: G.adj(v)){
if(this.hasCycle()) return;//只要找到一个环即可
else if(!marked[w]){
edgeTo[w] = v;
dfs(G,w);
}
else if(onStack[w]){
//条件1,marked[w]==true表示该结点已被访问
//条件2,onStack[w]==true表示是当前隐式栈中
//只满足前者可能是结点w作为两条路的终点被指向,但此时不构成环
cycle = new Stack<Integer>();
for(int x = v; x != w; x = edgeTo[w])
cycle.push(x);//后访问的点先压入栈中
cycle.push(w);
cycle.push(v);
}
}
onStack[v] = false;//调用栈结束后onStack[v]=false即表示出栈
}
public boolean hasCycle(){ return cycle != null;}
public Iterable<Integer> cycle(){ return cycle;}
}
- 在执行dfs(G,v)时将onStack[v]设为true,表示进入该路径,调用结束时设回false,只有当前路径上marked[w]和onStack[w]同时满足才构成有向环
示例
4.5.2 算法:三种不同的顶点排序
思考:既然DFS只会沿每条路径到头访问每个结点一次,那把dfs()的参数结点保存在某个数据结构,遍历该数据结构就能访问所有结点
模型:优先级限制的调度问题等价于计算有向无环图中所有顶点的拓扑顺序,DFS沿着有向边访问结点就是按照优先级访问
问题转化:综上,只需要按照某个顺序保存参数结点就可以得到所有顶点的拓扑顺序
结点保存顺序
- pre()前序:dfs()前将顶点加入队列
- post()后序:dfs()后将顶点加入队列
- reversePost()逆后序:dfs()后将顶点压入栈
示例
- pre:0-5-4-1-6-9-11-12-10-2-3-8-7
- post:4-5-1-12-11-10-9-6-0-3-2-7-8
- reversePost:8-7-2-3-0-6-9-10-11-12-1-5-4
实现
public class DepthFirstOrder{
private boolean marked[];
private Queue<Integer> pre;//前序
private Queue<Integer> post;//后序
private Stack<Integer> reversePost;//逆后序
public DepthFirstOrder(Digraph G){
marked = new boolean[G.V()];
pre = new Queue<>();
post = new Queue<>();
reversePost = new Stack<>();
for(int v = 0; v < G.V(); v++)
if(!marked[v]) dfs(G,v);
}
private void dfs(Digraph G, int v){
pre.enqueue(v);
for(int w: G.adj(v))
if(!marked[w]) dfs(G,w);
post.enqueue(v);
reversePost.push(v);
}
public Iterable<Integer> pre(){ return pre;}
public Iterable<Integer> post(){ return post;}
public Iterable<Integer> reversePost(){ return reversePost;}
}
- 结论:拓扑排序是所有顶点的逆后序reversePost
证明:有向图中优先级v->w反映在函数中即为dfs(G,v){dfs(G,w)}的递归关系,在调用dfs(v)时只可能有下列三种情况:
- dfs(w)已被调用返回
- dfs(w)将被调用,且先于dfs(v)返回
- dfs(w)已被调用,但未返回
但最后一种情况不可能在无环有向图中出现,只有环才能满足条件.
因此,v->w的优先级限制的v必须在w前被读出,逆后序总是先压入w,后压入v,读取时即v->w的拓扑顺序
算法4.5 拓扑排序
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Topological{
private Iterable<Integer> order;//逆后序
public Topological(Digraph G){
DirectedCycle cycleFinder = new DirectedCycle(G);//有向环查找器
if(!cycleFinder.hasCycle()){
DepthFirstOrder dfs = new DepthFirstOrder(G);
order = dfs.reversePost();//逆后序
}
}
public Iterable<Integer> order(){ return order;}
public boolean isDAG(){ return order != null; }
public static void main(String[] args){
Digraph G = new Digraph(new In(args[0]));
Topological top = new Topological(G);
for(int v:top.order()) StdOut.println(v);//依次出栈打印即为拓扑排序
}
}
算法分析
- 命题:使用DFS对DAG进行拓扑排序的时间和V+E成正比
证明:第一遍DFS保证不存在有向环,第二遍DFS产生逆后序排列,每次DFS时访问了每个顶点和所有边
- 最终的Topo顺序和构造有向图时结点插入顺序有关,同一幅DAG的Topo序列可能不同,但始终满足优先级的要求,如上图:
- DAG:(0,5)(5,4)(0,1)(0,6)(6,4)(6,9)(9,10)(9,11)(9,12)(11,12)(8,7)(7,6)(2,0)(2,3)(3,5)
- Topo:8-7-2-3-0-5-1-6-4-9-10-11-12
- DAG:(2,3)(0,6)(0,1)(2,0)(11,12)(9,12)(9,10)(9,11)(3,5)(8,7)(5,4)(0,5)(6,4)(6,9)(7,6)
- Topo:8-7-2-3-0-6-9-10-11-12-1-5-4
算法4.6 SSC的Kosaraju算法
原目录：算法（第四版） / 算法合集
4.6.1 有向图的强连通性
- 无向图的连通性:v-w,则v和w互相连通
- 有向图的可达性:v->w,则从v是单向可达w的
- 强连通:v<->w,即顶点v和w相互可达,此时v和w是强连通的
- 有向图的强连通性:当有向图中任意两个顶点互相可达,则有向图是强连通的
4.6.1.1 判断两个顶点是否强连通
- 当且仅当两个顶点在一个有向环中
4.6.1.2 强连通分量(SCC:Strong Connected Component)
- 强连通性是一种等价关系:
- 自反性:v和自己强连通
- 对称性:v和w强连通,则w和v强连通
- 可传递性:v和w强连通,则w和v强连通
- 由离散数学知识,等价关系可将点集V分成等价类V1,V2...,这些子集叫做强连通分量,其定义基于顶点而非边
- 一个V个顶点的有向图中有1~V个SCC
- 一个强连通图,只有一个SCC
- 一个DAG (Directed Acyclic Graph)含有V个SCC
4.6.2 强连通分量API
public class SCC
返回类型 方法 描述 SSC(Digraph G) boolean stronglyConnected(int v, int w) v和w是否强连通 int count() 图中SCC个数 int id(int v) v所在SCC的标识符
算法4.6 Kosaraju算法
思路
与CC只有几处语句不同
给定有向图G,求出其反向图GR
使用DepthFirstOrder计算GR逆后序
在原图G中按照GR逆后序访问所有未标记结点
在构造函数中,使用id[]和count和CC一样标记同一个连通分量中的结点
实现
public class KosarajuSCC {
private boolean marked[];//已访问结点
private int id[];//SCC标识符
private int count;//SCC个数
public KosarajuSCC(Digraph G){
marked = new boolean[G.V()];
id = new int[G.V()];
//G反向图的逆后序
Iterable<Integer> order = new DepthFirstOrder(G.reverse()).reversePost();
for (int s: order){
if (!marked[s]){
dfs(G,s);
count++;
}
}
}
private void dfs(Digraph G, int v){
marked[v] = true;
id[v] = count;
for (int w:G.adj(v))
if (!marked[w]) dfs(G,w);
}
public boolean stronglyConnected(int w, int v){
return id[w] == id[v];
}
public int id(int v){ return id[v];}
public int count(){ return count;}
}
算法分析
- 命题:使用DFS查找GR,并根据相反图逆后序访问原图,构造函数中每次递归标记为id[i]的顶点都在一个SSC中
- 命题:Kosaraju算法预处理所需的时间和空间与V+E成正比且支持常数级别的有向图强连通性查询
证明:构造GR,reverPost()(DFS一次),访问原图(DFS一次),每一步都和V+E成正比
4.6.3 顶点对可达性与传递闭包
问题:顶点对的可达性:给定图问"是否存在一条从v到w的路径"(非单点/多点可达性或者单点有向路径问题,而是希望建立类似CC类,经过预处理构造后通过connected(v,w)实现常数级别的判断而无需每次重新构造路径)
无向图:即连通性问题,使用基于DFS的CC算法,经过线性级别的预处理时间记录所有连通分量,即可使用connected(v,w)实现常数级别的判断
有向图:不同于强连通分量SCC问题,这时的可达性为单向的,为了实现预处理后常数时间的判断,需要构造传递闭包TransitiveClosure
- 传递闭包:有向图G的传递闭包由相同顶点构成另一幅图G',当G'中存在v->w时,当且仅当G中v到w是可达的(G中v到w可达但无直接边,就在G'构造边v->w)
- 对图构造传递闭包即离散数学中图的可达性矩阵
顶点对可达性API
public class TransitiveClosure
返回类型 方法 描述 TransitiveClosure(Digraph G) 预处理构造 boolean reachable(int v, int w) w是否从v可达
实现
public class TransitiveClosure {
private DirectedDFS[] all;//传递闭包/可达性为矩阵
TransitiveClosure(Digraph G){
all = new DirectedDFS[G.V()];
for (int v = 0; v < G.V(); v++)//构建矩阵的每一行
all[v] = new DirectedDFS(G, v);
}
boolean reachable(int v, int w){
return all[v].marked(w);
}
}
算法4.7 MST的Prim算法
原目录：算法（第四版） / 算法合集
最小生成树MST API
public class MST
返回类型 方法 描述 MST(EdgeWeightedGraph G) 构造函数 Iterable edges() MST所有边 double weight() MST权重
Prim算法
- 描述:每一步为树添加一个边.开始树只有一个顶点,向其中添加V-1条边,每次从连接树中顶点和树补的边中选择权重最小的边
- 命题:Prim算法可以得到任意加权连通图的最小生成树
证明:即切分定理
- 数据结构:
- 顶点:使用boolean marked[],当顶点v在树中,marked[v]==true
- 边:Queue mst,保存MST中的边
- 横切边:使用优先队列MinPQ根据权重比较所有边
- 边的失效:当marked[v]&&marked[w]时,这样的边已经非横切边,即失效
实现1.延时实现
- 延时实现:无效边留在优先队列pq当中,delMin()时判断,跳过无效边
- 注意:LazyPrimMST的pq非即时删除无效边,则运行中pq的元素数会超过G.V(),因此MinPQ需要resize()
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class LazyPrimMST {
private boolean[] marked;//树中顶点
private Queue<Edge> mst;//树中边
private MinPQ<Edge> pq;//横切边(含无效边)
public LazyPrimMST(EdgeWeightedGraph G){
marked = new boolean[G.V()];
mst = new Queue<>();
pq = new MinPQ<>(G.V());
visit(G,0);
while (!pq.isEmpty()){
Edge e = pq.delMin();//最小权边(可能无效)
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) continue;
mst.enqueue(e);
if (!marked[w]) visit(G,w);//将v或w加入树中(另一个已经在树中)
if (!marked[v]) visit(G,v);
}
}
//标记入树函数
private void visit(EdgeWeightedGraph G, int v){
marked[v] = true;
for (Edge e: G.adj(v))
if (!marked[e.other(v)]) pq.insert(e);
}
public Iterable<Edge> edges(){ return mst;}
public static void main(String[] args){
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
LazyPrimMST mst = new LazyPrimMST(G);
for (Edge e:mst.edges())
StdOut.println(e);
}
}
算法分析
- 命题:LazyPrim计算连通加权无向图G(V,E)的最小生成树所需空间和E成正比,时间和ElogE(最坏)成正比
证明:优先队列的insert()和delMin()中的比较是主要考虑部分.优先队列中E条边,即空间上限,最坏情况下,insert()为~lgE,delMin()为2lgE,因为最多只能插入E条边,删除E次最小元素.则最坏为ElogE(优先队列)
实现2.即时实现
- 即时实现:在pq中实时的删去无效边,只在pq中保存每个非树顶点w的一条边:即已知将其与树中点连接的最小权重边
- PrimMST使用索引优先队列,edgeTo[]和distTo[],具有以下性质
- marked[i],i在树中
- pq为索引优先队列,delMin()返回indexOfMin,即返回最小横切边关联的结点
- edgeTo[v]是v与树相连的权最小边,distTo[v]即权值
public class PrimMST {
private Edge[] edgeTo;//距树最近(最小权)边
private double[] distTo;//最小权
private boolean[] marked;//树中点
private IndexMinPQ<Double> pq;//有效横切边
public PrimMST(EdgeWeightedGraph G){
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;//权值都初始为正无穷
pq = new IndexMinPQ<>(G.V());
distTo[0] = 0.0;//顶点0和0.0初始化起点
pq.insert(0,0.0);
while (!pq.isEmpty())
visit(G,pq.delMin());
}
private void visit(EdgeWeightedGraph G, int v){
marked[v] = true;
for (Edge e:G.adj(v)){
int w = e.other(v);
if (marked[w]) continue;//忽略失效边v-w
if(e.weight() < distTo[w]){//发现更短有效路径e
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)) pq.change(w, distTo[w]);//非首次加入树
else pq.insert(w,distTo[w]);//首次加入树
}
}
}
public Iterable<Edge> edges(){
Bag<Edge> mst = new Bag<>();
for (int v = 1; v < edgeTo.length; v++)
mst.add(edgeTo[v]);
return mst;
}
}
算法分析
- 命题:Prim算法计算连通加权无向图G(V,E)的最小生成树所需空间和V成正比,时间和ElogV(最坏)成正比
证明:pq中顶点数最多为V,使用三个索引数组,则空间上限和V成正比.已知基于堆的索引优先队列的操作增长数量级是logV,则相加总时间和ElogV成正比
图示
算法4.8 MST的Kruskal算法
原目录：算法（第四版） / 算法合集
算法4.8 MST的Kruskal算法
- 与Prim方法对比:Prim算法中树的生长都是通过连接一个新的顶点,而Kruskal算法中不同顶点可以先连成较小树,最后不同树之间合并
- 描述:Kruskal算法每次将最小边加入MST中,新加入的边不会和已有边成环,知道树中有V-1条边
- 命题:Kruskal算法可以得到任意加权连通图的最小生成树
证明:由定义,当前加入边不会和MST中边构成环,则为跨越树和树补两界的且按权重顺序选择的边,必然为权重最小横切边,则运用贪心算法,连续选边可得到完整MST
- 数据结构:
- 顶点情况:并查集UF,当uf.connected(v,w)则v-w失效
- MST边:Queue mst,保存MST中的边
- 横切边:使用优先队列MinPQ根据权重比较所有边
实现
import edu.princeton.cs.algs4.UF;
public class Kruskal {
private Queue<Edge> mst;
public Kruskal(EdgeWeightedGraph G){
mst = new Queue<>();
MinPQ<Edge> pq = new MinPQ<>(G.V());
for (Edge e: G.edges()) pq.insert(e);//开始在pq中加入所有边
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V()-1){
Edge e = pq.delMin();//最小权边
int v = e.either(), w = e.other(v);
if(uf.connected(v,w)) continue;//失效边
uf.union(v,w);
mst.enqueue(e);
}
}
public Iterable<Edge> edges(){ return mst;}
}
算法分析
- Kruskal算法计算连通加权无向图G(V,E)的最小生成树所需空间和E成正比,时间和ElogE(最坏)成正比
证明:算法开销在于使用所有边初始化MinPQ,最多E次比较,MinPQ中最多E条边,为最大空间,每次操作最多需要2lgE次比较,合计ElogE,其中UF的最多E次connected()和V次union()可忽略
- Kruskal和Prim都不适用于有向图
算法4.9 SP的Dijkstra算法
原目录：算法（第四版） / 算法合集
算法描述
- 描述1:初始化distTo[s]为0,其余distTo[]为∞,之后逐个将distTo[]中最小非树结点放松,直到所有结点都在树中或所有非树结点distTo[]为∞(s不可达)
- 描述2:初始化后从s开始放松:将与s间隔一条边的顶点加入队列中,按权值小到大对所有间隔一条边结点都进行放松,然后是间隔两条边...结束条件同上
数据结构
- distTo[]:标记s->w的最短距离
- edgeTo[]:标记s->w最短路径的最后一条边
- IndexMinPQ:以"w"为索引,distTo[w]为键的索引优先队列,delMin()保证可以删除并返回路径最短的顶点
算法证明
证明:若v是起点可达的,v被放松时一定满足distTo[w]<=distTo[v]+e.weight(),放松v前的结点时,delMin()保证了distTo[v]一定是最小的,不会再改变,则distTo[w]只会变小,如此对每个顶点distTo[]都是最小的,且满足distTo[w]<=distTo[v]+e.weight(),根据最短路径最优性条件(书P420),则得到的distTo[]都是最短路径长度
实现
import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.Stack;
public class DijkstraSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
private IndexMinPQ<Double> pq;
public DijkstraSP(EdgeWeightedDigraph G, int s){
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
pq = new IndexMinPQ<>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
pq.insert(s, 0.0);
while (!pq.isEmpty()){
relax(G, pq.delMin());
}
}
private void relax(EdgeWeightedDigraph G, int v){
for (DirectedEdge e: G.adj(v)){
int w = e.to();
if (distTo[w] > distTo[v]+e.weight()){
distTo[w] = distTo[v]+e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.change(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
public double distTo(int v){ return distTo[v];}//s->v的距离
public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY;}
public Iterable<DirectedEdge> pathTo(int v){
Stack<DirectedEdge> stack = new Stack<>();
for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
stack.push(e);
return stack;//后根入栈
}
}
示例
算法分析
- G(V,E)中使用Dijkstra算法构建SPT所需空间和V成正比,时间和ElogE成正比(最坏)
证明:与使用索引优先队列的Prim一致
任意两顶点间最短路径
- 与算法4.6中建立传递闭包获得顶点对可达性类似,通过建立DijkstraSP[]判读顶点s,t直接知否有最短路径,已经最短路径大小
public class DijkstraAllPairsSP {
private DijkstraSP[] all;
public DijkstraAllPairsSP(EdgeWeightedDigraph G){
all = new DijkstraSP[G.V()];
for (int v = 0; v < G.V(); v++){
all[v] = new DijkstraSP(G, v);
}
}
//返回s->t最短路径
Iterable<DirectedEdge> path(int s, int t){ return all[s].pathTo(t);}
//返回s->t最短路径大小
double dist(int s, int t){ return all[s].distTo(t); }
}
算法4.10 无环加权有向图的SP算法
原目录：算法（第四版） / 算法合集
算法4.10 无环加权有向图的SP算法
算法描述
- Dijkstra算法中使用pq.delMin()保证了每个结点v只会放松一次,但操作pq开销较大,在无环加权有向图中,拓扑排序也能保证每个顶点只会放松一次
实现
public class AcyclicSP {
private DirectedEdge[] edgeTo;
private double[] distTo;
public AcyclicSP(EdgeWeightedDigraph G, int s){
edgeTo = new DirectedEdge[G.V()];
distTo = new double[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
Topological top = new Topological(G);//根据DAG建立拓扑排序
for (int v:top.order()) relax(G,v);
}
private void relax(EdgeWeightedDigraph G, int v){
for (DirectedEdge e: G.adj(v)){
int w = e.to();
if (distTo[w] > distTo[v]+e.weight()){
distTo[w] = distTo[v]+e.weight();
edgeTo[w] = e;
}
}
}
public double distTo(int v){}//s->v的距离
public boolean hasPathTo(int v){}
public Iterable<DirectedEdge> pathTo(int v){}
}
算法分析
- Topo顺序在E+V成正比时间内生成,则解决SP问题也与次成正比
- Topo顺序与边的权重正负无关,则可以解决负权重的最短路径问题
无环加权有向图的最长路径LP算法
算法描述
- 将图中G的边权重取相反数,求得最短路径即为最长路径
实现
可以不取相反数,采用等价但更简单的方式
- distTo[]都初始化为NEGATIVE_INFINITY
- >变为<,distTo[w] < distTo[v]+e.weight()时放松顶点.
-1.8 < -2.0 + 0.3时将distTo[w]增大为-1.7,即v->w比原来的edgeTo[w]权重大,LP问题中distTo[w]只会变大,与SP问题恰好相反
算法分析
- 同算法4.10,都与E+V成正比
并行任务调度问题
- 优先级限定的任务调度:只考虑一件任务发生的前提任务,最终产生Topo排序
- 优先级限定+并行调度:在满足优先级的情况下,尽可能同时完成无优先级冲突的任务,从而在最短时间内结束
- 思考:尽早安排每一个任务
- 建模:关键路径:等价于加权有向无环图的最长路径问题:Topo顺序保证了任务的先来后到,distTo[]理解为timeToDo[],只能增大或不变(实现中weight=0.0时,表示可并行处理,时间不计),因为不可能Topo排序中后面的任务先于前面的任务完成.
- 正确性证明: 把根据Topo顺序放松结点的最长路径理解为满足优先级限定下一项一项完成任务,但优先级限定边的权值为0即忽略了可并行任务的用时,综上关键路径即完整任务的最优选择
示例
实现:CPM类
- 构造加权DAG,起点s,终点t,其中一个任务对应一个起始点v.start,一个完成点v.end,N个任务,则G(2N+2,E),对于有先后限定的任务v->w,addEdge(v.end,w.start,0.0),对每个任务的自身addEdge(v.start,v.end,time)
- 每个任务的开始时间即为起点s到v.start点的dist
算法4.11 一般加权有向图的BellmanFordSP算法
原目录：算法（第四版） / 算法合集
背景
- 问题:相对最后期限限制的并行任务调度:算法4.10中,优先级限定的并行任务处理转化为加权有向无环图副本(权重都取相反数)的最短路径/原图的最长路径问题,但现在若限定了两个任务间的期限限制
- 建模:此时问题转换为一个可能存在环和负权重边的加权有向图最长路径/副本最短路径问题:v必须在w启动后d时间开始,则添加v->w,权重为-d的边
- 如2必须在4开始后12个单位时间开始,则2的开始点->4的开始点产生一条权重-12的边
- 正确性证明:Topo顺序放松保证了优先级限制,v->w的负权值在放松v时表现为(distTo[])timeToDo[w]<timeToDo[v]-d进一步d<timeToDo[v]-timeToDo[w]即相对期限
准备:关于一般加权有向图的最短路径问题
对比
- 权值都非负:重点在找寻近路
- 负权重:重点在为了经过负权重道路,甚至绕弯
- 可知算法的本质不在于找寻近路
常见误区
- 找到最小负权值-d,给每条边加上|-d|,产生一个无负权图,从中找最短路径
错误:产生的新图最短路径和原图无关,间上述对比
- 对Dijkstra算法修改
错误:Dijkstra算法的前提在于distTo[w]只会变大,但现在前提不成立,算法不成立
负权重的环
- 负权重环是一个还上边的权重和为负的环
- 当且仅当s到v的有向路径任何点不在负权重环内,s到v的最短路径才有意义
证明:若存在负权重环,则一直绕着环就可以使得路径无限变短
问题解决的前提
- s不可达的顶点,distTo[]设为+∞
- s到可达点路径上属于负权重环的顶点,distTo[]设为-∞
- 对其余顶点,计算最短路径
- 因此,在一般有向图中监测负权重环,在其不可达时解决最短路径问题
算法4.11 基于队列的Bellman-Ford算法
- Bellman-Ford算法:任意含有V顶点的加权有向图限定起点s,从s无法达任何负权重环:将distTo[s]初始化为0,其余为+∞,以任意顺序放松有向图所有边,重复V轮
证明:归纳法,假设进行Vi轮
i=0,1显然成立
设i时成立
当进行i+1轮放松时,distTo[v]i+1=distTo[v]i+e.weight(),不会更大,因为第i轮放松保证了最短路径;不会更小,它本身就是最短路径
改进:基于队列的Bellman-Ford算法
- 每一轮放松时只有上一轮distTo[]变化的顶点出边才会对其他distTo[]有影响,因此选用队列保存这样的顶点再进行放松
数据结构
- queue:保存上一轮distTo[w]变化的w
- boolean[] onQ:指示顶点是否已经在队列中,防止重复入队
relax()
private void relax(EdgeWeightedDigraph G, int v){
for (DirectedEdge e: G.adj(v)){
int w = e.to();
if (distTo[w] > distTo[v]+e.weight()){
distTo[w] = distTo[v]+e.weight();
edgeTo[w] = e;
if (!onQ[w]){
queue.enqueue(w);
onQ[w] = true;
}
}
//每次放松完一个顶点后查找是否到达一个负权重环
if (cost++ % G.V() == 0)
findNegativeCycle();
}
}
实现
public class BellmanFordSP {
private double[] distTo;
private DirectedEdge[] edgeTo;
private boolean[] onQ;//顶点是否在队列中
private Queue<Integer> queue;//正被放松的顶点
private int cost;//relax()调用次数
private Iterable<DirectedEdge> cycle;//edgeTo[]中是否有负权重环
public BellmanFordSP(EdgeWeightedDigraph G, int s){
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
onQ = new boolean[G.V()];
queue = new Queue<>();
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
onQ[s] = true;
while (!queue.isEmpty() && !hasNegativeCycle()){
int v = queue.dequeue();
onQ[v] = false;
relax(G, v);
}
}
private void relax(EdgeWeightedDigraph G, int v){}
public double distTo(int v){}
public boolean hasPathTo(int v){}
public Iterable<DirectedEdge> pathTo(int v){}
private void findNegativeCycle(){ }
private boolean hasNegativeCycle(){ }
public Iterable<Edge> negativeCycle(){ }
}
算法分析
- V个顶点的加权有向图给定起点s,最坏情况时间和EV成正比,空间和V成正比
证明:每一轮放松E条边,共V轮
负权重环的监测
- 参考4.2节有向环寻找类DirectedCycle构造EdgeWeightedDirectedCycle
private void findNegativeCycle(){
int V = edgeTo.length;
EdgeWeightedDigraph spt;
spt = new EdgeWeightedDigraph(V);
for (int v = 0; v < V; v++){
if (edgeTo[v] != null)
spt.addEdge(edgeTo[v]);
}
EdgeWeightedDirectedCycle cf;
cf = new EdgeWeightedDirectedCycle(spt);
cycle = cf.cycle();
}
private boolean hasNegativeCycle(){ return cycle!=null;}
public Iterable<DirectedEdge> negativeCycle(){ return cycle;}
套汇问题
- 背景:给定一个sxt货币兑换图,(s,t)处数字即为1单位货币s可兑换多少货币t
- 问题:表格等价于加权有向图,顶点:货币,边和权重:货币对以及汇率,若s->t权重x,t->u权重y,则s->t->u即1单位货币s可兑换xy个货币t,但当u->s权重z且xyz>1时,表面s->t->u->s可以用1单位s换取大于1单位s,套汇即以钱生钱
- 建模:套汇问题即有向加权图的负权重环检测问题
- 证明:将汇率取对数后取反,如-ln(0.74),这样汇率之积xyz对应-ln(x)-ln(y)-ln(z)之和,xyz>1对应-ln(x)-ln(y)-ln(z)<0,即负权重环代表一种套汇机会
算法5.1 低位优先字符串排序
原目录：算法（第四版） / 算法合集
算法描述
- 字符串长度为W,从右向左对每个字符使用键索引计数法将所有字符串排序W遍,基数排序
实现
public class 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--){
int[] count = new int[R+1];
for (int i = 0; i < N; i++)//统计频度
count[a[i].charAt(d)+1]++;
for (int r = 0; r < R; r++)//频度转化为索引
count[r+1] += count[r];
for (int i = 0; i < N; i++)//排序
aux[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)//回写
a[i] = aux[i];
}
}
}
算法分析
- 基于R个字符字母表的N个长W字符串为键的元素,LSD需要访问7WN+3WR次数组,额外空间和N+R成正比
证明:W轮键索引计数:初始化数组:N+W(R+1),循环:W(2N+2R+3N+2N),空间上由aux[N]和count[R+1]可得
- LSD算法是稳定的
证明:对于每一轮索引计数分别是稳定的,递推至W轮始终是稳定的
算法5.2 高位优先字符串排序
原目录：算法（第四版） / 算法合集
算法描述
- 对于不等长字符串,应该考虑从左到右遍历字符
高位优先字符串排序中count[]的意义
实现
import edu.princeton.cs.algs4.Insertion;
public class MSD {
private static int R = 256;//基数
private static final int M = 15;//小数组插入排序的阈值
private static String[] aux;//辅助数组
private static int charAt(String s, int d){
if (d < s.length()) return s.charAt(d);else return -1;
}
public static void sort(String[] a){
int N = a.length;
aux = new String[R+1];
sort(a,0, N-1, 0);
}
private static boolean less(String[] a, int v, int w, int d){
return a[v].charAt(d) < a[v].charAt(d);
}
private static void sort(String[] a, int lo, int hi, int d){
if (hi <= lo + M){//小数组,插入排序
Insertion(a, lo, hi, d);
return;
}
int [] count = new int[R+2];
for (int i = lo; i <= hi; i++)//计算频度
count[charAt(a[i],d) + 2]++;
for (int r = 0; r < R; r++)//转换为索引
count[r+1] += count[r];
for (int i = lo; i <= hi; i++)//数据分类
aux[count[charAt(a[i], d)+1]++] = a[i];
for (int i = lo; i <= hi; i++)//回写
a[i] = aux[i];
//递归的以每个字符为键进行排序
for (int r = 0; r < R; r++)
sort(a, lo+count[r], lo+count[r+1]-1, d+1);
}
}
- 首字母排序以及整体递归情况
算法弊端
- 小数组问题:随着递归深入,最终每个字符串都会遇到hi==lo即大小为1的子数组,若不进行处理:
- 每次count[]都需要初始化为0
- 还需进行R次索引转换(无意义)
因此需要设置阈值M作为进行小数组插入排序的门槛,且为了避免检查已知相同的字符所带来的的成本
- 使用假设前d个字符均相同的插入排序
private static boolean less(String v, String w, int d){
return v.substring(d).compareTo(w.substring(d)) < 0;
}
private static void exch(String[] a, int v, int w){
String temp = a[v];
a[v] = a[w];
a[w] = temp;
}
//假设前d个字符相同的插入排序
private static void Insertion(String[] a, int lo, int hi, int d){
for(int i = lo; i <= hi; i++){
for (int j = i; j > lo && less(a[j],a[j-1],d); j--)
exch(a,j,j-1);
}
}
- 等值键:如上图,等值键的所有字符都会被检查,开销不小
- 额外空间:MSD使用了两个辅助数组aux[]和count[],aux[]大小为N且在递归外创建,但每层递归都会创建count[R+2],这部分空间直到递归结束才会释放
算法分析
- MSD算法中字符串的顺序不重要,每个字符串值的情况决定了开销
- 随机字符串:亚线性
- 非随机且有重复:接近线性时间
- 最坏情况(N个完全相同字符串):线性时间
- 命题:对基于R个字符的字母表的N个字符串排序,MSD平均需要检查NlogRN个字符
- 时间:对基于R个字符的字母表的N个字符串排序,MSD访问数组的次数在8N+3R到~7wN+3wR之间,w为字符平均长度
证明:最好情况,首字母全不不同,只需一遍就能排好序,最坏情况下和LSD类似
- 空间:对基于R个字符的字母表的N个字符串排序,MSD最坏时需要空间~Rwmax+N
证明:aux[N]在递归外创建,count[R+2]每层递归创建一个,递归最深wmax层
- 根据3,当小数组处理选择M时,应R与M²成正比
证明:当M作阈值,可分为N/M组,插入排序需要比较(M²/4*N/M=MN/4)次,而MSD会访问数组NR/M次,以比较换访问,当MN/4<NR/M,可得R>M²/4
算法5.3 三项字符串快排
原目录：算法（第四版） / 算法合集
算法描述
- 普通MSD算法每层递归会创建count[R+2],其中大部分都是空数组.而三项切分字符串快排,根据键的首字母v,切分成首字符小于v,等于v,大于v三部分,仅在首字符等于v的子数组中对下一个字符再次三向切分,其余两部分继续对首字符三向切分
实现
public class Quick3string {
private static int charAt(String s, int d){
if (d < s.length()) return s.charAt(d);
else return -1;
}
public static void sort(String[] a){
sort(a, 0, a.length-1, 0);
}
private static void exch(String[] a, int v, int w){
String temp = a[v];
a[v] = a[w];
a[w] = temp;
}
private static void sort(String[] a, int lo, int hi, int d){
if (lo >= hi) return;
int lt = lo, gt = hi;
int v = charAt(a[lo], d);//枢轴
int i = lo + 1;
while (i <= gt){
int t = charAt(a[i], d);
if (t > v) exch(a, lt++, i++);
else if (t < v) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt-1, d);
if (v > 0) sort(a, lt, gt, d+1);//空子数组,不进行递归
sort(a, gt+1, hi, d);
}
}
示例
算法分析
- 当字符串很长但长度相同,且前面大部分字符相同时
- 标准快排:~w2NlnN
- 三向切分: wN+2NlnN
证明:三向切分中发现相同开头字母需要花wN,而对剩下部分的比较需2NlnN次比较
算法5.4 基于单词查找树的符号表
原目录：算法（第四版） / 算法合集
算法5.4 单词查找树
以字符串为键的符号表API
public class StringST
返回类型 方法 描述 StringST() 创建符号表 void put(String key, Value val) 插入键值对 Value get(String key) key对应值 void delete(String key) 删除key以及值 boolean contains(String key) 是否含有key的值 boolean isEmpty() 符号表是否为空 String longestPrefixOf(String s) s前缀中最长的键 Iterable keysWithPrefix(String s) 所有以s为前缀的键 Iterable keysThatMatch(String s) 所有和s匹配的键 int size() 键值对数量 Iterable keys() 所有和s匹配的键
算法5.4 (R向)单词查找树
- 基本性质
- 将每个键(String)关联值(Value)保存在该键最后一个字母对应结点中
- 值为null的键在符号表中无对应键,存在为了简化单词查找树中的查找
public class TrieST<Value>{
private static int R = 256;
private Node root;
...
}
- 查找:从首字母链接开始,到下一个结点对应第二个字母的链接...不断向下,直到键最后一个字母对应结点或遇到空链接
- 键尾字符对应结点值非空--查找命中
- 键尾字符对应结点值为空--未命中,符号表中不存在被查找的键
- 查找结束于空链接--未命中
public void get(String key){
Node x = get(root, key, 0);
if(x == null) return null;//未找到,返回null
return (Value)x.val;
}
private Node get(Node x, String key, int d){
if(x == null) return null;//空链接
if(d == key.length()){ return x;}
char c = key.charAt(d);//找到第d个字符对应子单词查找树
return get(x.next[c], key, d+1);
}
- 插入:和BST一致,插入就是先进行查找,直到树中尾字符的结点或空链接
- 先遇到空链接:此时树中无插入结点,则需要为每个字符创建一个新结点将值保存在末尾
- 先遇到尾字符:此时树中已有插入结点,则更新值
public void put(String key, Value val){
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d){
if(x == null) x = Node();//空链接,创建新结点
if(d == key.length()){ x.val = val; return x;}
char c = key.charAt(d);//找到第d个字符对应子单词查找树
x.next[c] = put(x.next[c], key, val, d+1);
return x;
}
- 结点的表示
- 每个结点含有R个链接,对应每个可能字符
- 字符和键值隐式的保存:如sea,数据结构中没有"s""e""a",但通过从根结点到最后结点每段路径的链接位置19->5->1标识
//内部类
private static class Node{
private Object val;//无法定义泛型数组
private Node[] next = new Node[R];
}
- 大小:统计树中键的数量
- 即时实现:设置实例变量N,在put()和delete()时更新
- 延时实现:递归遍历所有结点
//递归延时实现:牺牲性能
public int size(){ return size(root); }
private int size(Node x){
if(x == null) return 0;
int cnt = 0;
if(x.val != null) cnt++;
for(char c = 0; c < R; c++)
cnt += size(next[c]);
return cnt;
}
- 查找所有键
- BST中Node有val变量,所以可以通过遍历BST后将val放入队列完成所有查找
- SST中没有显式保存字母,需要实现collect():将字符显示入队同时进入下个字符链接,查找所有键时,使用""为前缀,调用keysWithPrefix(),方法中先使用get()获得给定前缀的查找树
public Iterabel<String> keys(){
return keysWithPrefix("");
}
public Iterable<String> keysWithPrefix(String pre){
Queue<String> q = new Queue<>();
collect(get(root, pre, 0));
return q;
}
private void collect(Node x, String pre, Queue<String> q){
if(x == null) return;
if(x.val != null) q.enqueue(pre);
//当x!=null且x.val==null时,即一个中间字符,继续调用collect()
for(char c = 0; c < R; c++)
collect(x.next[c], pre + c, q);
}
- 通配符匹配
- 以"."为通配符,一个.代表一个字母,执行keysThatMatch(".he"),结果会是she,the等,keysThatMatch("s.."),结果会是sea,she
- 修改collect(),入队条件扩充为(d == pat.length() && x.val != null),没有前半句会匹配出字符数不达标的String
public Iterable<String> keysThatMatch(String pat){
Queue<String> q = new Queue<String>();
collect(root, "", pat, q);
return q;
}
private void collect(Node x, String pre, String pat, Queue<String> q){
int d = pre.length();
if(x == null) return;
if(d == pat.length() && x.val != null) q.enqueue(pre);
if(d == pat.length()) return;
char next = pat.charAt(d);
//当x!=null且x.val==null时,即一个中间字符,继续调用collect()
for(char c = 0; c < R; c++)
if(next == '.' || next == c)
collect(x.next[c], pre + c, pat, q);
}
- 最长前缀
- 给定字符串,返回其前缀中最长的键:如longestPrefixOf("shell"),返回she,longestPrefixOf("shells")返回shell
public String longestPrefixOf(String s){
int length = search(root, s, 0, 0);
return s.substring(0, length);
}
private int search(Node x, String s, int d, int length){
if(x == null) return null;//空链,停止
if(d == s.length()) return length;//字符串本身为键
if(x.val != null) length = d;
char c = s.charAt(d);
return search(x.next[c], s, d+1, length);
}
- 删除
- 在SST中删除,找到键对应结点,将值设为null,若结点后还指向某个子结点,则无需其他操作
- 若结点后所有链接都为空,则需要删除结点,若删去它后父结点为空,则继续删去父结点
public void delete(String key){
root = delete(root, key, 0);
}
private Node delete(Node x, String key, int d){
if(x == null) return null;
if(d == key.length()) x.val = null;//找到结点,值设为null
else{
char c = key.charAt(d);
x.next[c] = delete(x.next[c], key, d+1);
}
if(x.val != null) return x;
for(char c = 0; c < R; c++)
if(x.next[c] != null) return x;
return null;
}
算法分析
- 单词查找树的链表结构和键的插入或删除顺序无关:给定的一组键,树是唯一的
- 单词查找树中查找或插入一个键,访问数组次数最多为键长度加1
证明:put()和get()递归中的参数d,初始0,进入最后一次递归时x.next[c] = put(x.next[c], key, val, d+1),此时d=key.length()
- 字母表大小R,对N个随机键构造的查找树中,未命中查找平均需要检查~logRN个结点,未命中查找成本与键的长度无关
证明:见书P484
- 一棵单词查找树中链接总数在RN到RNw间,w为键平均长度
- 缩小R可节省大量空间
证明:树中,每个键有一个结点保存值,同时一个结点关联R个链接,因此假设最好情况N个键有N个结点,则RN个链接,但若所有键首字母都不同,每个键的每个字母都有一个对应结点,链接为R乘所有键中字符总数:RNw
算法5.5 三向单词查找树
原目录：算法（第四版） / 算法合集
算法5.5 三向单词查找树
算法描述
- R向查找树每个结点保存R条链接,会有大量空间损耗,而三向单词查找函数TST,采用类似BST的结构,每个结点一个字符,三条链接,一个值,链接对应小于,等于,大于值的结点,TST中字符是显示保存的
实现
public class TST<Value>{
private Node root;
private class Node{
char c;
Node left, mid, right;//三个子树
Value val;//显示保存字符
}
public Value get(String key){
Node x = get(root, key, 0);
if(x == null) return null;
return (Value)x.val;
}
private Value get(Node x, String key, int d){
if(x == null) return null;
char c = key.charAt[d];
if(c < x.c) return get(x.left, key, d+1);
else if(c > x.c) return get(x.right, key, d+1);
else if(d < key.length()-1) return get(x.mid, key, d+1);
else return x;
}
public void put(String key, Value val){ root = put(root, key, val, 0);}
private Node put(Node x, String key, Value val, int d){
char c = key.charAt(d);
if(x == null){ x = new Node(); x.c = c};
if(c < x.c) x.left = put(x.left, key, val, d);
else if(c > x.c) x.left = put(x.right, key, val, d);
else if(d < key.length()-1) put(x.mid, key, d+1);
else x.val = val;//键存在,更新值
return x;
}
}
算法分析
- N个平均长度w的字符串构造的TST中链接总数在3N到3Nw之间
- 查找成本:未命中查找平均比较~lnN次,一次插入或命中查找会比较一次被查找键中的每个字符
字符串查找算法
算法5.6 KMP字符串查找
原目录：算法（第四版） / 算法合集
Knuth-Morris-Pratt子字符串查找
算法描述
- KMP算法基本思想是匹配失败时,已经知晓部分文本,从而避免回退到所有字符前
DFA模拟
DFA确定优先有限状态自动机,由状态和转换构成,pat中的每一个字符可代表一个状态
二维数组表示:dfa[转换][状态]即为一个DFA
字符串查找:DFA中,只有一条是匹配转换,从j->j+1,其余都非匹配,回到之前某个状态
KMP算法和DFA
- 模拟DFA运行:只要知道dfa[][]就可以得到KMP算法:当txt的i和pat的j指向字符匹配失败(从txt的i-j+1开始匹配),pat的下一可能匹配位置应从i-dfa[txt.charAt(i)][j]开始,但从该位置开始的dfa[txt.charAt(i)][j]个字符和pat的前dfa[txt.charAt(i)][j]个字符相同,无需回退指针i,只需将j设置为dfa[txt.char(i)][j]并且i+1即可
//模拟DFA运行
public int search(String txt){
int i,j,N = txt.length(), M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++)
j = dfa[txt.charAt(i)][j];
if (j == M) return i-M;//找到匹配
else return M;//未找到匹配
}
构造DFA
- 核心:dfa[i][j]要理解为j状态时接收i时发生的转换
- 考虑暴力解法在pat.charAt(j)匹配失败时
- 回退文本指针i至初始位置
- 文本指针右移一位,重新开始扫描
- 重点在于:pat.charAt(1)到pat.charAt(j-1)被重新扫描,首字母和最后一个字符忽略
- 考虑DFA只要知道暴力法回退扫描完后DFA的状态,将其重置为此状态,就达到了不移动指针但等价的效果
- 匹配失败:dfa[][X]复制到dfa[][j]
- 匹配成功: dfa[pat.charAt(j)][j]设置为j+1
- 重启状态X: X = dfa[pat.charAt(j)][X]
public KMP(String pat){
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
//构建DFA
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j< M; j++){
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X];//匹配失败
dfa[pat.charAt(j)][j] = j+1;//匹配成功
X = dfa[pat.charAt(j)][X];//更新重启状态
}
}
KMP算法API
返回类型 方法 描述 KMP(String pat) 根据pat构建DFA int search 输入txt运行DFA
public class KMP {
private String pat;
private int[][] dfa;
public KMP(String pat){}
public int search(String txt){}
public static void main(String[] args){
String pat = args[0];
String txt = args[1];
KMP kmp = new KMP(pat);
StdOut.println("text: " + txt);
int offset = kmp.search(txt);
StdOut.print("pattern");
for (int i = 0; i < offset; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
算法分析
- 长度M的pat和N的txt,KMP算法访问字符不会超过M+N个
证明:在KMP()构造DFA时访问pat中每个字符一次,在search()访问每个txt字符一次
算法5.7 Boyer-Moore字符串查找
原目录：算法（第四版） / 算法合集
算法5.7 Boyer-Moore字符串查找
算法描述
- BM查找是在允许回退时,从右向左扫描pat检查是否与txt匹配,并在匹配失败时通过跳跃将文本中字符和它在pat中出现的最右位置对齐
实现
- 跳跃表right[]:该数组记录字母表中每个字符在pat中最靠右出现的位置,当不存在记为-1,该记录表示当匹配失败时pat应该向右跳跃几位
public BoyerMoore(String pat){
this.pat = pat;
int R = 256;
int M = pat.length();
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < M; j++)
right[pat.charAt(j)] = j;
}
- 查找:i,j分别为txt和pat指针,若j从M-1到0循环,txt.charAt(i+j)和pat.charAt(j)都相等,则匹配成功,否则失败
- 失败字符不在pat中:则将pat右移j+1位(通过i增加j+1实现),重置j为M-1
- 失败字符在pat中:则将pat右移直到该字符和其在pat中最右边位置对齐
- 当需要左移时:至少让i+1,右移一位
public int search(String txt){
int N = txt.length();
int M = pat.length();
int skip;
for (int i = 0; i < N; i += skip){
skip = 0;
for (int j = M-1; j >= 0; j--){
if (txt.charAt(i+j) != pat.charAt(j)){
skip = j - right[txt.charAt(i+j)];
if (skip < 1) skip = 1;
break;//当前字符匹配失败
}
}
if (skip == 0) return i;//找到匹配
}
return N;//匹配失败
}
public class BoyerMoore {
private int[] right;
private String pat;
public BoyerMoore(String pat){}
public int search(String txt){}
}
算法分析
- 长N的txt和M的pat,是哟BM算法需要~N/M次比较
证明:跳跃使得几乎所有比较都会跳过M个字符
算法5.8 Rabin-Karp指纹字符串查找
原目录：算法（第四版） / 算法合集
RK字符串查找算法
算法描述
- RK算法是一种基于散列的算法:计算pat的散列函数,用相同函数计算txt中所有可能的M个字符的字符串散列值,寻找匹配
实现
- 计算散列函数:Horner方法--除留余数法计算散列值
private long hash(String key, int M){
long h = 0;
for (int j = 0; j < M; j++)
h = (R*h + key.charAt(j)) % Q;
return h;
}
问题:算法不会生成散列表,需要实时计算散列值比较,若每次都接收一个key在计算,开销最坏依旧为NM和暴力法一致
改进:利用i位散列值,计算i+1位散列值
- txt中i位起始的M个字符散列值:减去LSD,乘R,加上新的MSD
- 转换为R进制数:Xi=tiRM-1+ti+1RM-2+...+ti+M-1R0
- xi+1 = (xi-tiRM-1)R+ti+
M
- h(xi+1)=xi+1modQ
- 以上操作可分步求模:分步求模等价与所有运算后求模,且实际运算加上Q保证结果为正
private int search(String txt){
int N = txt.length();
long txtHash = hash(txt, M);//注意为M
if (patHash == txtHash) return 0;//初始就匹配成功
for (int i = M; i < N ; i++){
txtHash = (txtHash + Q - RM * txt.charAt(i-M) % Q) % Q;
txtHash = (txtHash*R + txt.charAt(i)) % Q;
if (txtHash == patHash) return i-M+1;//找到匹配
}
return N;//未找到
}
- 正确性:当散列值相等后,在没有构建散列表的情况下为了避免散列值冲突可能会再次比较两个字符串是否一致,但若令Q为大于1020,冲突概率小于10-20,叫做蒙特卡洛算法
public class RabinKarp {
private long patHash;
private int M;
private long Q;//一个很大素数
private int R;
private long RM;//减去第一个数字
public RabinKarp(String pat){}
private long hash(String key, int M){}
private int search(String txt){}
}
算法分析
- 当Q采取很大素数时,RK算法可以在接近线性级别且保持准确性的查找字符串,被称为指纹查找,因其可以将极大的pat转换为极少的信息hashcode进行查找
Ex1_1_24辗转相除法（递归）
原目录：算法（第四版） / Ch1 基础 › 1.1基础模型
要求：计算111111和1234567的最大公约数
pubilc class Ex1_1_24{
private static int Euclid(int a, int b){
int c = a % b;
if（c == 0）return b;
return Euclid（b， c）;
}
pubilc static void main(String[] args){
System.out.println(Euclid(1111111, 1234567)
}
}
要点:
a = n*b + c, 当c == 0时, b即为最大公约数,否则b代替a, c代替b.
Ex1_1_27二项分布概率计算
原目录：算法（第四版） / Ch1 基础 › 1.1基础模型
要求:估计用以下代码计算binomial(100, 50, 0.25)的次数
private static double binomial(int N, int k, double p){
if(N == 0 && k == 0) return 1.0;
if(N < 0 || k < 0) return 0.0;
return (1.0 - p)*binomial(N-1, k, p) + p*binomial(N-1, k-1, p);
}
解析:
binomial方法主要运用了二项概率的递推公式
约分即得到组合数递推公式
\(C_N^k=C_N^{k-1}+C_{N-1}^{k-1}{\color{Blue}\ }\)
问题:
该方法一个递归就产生两个子递归,运算量非常大,如题数据会一直计算无法得到结果
改进方法:
思路:
已知二项概率公式和组合数公式
\(P(N,k)=C_N^kp^k(1-p)^{N-k}\)
\(C_N^k=\frac{N!}{k!(N-k)!}\)
先计算组合数,但当N较大很大时,阶乘会超出int类型值域,所以需要每次乘一项后就约分为最简形式,可以使用求最大公约数的算法
例:
\(C_3^2=\frac{3}{2\times1}\times\frac{2}{1\times1}\times\frac{1}{1\times1}\)
pubilc class Ex1_1_27{
//计算组合数
private static double Combine(int X, int Y, int Z){
if(x == 0 && Y == 0 && Z == -1){
return 1;
}
if(x == 0) x = 1;
if(Y == 0) Y = 1;
if(Z == 0) Z = 1;
int a = Euclid(X, Y*Z);
return Combine((x*1.0/a)/(Y*Z/a));//强转或x*1.0,否则返回int
}
//计算概率
private static double binomial(int N, int k, double p){
double p1 = 1;
double p2 = 1;
for(int i = 1; i <= k; i++){
p1 *= p;
}
for(int i = 1; i <= (N-k); i++){
p2 *= 1-p;
}
double C = Combine(N, k, N-k);
return C * p1 * p2;
}
public static void main(String[] args){
System.out.println(binomial(100, 50, 0.25));
//概率:6.828252801404798E-91
}
}
Ex1_1_31-32 StdDraw
原目录：算法（第四版） / Ch1 基础 › 1.1基础模型
Ex1_1_31要求:接收整数N和double p,在圆上画出大小0.05且间距相等的N个点,每对点以概率p相连
关键算法: 得到圆上等距的N个点,x=rconα,y=rsinα
for(int a = 0; a < N; a++){
point[a][0] = Math.cos(a*2*Math.PI/N);
point[a][1] = Math.sin(a*2*Math.PI/N);
StdDraw.point(point[a][0],point[a][1]);
}</code></pre>
Ex1_1_32要求:接收整数N和double l,r,将(l,r)分为N段,画出输入流中值在每段的直方图
关键算法:统计每段的输入值个数
while (!StdIn.isEmpty()){
double input = StdIn.readDouble();
for(int i = 0; i< N;i ++){
if(input <= l+(i+1)*d && input > l+i*d){
amount[i] += 1.0/N;
}
double x = 1.0*i/N;
double y = amount[i]/2.0;
StdDraw.filledRectangle(x,y,0.5/N,y);
}
}
关于StdDraw.filledRectangle
默认在长宽各为1的创口绘图,参数前两个为每个直方的中心点坐标,后两个为宽度/2,高度/2
重定向与管道
原目录：算法（第四版） / Ch1 基础 › 1.1基础模型
重定向
命令行中使用"<"字符可以将标准输入定向到文本文件,如java Average < data.txt表示对data中数据求平均值;">"将标准输出定向到文本文件,java RandomSeq 1000 100.0 200.0 > data.txt表示将输出写入data
管道
管道通过"|"符号将一个程序的输出作为另一个程序的输入,如java RandomSeq 1000 100.0 200.0 | java Average
Powershell与命令行下运行区别
1.Powellshell中输入cmd后,即回归普通cmd,重定向两种符号都可使用
2.直接在Powershell中无法使用"<"接收文件作为标准输入
1.2数据抽象
原目录：算法（第四版） / Ch1 基础
1.2数据抽象
数据类型: 一组值和一组对这些值操作的集合
抽象数据类型(ADT): 将数据和函数实现关联,并将数据的表示方式隐藏起来.
1.2.1使用抽象数据类型
1.2.1.2继承的方法
toString()方法:Java所有数据类型都会继承此方法返回用String类型表示的该类型值(返回用字符串表示的该数据类型值的内存地址)
1.2.1.4对象
对象三大特性:状态,标识(内存中的位置),行为
引用是访问对象的一种方式,不同Java实现中对引用的实现细节不一样,但可认为引用就是内存地址
1.2.1.6调用实例方法
静态方法主要作用:实现函数
非静态(实例)方法主要作用:实现数据类型的操作
1.2.1.8赋值语句*
原始数据类型的"x=y"将y值复制到x中,对于引用类型,复制的是引用
1.2.1.9将对象作为参数*
原始数据类型———将参数值的副本传递给方法(桉值传递)
引用类型———传递引用的值(复制引用)
1.2.1.10将对象作为返回值
Java方法只能有一个返回值,但有了对象实际上就能返回多个值
1.2.1.11数组也是对象*
Java中,所有非原始数据类型的值都是对象,因此数组作为参数时,也是传递了引用的副本
1.2.1.12对象的数组*
Java中,对象数组即是一个由对象的引用组成的数组,而非对象本身.如果对象非常大,在移动时只需操作引用而非对象本身,提高效率;对象很小时,操作引用反而会降低效率.
小结:运用数据抽象的思想编写代码(定义和使用数据类型,将数据类型的值封装在对象中)的方式称为面向对象编程.
1.2.2抽象数据类型举例
1.2.2.3字符串
String和字符数组类似,但String可以直接使用字符串字面量而非构造函数来创建并初始化字符串
为什么不使用字符数组代替String?:为了使diamante更简洁清晰,且String有许多实例方法可供使用.
1.2.3抽象数据类型的实现
根据抽象数据类型的定义:一种向用例隐藏内部表示的数据类型,抽象数据类型中的实例变量是private的
1.2.3.5API,用例与实现
开发数据类型的步骤:
- 定义API:将使用和实现分离,实现模块化编程.
- 用一个Java类实现API的定义
- 实现多个测试用例来验证
1.2.5.6字符串表示的习惯
一个对象的数据类型如果没有实现toString()方法,则会调用Object的默认实现,返回一个含有该对象内存地址的字符串,无实用价值,一般都需重新实现
1.2.5.9内存管理*
原始数据类型:内存管理对于原始数据类型比较容易,因为内存分配所需的信息在便一阶段就能够获取,Java会在声明变量时为它们预留内存空间,并在离开作用域后释放空间
对象:系统会在创建一个对象是分配内存,Java具有自动内存管理,可将无用的对象内存释放回内存池(垃圾回收)
1.2.5.10不可变性*
Java通过final强制保证不可变性,但final只能保证原始数据类型的实例变量不可变,对于引用类型的实例变量,该实例变量的值(某个对象的引用)无法改变,但对象的值本身仍可以改变
答疑
- 区别原始数据类型和引用类型的原因?
尽管Integer等封装类型可以转原始数据类型为引用类型,但原始数据类型接近低层,运行快速
- Java中的指针:
指针可以看做机器地址,Java的引用被称为安全指针,保证每个引用指向对象并回收无用的对象
3.Java实现引用和垃圾收集的细节?
一种自然方式是指针(机器地址),另一种是句柄(指针的指针),前者访问数据速度快,后者更好实现垃圾回收
Ex1_2_3
原目录：算法（第四版） / Ch1 基础 › 1.2数据抽象
编写Interval2D用例
import edu.princeton.cs.algs4.Interval1D;
import edu.princeton.cs.algs4.Interval2D;
import edu.princeton.cs.algs4.Point2D;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_2_3 {
private static void draw2D(int N,double min,double max) {
Interval2D[] box = new Interval2D[N];
Point2D[][] point = new Point2D[N][4];
double xlo,xhi,ylo,yhi;
int intersectCount = 0, containCount = 0;
for(int i=0; i<N; i++) {
do xlo = Math.random();
while (xlo < min || xlo > max);
do xhi = Math.random();
while (xhi < min || xhi > max || xhi < xlo );
do ylo = Math.random();
while (ylo < min || ylo > max);
do yhi = Math.random();
while (yhi < min || yhi > max || yhi < ylo );
Interval1D xinterval = new Interval1D(xlo,xhi);
Interval1D yinterval = new Interval1D(ylo,yhi);
box[i] = new Interval2D(xinterval,yinterval);
point[i][0] = new Point2D(xlo,ylo);
point[i][1] = new Point2D(xlo,yhi);
point[i][2] = new Point2D(xhi,ylo);
point[i][3] = new Point2D(xhi,yhi);
box[i].draw();
}//绘图循环
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
if(box[i].intersects(box[j])) {
intersectCount++;
}
}
}//遍历判断相交
StdOut.println(intersectCount);
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
if(box[i].contains(point[j][0])
&&box[i].contains(point[j][1])
&&box[i].contains(point[j][2])
&&box[i].contains(point[j][3])) {
containCount++;
}
}
}//遍历判断包含
containCount -= N;
StdOut.println(containCount);
}
public static void main(String[] args) {
int N = Integer.parseInt(args[0]);
double min = Double.parseDouble(args[1]);
double max = Double.parseDouble(args[2]);
draw2D(N,min,max);
}
}
要点:
判断矩形间相交用组合思想,N(N-1)次循环,不重复计算相交;判断矩形间包含时用排列思想,NN次循环,才能判断包含.
Ex1_2_6
原目录：算法（第四版） / Ch1 基础 › 1.2数据抽象
要求 判断两个字符串是否是回环变位
import edu.princeton.cs.algs4.StdOut;
public class Ex1_2_6 {
private static boolean circular(String s, String t) {
return (s.length() == t.length() && (s + s).indexOf(t) > 0);
}
public static void main(String[] args){
if(circular("ACTGACG","TGACGAC")){
StdOut.println("yes");
}else{
StdOut.println("No");
}
}
}
要点:
indexOf()在找不到子串是返回-1,因此(s.length() == t.length() && (s + s).indexOf(t) > 0)一句话即可判断是否是回环变位
Ex1_2_10
原目录：算法（第四版） / Ch1 基础 › 1.2数据抽象
要求:能进行±1的可视化counter
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdRandom;
public class Ex1_1_10 {
public static class VisualCounter{
private int times = 0;
private int count = 0;
private int max;
public VisualCounter(int N, int max){
this.max = max;
StdDraw.setXscale(0,N);
StdDraw.setYscale(-max,max);
StdDraw.setPenRadius(.005);
}
public void increment(){
count++;
times++;
if(count > max) count = max;
StdDraw.point(times,count);
}
public void reduction(){
times++;
count–;
if(count < -max) count = -max;
StdDraw.point(times,count);
}
}
public static void main(String[] args){
int N = Integer.parseInt(args[0]);
int max = Integer.parseInt(args[1]);
VisualCounter counter = new VisualCounter(N,max);
for(int i=0; i<N; i++){
if(StdRandom.bernoulli(0.5)){
counter.increment();
}else{
counter.reduction();
}
}
}
}
结果(N = 10000, max = 100)
源图片已失效：1_2/VisualCounter.jpg
1.3背包,队列和栈
原目录：算法（第四版） / Ch1 基础
1.3背包,队列和占道
1.3.1API
1.3.1.3可迭代的集合类型
如果集合是可迭代的,就能够使用foreach语句
1.3.1.4背包
背包(Bag)是一种不支持从中删除元素的集合类型
1.3.1.5先进先出队列*
队列(Queue)是一种基于先进先出(FIFO)的集合类型
使用情形: 在集合保存元素的同时保存相对顺序:使它们入列顺序和出列顺序相同
1.3.1.6下压栈*
栈(Stack)是一种基于后进先出(LIFO)的集合类型
使用情形: 在集合保存元素的同时颠倒相对顺序
1.3.1.7算术表达式求值*
求值算法:双栈运算法
操作:
- 准备两个栈:运算符栈,操作数栈
- 忽略左括号,将操作数和运算符分别压入对应栈内
- 遇到右括号,弹出一个运算符,弹出所需数量的操作数,并将运算符和操作数的结果压入操作数栈
漏洞:
- 最多只能有两个操作数在括号内运算
- 必须有左括号和右括号
1.3.2集合类数据类型的实现
1.3.2.2 泛型*
创建泛型数组在Java中不被允许,需要使用强转
Item[] a = (Item[]) new Object[cap];
1.3.2.4对象游离*
栈中元素pop()后,被弹出元素的引用依旧存在于数组中,但元素不会再被访问,垃圾回收机无法判断,除非引用被覆盖,这是需要使引用指向null
Item item = a[--N];
a[N] = null;//防止游离
1.3.2.5迭代*
实现可迭代类的方法:
- 集合实现Iterable接口,在类中重写iterator()方法,并返回迭代器Iterator
implements Iterable<Item>
public Iterator<Item> iterator(){
return new XXXIterator();
}
- 根据不同要求,可以编写子类XXXIterator,重写hasNext(),next(),remove()方法,生成迭代器
1.3.3 链表*
链表定义:一种递归的数据结构,或者为空(null),或者指向一个节点(node)的引用,该结点含有一个泛型元素和一个指向另一条链表的引用.
1.3.3.1节点记录
private class Node{
Item item;
Node mext;
}
1.3.3.7遍历
for(Node x = first; x != null; x = x.next){
//链表的遍历
}
1.3.4综述
基础数据结构
数据结构 优点 缺点 数组 通过所以可直接访问任意元素 在初始化时就需知道元素数量 链表 使用的空间大小和元素数量成正比 需通过引用访问任意元素
答疑
1.为什么将内部类Node声明为private?
为了将Node的方法和实例变量的访问范围限制在包含它的类中.私有嵌套类的特点:只有包含它的类可以直接访问它的实例变量,所以无需声明它的实例变量为public或private
2. 为什么不实现一个单独的Collection数据类型实现添加,删除,迭代?
宽接口无法保证高效的实现某些方法,设计只有几个操作的借口可以简化操作,并限制用例行为.
Ex1_3_9 补全缺少左括号的中缀表达式
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_9 补全缺少左括号的中缀表达式
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_9 {
public static void main(String[] args){
Stack<String> vals = new Stack<>();
Stack<String> ops = new Stack<>();
while (!StdIn.isEmpty()){
String s = StdIn.readString();
if(s.equals("+")) ops.push(s);
else if(s.equals("-")) ops.push(s);
else if(s.equals("*")) ops.push(s);
else if(s.equals("/")) ops.push(s);
else if(s.equals("sqrt")) ops.push(s);
else if(s.equals(")")){
String op= ops.pop();
String val = vals.pop();
if(op.equals("sqrt")){//需满足sqrt中为两个值的运算
String exp = String.format("( %s %s )",op,val);
vals.push(exp);
}else {
String exp = String.format("( %s %s %s )", vals.pop(), op, val);
vals.push(exp);
}
}
else{
vals.push(s);
}
}
StdOut.println(vals.pop());
}
}
/1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )补全后
( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )
sqrt 3 + 5 ) )补全后
( sqrt ( 3 + 5 ) )
/
要点:
- 使用堆栈,用String.format()前各弹出一个符号和数值
Ex1_3_10 中序转后序
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_10 中序转后序
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_10 {
public static void main(String[] args){
Stack<String> vals = new Stack<>();
Stack<String> ops = new Stack<>();
while (!StdIn.isEmpty()){
String s = StdIn.readString();
if(s.equals("("));
else if(s.equals("+")) ops.push(s);
else if(s.equals("-")) ops.push(s);
else if(s.equals("*")) ops.push(s);
else if(s.equals("/")) ops.push(s);
else if(s.equals("sqrt")) ops.push(s);
else if(s.equals(")")){
String val = vals.pop();
String op = ops.pop();
if(op.equals("sqrt")){
String temp = String.format("%s %s",val,op);
vals.push(temp);
}else{
String temp = String.format("%s %s %s",vals.pop(),val,op);
vals.push(temp);
}
}
else vals.push(s);
}
StdOut.println(vals.pop());
}
}
//( ( 1 + 2 ) * ( ( 3 - 4 ) * ( 5 - 6 ) ) )转为1 2 + 3 4 - 5 6 - * *
要点:
- 使用双栈法的变形
- 中序表达式一定需要满足两个一组用括号括起
Ex1_3_11 计算后序表达式
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_11 计算后序表达式
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_11 {
public static void main(String[] args){
Stack<Double> vols = new Stack<>();
while (!StdIn.isEmpty()){
String s = StdIn.readString();
double vol = 0;
switch (s){
case "+":
vol = vols.pop() + vols.pop();
vols.push(vol);
break;
case "-":
vol = -vols.pop() + vols.pop();
vols.push(vol);
break;
case "*":
vol = vols.pop() * vols.pop();
vols.push(vol);
break;
case "/":
vol = 1/vols.pop() * vols.pop();
vols.push(vol);
break;
case "sqrt":
vol = Math.sqrt(vols.pop());
vols.push(vol);
break;
default:
vol = Double.parseDouble(s);
vols.push(vol);
break;
}
}
StdOut.println(vols.pop());
}
}
要点:
- 使用双栈法变形
- 注意pop出的顺序
Ex1_3_28 递归返回节点最大值
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_28 递归返回节点最大值
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class Ex1_3_28_maxNode<Item> {
private class Node{
Item item;
Node next;
}
private Node head;
private int N = 0;
public boolean isEmpty(){
return head == null;
}
public int size(){
return N;
}
public void headInsert(Item item){
Node node = head;
head = new Node();
head.item = item;
head.next = node;
N++;
}
public void headRemove(){
if (isEmpty()) throw new RuntimeException("Queue underflow");
else{
head = head.next;
N--;
}
}
public int max(Node max, Node node){
if(max == null) return 0;//空链表
else if(node == null) return (int)max.item;//最大值
else{
if((int)max.item > (int)node.item){
return max(max, node.next);
}else return max(node, node.next);
}
}
public static void main(String[] args){
Ex1_3_28_maxNode m = new Ex1_3_28_maxNode();
while (!StdIn.isEmpty()){
int a = StdIn.readInt();
m.headInsert(a);
}
StdOut.println(m.max(m.head,m.head.next));
}
}
要点:
- 链表实现,采用头插头删
- 递归初始接收head,head.next为参数;当开始head == null说明是空链表,返回0,当node == null说明链表已经遍历完毕,返回max
Ex1_3_31 双向链表DulLinkList
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_31 双向链表DulLinkList
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
public class DulLinkList<Item> {
private class DulNode {
Item item;
DulNode left;
DulNode right;
}
private DulNode head;
private DulNode tail;
private int size;
public int getSize() {
return size;
}
public boolean isEmpty() {
return head == null;
}
//从表头插入节点
public void headInsert(Item item) {
DulNode current = head;
head = new DulNode();
head.item = item;
if (isEmpty()) {
tail = head;
}//链表为空时head,tail指向一个节点
else {
head.right = current;
}
size++;
}
//从表尾插入节点
public void tailInsert(Item item) {
DulNode current = tail;
tail = new DulNode();
tail.item = item;
tail.left = current;
if (isEmpty()) {
head = tail;//tail = head错误,两个永远为null
}//链表为空时head,tail指向一个节点
else {
current.right = tail;
}
size++;
}
//从表头删除节点
public Item headDel() {
Item item = head.item;
head = head.right;
size--;
return item;
}
//从表尾删除节点
public Item tailDel() {
Item item = tail.item;
tail = tail.left;
size--;
return item;
}
//在指定节点前插入节点
public void beforeInsert(DulNode exist, Item item) {
DulNode dulNode = new DulNode();
dulNode.item = item;
if(exist.left == null) headInsert(item);
else{
exist.left.right = dulNode;
dulNode.left = exist.left;
exist.left = dulNode;
dulNode.right = exist;
size++;
}
}
//在指定节点后插入节点
public void afterInsert(DulNode exist, Item item){
DulNode dulNode = new DulNode();
dulNode.item = item;
if(exist.right == null) tailInsert(item);
else{
exist.right.left = dulNode;
dulNode.right = exist.right;
exist.right = dulNode;
dulNode.left = exist;
size++;
}
}
//删除指定节点
public Item del(DulNode dulNode){
Item item = dulNode.item;
if (dulNode == head) headDel();
else if(dulNode == tail) tailDel();
else{
dulNode.left.right = dulNode.right;
dulNode.right.left = dulNode.left;
}
return item;
}
//测试用例
public static void main(String[] args){
DulLinkList linkList = new DulLinkList();
while(!StdIn.isEmpty()){
String s = StdIn.readString();
linkList.tailInsert(s);
}
linkList.beforeInsert(linkList.head,-1);
StdOut.println(linkList.size + " elements");
StdOut.println(linkList.head.item);
StdOut.println(linkList.tail.item);
}
}
要点:
- 插入节点时,当链表为空,head,tail都指向新节点,注意
//实例化表头
DulNode current = head;
head = new DulNode();
head.item = item;
if (isEmpty()) {
tail = head;
}//链表为空时head,tail指向一个节点
else {
head.right = current;
}
//实例化表尾
DulNode current = tail;
tail = new DulNode();
tail.item = item;
tail.left = current;
if (isEmpty()) {
head = tail;//tail = head错误,两个永远为null
}//链表为空时head,tail指向一个节点
else {
current.right = tail;
}
将实例化的节点赋值给空引用,才能让tail与head都指向实例化节点,若赋值顺序颠倒,两节点用为null
2. 注意在指定节点前/后插入节点,要判断指定节点是否是头/尾结点,否则会产生空指针错误
3. 插入节点时连接顺序不同
//前插
if(exist.left == null) headInsert(item);
else{
exist.left.right = dulNode;
dulNode.left = exist.left;
exist.left = dulNode;
dulNode.right = exist;
size++;
}
//后插
if(exist.right == null) tailInsert(item);
else{
exist.right.left = dulNode;
dulNode.right = exist.right;
exist.right = dulNode;
dulNode.left = exist;
size++;
}
在指定节点前插入节点时:在AB中指定B插入C,则先连接A.right和B.left再连接BC
在指定节点后插入节点时:在AB中指定A插入C,则先连接C.right和B.left再连接AC
Ex1_3_37 Josephus问题
原目录：算法（第四版） / Ch1 基础 › 1.3背包,队列和栈
Ex1_3_37 Josephus问题
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
//使用由循环单链表实现的队列完成
public class Ex1_3_37_Josephus<Item> {
private class Node{
Item item;
Node next;
}
private int size;
private Node last;
public boolean isEmpty(){ return size == 0; }//last.next不可用
public int size(){ return size; }
public void enqueue(Item item){
Node oldLast = last;
last = new Node();
last.item = item;
if(isEmpty()) last.next = last;
else{
last.next = oldLast.next;
oldLast.next = last;
}
size++;
}
public Item dequeue() {
Item item = last.next.item;
size--;
if (isEmpty()) last = null;
else {
last.next = last.next.next;
}
return item;
}
//测试用例
public static void main(String[] args){
Ex1_3_37_Josephus Queue = new Ex1_3_37_Josephus();
int N = Integer.parseInt(args[0]);
int M = Integer.parseInt(args[1]);
for(int i = 0; i < N; i++){ Queue.enqueue(i); }
for(int i = 0; i < N; i++){
Ex1_3_37_Josephus.Node node = Queue.last.next;
for(int j = 0; j < M-2; j++){
node = node.next;
}
Queue.last = node;
StdOut.println(Queue.dequeue());
}
}//当N=7, M=2时输出1 3 5 0 4 2 6, 6号位最后一个
}
要点
- Queue除了使用有first和last节点的链表实现,还可以使用只有last节点的循环链表实现
- 这种实现中,isEmpty()不能使用last.next == null判断,因为dequeue()和enqueue()中last.next开始总等于null
- 实现思路:每次需要删除规定位次的结点,只能动态改变头结点(尾节点)引用的指向
for(int i = 0; i < N; i++){
CircleLinkList.Node node = linkList.last.next;//找出当前头结点
for(int j = 0; j < M-2; j++){//根据规定的位次找到当前头结点下规定位次节点
node = node.next;
}
linkList.last = node;//为方便删除,让被找出节点成为头节点(实际上找出尾节点,头结点自动形成)
StdOut.println(linkList.dequeue());//删除并打印
}
1.4算法分析
原目录：算法（第四版） / Ch1 基础
1.4算法分析
1.4.3数学模型
一个程序运行的总时间主要和两点有关:
1. 执行每条语句的耗时
2. 执行每条语句的频率
前者取决于计算机,编译器和操作系统.后者取决于程序本身和输入,因此
总时间 = 每条语句耗时*每条语句频率 + 指令成本
1.4.3.1近似
在频率分析中可能产生冗长的表达式,如:
\(\frac{N(N-1)(N-2)}{6}=\frac{N^3}{6}-\frac{N^2}{2}+\frac{N}{3}\)
这种表达式中,首项之后的其他项都很小,常使用~符号忽略较小项
一般的近似方式
\(g(N)\sim af(N),f(N)=N^b(logN)^c(a,b,c=constant)\)
一般不会指定底数,因为常数a可以弥补
典型的近似
函数 近似 增长的数量级 N³/6-N²/2+N/3 ~N³/6 N³ N²/2-N/2 ~N²/2 N² lgN+1 ~lgN lgN 3 ~3 1
常见的增长数量级函数
描述 函数 常数级别 1 对数级别 logN 线性级别 N 线性对数级别 NlogN 平方级别 N² 立方级别 N³ 指数级别 2^N
1.4.3.2近似运行时间
近似运行时间的计算:根据执行频率将Java语句分块,计算出每种频率的首项近似,判定每条指令的执行成本并计算出总和.
关键现象:执行最频繁的指令--程序的内循环,决定了程序执行的总时间.
1.4.4增长数量级的分类
典型增长数量级函数
对增长数量级的常见假设总结
描述 增长的数量级 说明 举例 常数级别 1 普通语句 两数相加 对数级别 logN 二分策略 二分查找 线性级别 N 循环 找出最大值 线性对数级别 NlogN 分治 归并排序 平方级别 N² 双层循环 检查所有元素对 立方级别 N³ 三层循环 检查所有三元组 指数级别 2^N 穷举查找 检查所有子集
注意:平方级别和立方级别的算法对于大规模的问题是不可用的,许多问题的平方级解法可以有线性对数级别算法代替
1.4.6倍率实验
倍率实验通过计算每次试验和上一次运行时间的比值(问题规模每次翻倍),反复运行直到比值趋近极限2b.可得结论:它们运行时间的增长数量级约为Nb
常见的增长数量级函数(指数级别除外)均有如下结论:
\(如果T(N)\sim aN^blgN,则\frac{T(2N)}{T(N)}\sim 2^b\)
1.4.7注意事项
1.4.7.1大常数
有事只保留首项是错误的,如2N²+cN中,如果c非常大,则首项近似就是错误的
1.4.7.2非决定性内循环
1.4.7.3指令时间
1.4.7.4系统因素
1.4.7.6对输入的强烈依赖
1.4.9内存
Java原始数据类型常见内存/需求
类型 字节 boolean 1 byte 1 char 2 int 4 float 4 long 8 double 8
1.4.9.1对象
对象使用内存 = 所有实例变量内存 + 对象本身开销(一般为16字节,包括一个指向对象的类的引用,垃圾收集信息,同步信息,且一般内存的使用都会被填充为8字节的倍数)
一个Integer对象使用24字节开销 = 16字节对象开销 + 4字节int开销 + 4字节填充
1.4.9.2链表
嵌套的非静态(内部)类,如Node类,还需要额外8字节用于一个指向外部类的引用
一个Node对象使用40字节开销 = 16字节对象本身 + 指向Item和Node对象的引用各需要8字节 + 8字节额外开销
1.4.9.3数组
Java中数组被视为对象,数组都需要24字节的头信息(16字节对象开销+4字节保存长度+4字节填充);一个对象的数组实际上是对象的引用的数组,除了对象元素的开销还有对象引用的开销;而二维数组是一个数组的数组,每个数组都是一个对象
- 一般数组:一个N个int的数组开销(24+4N)字节 = 24字节头信息 + 4N数组元素开销
- 对象数组:一个含有N个Node对象的数组开销(24+40N+8N)字节 = 24字节头信息 + 40N对象元素开销 + 8N对象引用开销
- 二维数组:一个M*N的double类型数组开销()字节 = 24字节头信息 + 8M字节所有对象引用开销 + 24M元素数组开销 + 8MN所有double变量开销
1.4.9.4字符串对象
String对象在库中定义
public class String
{
private char[] value;
private int offset;
private int count;
private int hash;
...
}
String的标准实现含有4个实例变量:一个指向字符数组的引用(8字节)和三个int值(各4字节),第一个int值描述的是字符数组中的偏移量,第二个int值是一个计数器(字符串的长度),第三个int值是一个散列值,因此
一个String对象开销40字节() = 16字节对象开销 + 3*4int开销 + 8字节引用开销 + 4个填充字节
但这只是除了字符数组之外字符串所需的内存空间,所有字符所需的内存需要另记,因为String的char数组常常在多个字符串之间共享,因为String对象不可变.这种设计使String的实现可以在多可对象有相同value[]数组时节省内存
1.4.9.5字符串的值和子字符串
一个长度为N的String对象一般需要(64+2N)字节 = 40字节本身开销 + (24 + 2N)数组开销
但当调用substring()方法创建子字符串是,它仍然使用了相同的value[]数组,因此只会使用40字节,子字符串的别名,子字符串对象的偏移量和长度与标记了子字符串的位置,即"一个子字符串所需的额外内存是一个常数,构造一个子字符串所需的时间也是常数"
在递归中创建数组和其他大型对象的风险
每一次递归调用都会使用大量内存,当方法返回时,占用的内存也被返回给系统栈.new出对象时,系统会从堆内存的另一块区域为该对象分配内存,而且所有对象会一直存在,直到引用消失.这种动态过程使得准确估计一个程序的内存使用极为困难.
答疑
问:大O的含义是什么?
答:定义:对于f(N)和g(N),如果存在常数c和N'使得对于所有N>N'都有|f(N)|<cg(N),则我们称f(N)为O(g(N)),主要描述算法性能的渐进上限.但算法的实际性能可能好很多,所以大O主要简化乐对增长数量级的上限的研究.
2.1初级排序算法
原目录：算法（第四版） / Ch2 排序
2 排序
2.1初级排序算法
2.1.1游戏规则
2.1.1.2运行时间
排序成本模型
类型 说明 交换元素算法 计算比较和交换的数量 不交换元素 计算访问数组的次数
2.1.1.3额外内存使用
排序算法分类
类型 说明 原地排序算法 只需函数调用所需的栈和固定数目的实例变量 其他排序算法 需要额外内存空间存储数组副本
2.1.1.4数据类型
创建自己的数据类型时,只要实现Comparable接口就可以保证用例代码可以将其排序,只需要实现compareTo()方法定义目标类型对象的自然次序,从而实现主键抽象
v.compareTo(w)规则
v,w大小关系 方法返回值 v == w 0 v > w >0 v < w <0 无法比较/含有null 抛出异常
2.1.2选择排序
2.1.3插入排序
2.1.6希尔排序
排序算法类模版
原目录：算法（第四版） / Ch2 排序 › 2.1初级排序算法
排序算法类模版
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Selection {
public static void sort(Comparable[] a){
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}//比较v是否小于w
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}//元素交换
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}//单行打印
public static boolean isSorted(Comparable[] a){
for(int i = 1; i < a.length; i++){
if(less(a[i],a[i-1])) return false;
}
return true;
}//判断是否有序
public static void main(String[] args){
String[] a = In.readStrings();
sort(a);
assert isSorted(a);
show(a);
}
}
Ex2_2_11归并排序优化
原目录：算法（第四版） / Ch2 排序 › 2.2归并排序
Ex2_2_11归并排序优化
优化一:加快小数组排序:
递归会使小规模问题中的方法调用过于频繁,可以规定,当lo和hi的差值小于某一阈值时就改用插入排序,只需要替换一句话
//if (hi <= lo) return;
if (hi - lo <= 15) {
Insertion(src, lo, hi);
return;
}
优化二:测试数组是否已经有序:
可以增加一个判断,如果a[mid]<=a[mid+1]则认为数组已经是有序的(以为此时左右两部分已经是排好序的),并跳过merge()方法,此时任意有序子数组算法运行时间就变成了线性的.
if (less(aux[mid], aux[mid + 1])) {
System.arraycopy(aux, lo, src, lo, hi + 1 - lo);//如果已经有序,只需复制过来就好
return;
}
merge(src, aux, lo, mid, hi);
优化三:不将元素复制到辅助数组:
原来merge()方法是将原数组src复制一份到aux后,再将aux的元素按顺序归并回src,但可以优化这一步,节省将数组元素复制到aux的时间(但空间不行),这需要在递归的每层交换输入数组和辅助数组的参数位置
private static void sort(Comparable[] src, Comparable[] aux, int lo, int hi) {
//if (hi <= lo) return;
if (hi - lo <= 15) {
Insertion(src, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(aux, src, lo, mid);//交换角色
sort(aux, src, mid + 1, hi);
if (less(aux[mid], aux[mid + 1])) {
System.arraycopy(aux, lo, src, lo, hi + 1 - lo);//如果已经有序,只需复制过来就好
return;
}
merge(src, aux, lo, mid, hi);//保持原顺序,确保最终是src被排好序
}
完整代码
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class Ex2_2_11 {
private static Comparable[] aux;
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}//比较v是否小于w
public static void sort(Comparable[] src){
aux = src.clone();
sort(src, aux,0, src.length-1);
}
private static void sort(Comparable[] src, Comparable[] aux, int lo, int hi) {
//if (hi <= lo) return;
if (hi - lo <= 15) {
Insertion(src, lo, hi);
return;
}
int mid = lo + (hi - lo) / 2;
sort(aux, src, lo, mid);//交换角色
sort(aux, src, mid + 1, hi);
if (less(aux[mid], aux[mid + 1])) {
System.arraycopy(aux, lo, src, lo, hi + 1 - lo);//如果已经有序,只需复制过来就好
return;
}
merge(src, aux, lo, mid, hi);//保持原顺序,确保最终是src被排好序
}
private static void merge(Comparable[] src, Comparable[] aux, int lo, int mid, int hi){
int i = lo;
int j = mid + 1;
// 少了复制到辅助数组的步骤
// for(int k = lo; k <= hi; k++){
// aux[k] = a[k];
// }
for(int k = lo; k <= hi; k++){
if(i > mid) src[k] = aux[j++];
else if(j > hi) src[k] = aux[i++];
else if(less(aux[j],aux[i])) src[k] = aux[j++];
else src[k] = aux[i++];
}
}
private static void Insertion(Comparable[] a, int lo, int hi){
for(int i = lo+1; i <= hi; i++){
for(int j = i; j > lo && less(a[j],a[j-1]); j--){
exch(a,j,j-1);
}
}
}
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}//元素交换
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}
public static void main(String[] args){
String[] a = In.readStrings();
sort(a);
show(a);
}
}
src和aux交替角色示意以及分治思想
如图所示,只要第一次sort时顺序正确,最终一定对应merge使得src有正确排序(911,910代表不同地址的两个数组)
Review:
- 避免复制到辅助数组:
前提是sort(Comparable[] src)中执行aux = src.clone(),aux[]先进行克隆.在重载sort(Comparable[] src,Comparable[] aux, int lo, int hi)中,aux要作为参数传入,交换传参针对两个sort()和arraycopy(),merge()中aux和src顺序不变.
- 检测是否已有序:
若有序,则使用语句System.arraycopy(aux, lo, src, lo, hi+1-lo).
该函数对于数组是深拷贝(两个引用指向不同的数组对象),对于数组内的对象是浅拷贝(数组对象中存放的不同对象引用实际指向一个堆上的对象).因为操作的传入参数是数组,那么回归本意,效果是深复制.
Ex2_2_17链表归并排序
原目录：算法（第四版） / Ch2 排序 › 2.2归并排序
Ex2_2_17链表归并排序
public class List<Item> {
private class Node{
Item item;
Node next;
}
private Node head;
private Node tail;
private boolean less(Comparable v, Comparable w){ return v.compareTo(w)<0 ;}
private boolean isEmpty(){ return head == null;}
private void add(Item item){
Node current = tail;
tail = new Node();
tail.item = item;
if(isEmpty()) head = tail;
else current.next = tail;
}
private Node ListMerge(Node head){
if(head.next == null) return head;
Node fast = head.next;
Node slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}//slow-fast方法找到中间节点,fast走两步,slow走一步,当fast到末尾,slow即在中间节点
Node leftHead = head;
Node rightHead = slow.next;
slow.next = null;//左边去尾
Node newLeft = ListMerge(leftHead);
Node newRight = ListMerge(rightHead);
Node newList;//newList用来指向归并后数组头结点
Node tail;//tail指向归并中的尾节点
if(less((String)newLeft.item,(String)newRight.item)){
newList = newLeft;
newLeft = newLeft.next;
}else{
newList = newRight;
newRight = newRight.next;
}//确定头结点
tail = newList;
tail.next = null;
//升序归并尾节点
while (newLeft != null || newRight !=null){
if(newLeft == null){
tail.next = newRight;
newRight = null;
}
else if(newRight == null){
tail.next = newLeft;
newLeft = null;
}
else if(less((String)newLeft.item,(String)newRight.item)){
tail.next = newLeft;
newLeft = newLeft.next;
tail = tail.next;
tail.next = null;
}
else{
tail.next = newRight;
newRight = newRight.next;
tail = tail.next;
tail.next = null;
}
}
//返回归并后数组头结点
return newList;
}
public static void main(String[] args){
List<String> list = new List<>();
for(int i = 5; i >= 0; i--){
list.add(Integer.toString(i));
}
List.Node temp = list.ListMerge(list.head);
}
}
要点:
- 关于链表如何找到中间节点:使用fast-slow方法,fast节点初始为head.next,slow节点初始为head,每次fast后移两节点,slow后移一节点,当fast到末尾时,slow就在中间节点.比使用一个int变量标记循环要简单的多
Node fast = head.next;
Node slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}//slow-fast方法找到中间节点,fast走两步,slow走一步,当fast到末尾,slow即在中间节点
- 记得分成左右部分后,左边链表的尾节点.next要赋值为null,否则最终的链表会无限循环
slow.next = null;//左边去尾
- newList节点和tail节点分别标识排序后链表的头和尾
Node newList;//newList用来指向归并后数组头结点
Node tail;//tail指向归并中的尾节点
特点:
- 这是链表排序的最佳方法,因为不需要额外空间且运行时间是线性的.
Review:
- 链表归并排序只是List类下的方法,不要和其他排序算法实现静态方法搞混,此处都为非静态方法;
- 对于链表的归并,一个ListMerge函数既做到排序有完成归并,无需sort()函数;
- 对于
(newLeft == null)和(newRight == null),直接tail.next = newRight和tail.next = newLeft整个半条链表就会连接,不用一个个节点连接;
- 关于newList和tail指针的必要性:之所以分设两个指针,newList为了始终执行归并后链表的头结点,如果只有一个指针,最终无法返回头结点,所以tail起到时刻跟踪尾部节点功能;
tail.next = newRight;//1
newRight = newRight.next;//2
tail = tail.next;//3
tail.next = null;//4
- tail语句顺序问题:如上为最后的while循环,2一定要在3,4前,tail相当于一个遥控器,3,4先执行会使其和newRight遥控器对应一个,这样tail.next也就是newRight.next = null,内存中后面的Node直接变成无引用,语句4可有可无,tail.next总会被覆盖;
Ex2_3_18三取样切分
原目录：算法（第四版） / Ch2 排序 › 2.3快速排序
Ex2_3_18三取样切分
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
public class Ex2_3_18 {
private static void sort(Comparable[] a){
StdRandom.shuffle(a);
sort(a,0,a.length-1);
}
private static void sort(Comparable[] a, int lo, int hi){
if(lo <= hi + 5) { Insertion(a,lo,hi); return;}//以5为阈值进行插入排序
int j = partition(a,lo,hi);
sort(a,lo,j-1);
sort(a,j+1,hi);
}
private static int partition(Comparable[] a, int lo, int hi){
int i = lo;
int j = hi + 1;
while (true){
while (less(a[i++],a[midNum(a,lo,hi)]));
while (less(a[lo],a[j--]));
if(i >= j) break;
exch(a,i,j);
}
exch(a,lo,j);
return j;
}
//三取样,以中位数为切分元素,并把切分元素移动到末端作为标记
private static int midNum(Comparable[] a, int lo, int hi){
if( (a[lo].compareTo(a[lo+1]) * a[lo].compareTo(a[lo+2])) < 0){
exch(a,lo,a.length-1);
return lo;
}
else if( (a[lo+1].compareTo(a[lo]) * a[lo+1].compareTo(a[lo+2])) < 0){
exch(a,lo+1,a.length-1);
return lo+1;
}
else{
exch(a,lo+2,a.length-1);
return lo+2;
}
}
private static void Insertion(Comparable[] a, int lo, int hi){
for(int i = lo+1; i <= hi; i++){
for(int j = i; j>lo && less(a[j],a[j-1]); j--){
exch(a,j,j-1);
}
}
}
private static boolean less(Comparable v, Comparable w){
return v.compareTo(w) < 0;
}//比较v是否小于w
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}//元素交换
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++)
StdOut.print(a[i] + " ");
StdOut.println();
}//单行打印
public static void main(String[] args){
String[] a = In.readStrings();
sort(a);
show(a);
}
}
要点:
- 取样以子数组前三个数的中位值为切分元素: Comparable v = a[midNum(a,lo,hi)];
- midNum方法在返回中位元素索引同时,交换其与末尾元素,这样在partition内循环中,右子数组循环 while (less(a[i++],a[midNum(a,lo,hi)]));就无需边界检查,因为最终一定a[hi]==v退出循环;while (less(a[lo],a[j--]));j减为lo时一定a[lo]==v退出循环
2.4优先队列
原目录：算法（第四版） / Ch2 排序
2.4优先队列
应用程序有时候需要处理有序元素,但不必全部排序,如:为应用程序分配优先级,这时一个合适的数据结构应该支持删除最大元素和插入元素,这种数据结构即为优先队列
2.4.2初级实现
2.4.2.1数组实现(无序)
基于数组下压栈实现,insert()和下压栈的push()一样,实现删除最大元素可以通过内循环将最大元素移动至栈顶后pop()
2.4.2.2数组实现(有序)
在insert()中添加代码使得较大元素右移,删除最大元素只需pop()
2.4.2.3链表实现
以基于链表的下压栈为基础,修改pop()弹出最大元素或修改push()逆序插入后pop()
使用无序序列是解决问题的惰性方法,仅在必要时采取行动,使用有序序列是积极方法,使后续操作更高效
优先队列不同实现运行时间增长数量级
数据结构 插入元素 删除最大元素 有序数组 N 1 无序数组 1 N 堆 logN logN 理想情况 1 1
2.4.3堆的定义
定义:二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组第一个位置)
堆有序:当一棵二叉树的每个节点都大于等于它的两个子结点时,称为堆有序
一棵大小为N的完全二叉树的高度为<=lgN,且当N为2次幂,高度加1
2.4.4堆的算法
使用长度N+1的数组pg[]来表示一个大小为N的堆,不使用pq[0],堆元素放在pq[1]和pq[N]中.
1. 堆的操作会首先进行一些简单改动,打破堆的状态,在遍历堆按要求恢复顺序,此过程为堆的有序化
有序化过程中会有两种情况:
- 当某个结点优先级上升(或是在堆底加入一个新的元素),需要右下至上恢复堆的顺序(上浮swim)
private void swim(int k){
while(k > 1 && less(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
- 当某个结点优先级下降(如根结点被替换为较小结点),需要由上至下恢复堆的顺序(下沉sink)
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;
}
}
2. 插入元素:将新元素加到数组末尾,增加堆的大小并让元素上浮到合适位置
3. 删除最大元素:从数组顶端删除删去最大元素并让数组最后一个元素放到顶端,减小堆的大小并让元素下沉到合适位置
基于堆的优先队列:见算法2.6
2.4.4.7索引优先队列:见Ex2_4_33
2.4.5堆排序(实现见算法2.7)
答疑:
- 优先队列的应用?为什么不把元素排好序后在插入数组?
答:因为有时数据量太大,无法排序,甚至无法装进内存,如果从10亿个元素中选出最大10个,使用优先队列,只需要一个可存储十个元素的优先队列,实时的向后读取数据即可.
- 为什么不直接extends Comparable接口,而要使用泛型?
答:这样delMax()的用例需要将返回值强行转换为某具体类型,应避免在用例中强转;
- 为什么堆排序采用从下至上构造堆,而不是直接向堆添加元素?
答:这样可以提高效率,且代码更少(从下往上构造不用swim()函数),理解算法的难度不一定与它的简洁性或效率有关
Ex2_2_33 索引优先队列
原目录：算法（第四版） / Ch2 排序 › 2.4优先队列
2.4.4.7/Ex2_2_33/34 索引优先队列
很多时候,数据输入流有多个,且数量巨大(10亿个),使用索引可以确定不同输入流,使用优先队列可以确保无论输入多长都可以读入并排序,二者结合即索引优先队列
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
/*
本例使用merge(),基于索引优先队列,将作为命令行输入的多
行字符串(字符串本身升序排好),归并为为一行有序的输出.
*/
public class IndexMinPQ<Key extends Comparable<Key>> {
private Key[] keys;//存放原始数据,顺序不变
private int[] pq;//存放索引的二叉堆,从1开始
private int[] qp;//存放索引的逆序,qp[pq[i]] = pq[pq[i]] = i;
private int N;//PQ中元素数量
/*
----------constructor and Helpers-----------
*/
public IndexMinPQ(int maxN){
keys = (Key[]) new Comparable[maxN+1];
pq = new int[maxN+1];
qp = new int[maxN+1];
//当索引i不在队列中,令qp[i] = -1
for (int i =0; i<= maxN; i++) qp[i] = -1;
}
public boolean isEmpty(){ return N == 0;}
public int size(){ return N;}
//通过返回对索引的查找结果确定是否包含元素
public boolean contains(int k){ return qp[k] != -1; }
/*
----------major function-----------
*/
public void insert(int pri, Key key){
N++;
pq[N] = pri;//保存索引
qp[pri] = N;//保存pq的逆序
keys[pri] = key;
swim(N);
}
public Key min(){ return keys[pq[1]]; }
public int delMin(){
int indexOfMin = pq[1];
exch(1, N--);
sink(1);
keys[pq[N+1]] = null;
qp[pq[N+1]] = -1;
return indexOfMin;//返回indexOfMin,确定输入流
}
private void change(int pri, Comparable key){
keys[pri] = key;
int index = qp[pri];
swim(index);
sink(index);
}
public void delete(int pri){
int index = qp[pri];
exch(index, N--);
swim(index);
sink(index);
keys[pri] = null;
qp[pri] = -1;
}
//此处使用large(),构造小顶堆
private boolean larger(int i, int j){
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
private void exch(int i, int j){
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
public void swim(int k){
while (k > 1 && larger(k/2, k)){
exch(k/2, k);
k = k/2;
}
}
public void sink(int k) {
while (k * 2 <= N) {
int j = k * 2;
if (larger(j, j + 1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
if (!larger(k, j)) break;//比较父子大小
exch(k, j);
k = j;
}
}
public static void merge(In[] streams){
int N = streams.length;
IndexMinPQ<String> pq = new IndexMinPQ<>(N);
for (int i = 0; i < N; i++)
if (! streams[i].isEmpty())
pq.insert(i,streams[i].readString());
while (!pq.isEmpty()){
StdOut.println(pq.min());
int i = pq.delMin();
if (! streams[i].isEmpty())
pq.insert(i,streams[i].readString());
}
}
/*
-----------test function-----------
*/
public static void main(String[] args){
int N = args.length;
In[] streams = new In[N];
for (int i = 0; i < N; i++)
streams[i] = new In(args[i]);
merge(streams);
}
}
算法理解:
关于索引优先队列:
在一般的优先队列中,我们只能通过delMax()访问最大元素,无法直接访问队列中其他元素进行更新或删除,要是建立一个映射关系,让队列中第k个元素操纵着原始数据,队列中针对这种关系排序即可,不改变原始数据结构.实现这种映射控制需要索引(priority)
上述算法中,keys[]即为原始数据结构,只有change()或delete()会改变其中元素,排序对其无影响;pq[]为索引队列,里面依据keys[]中元素堆有序保存了对应的索引,pq[1]即保存了最小元素的索引,比如pq[1]=3,说明keys[3]的元素最小
当要更新元素时,如将keys[5]元素改变,再去维护pq[i]的值,但除非遍历pq[],无法获悉哪个元素pq[i]保存了5,因此必须再添加一个数组,保存与对象相关的队列数组元素下标,qp[pq[i]]=pq[qp[i]]=i;,假如qp[5] = 3,则pq[3]中保存了索引5,这时恢复pq有序,对应恢复qp有序.
关于归并输入流:
假设命令行参数传入m1.txt,m2.txt,m3.txt三个文件,每个文件中有一列升序的字符串,则main函数stream[]是含有N=3的数组,则merge()一开始读取stream[]三个流元素的首个字符串,三个字符串构成索引优先队列,然后delMin(),输出并删除三者最小,再补充删去元素索引对应的下个字符串,知道所有流下的所有字符串都被输出并删除,达成归并不同流并排序的目的.
图示:
算法分析:
大小N的索引优先队列,插入insert(),改变优先级change(),删除delete(),删除最小元素delMin()操作所需比较次数和logN成正比
证明:由堆中所有路径最长为~lgN,可得
N个元素的堆索引优先队列不同操作最坏情况下成本
操作 比较次数增长级 insert() logN change() logN contains() 1 delete() logN min() 1 minIndex() 1 delMin() logN
Review:
- 索引pri是指定key[]中的某个位置,实际元素即key[pri],pq[i]==pri代表此索引堆有序后在堆中第i处,为方便找出key[pri]的索引在pq[]哪个位置,引入qp[],使得qp[pri]=qp[pq[i]]=i;
- sink()中
if (larger(j, j+1) && j < N) j++构造小顶堆找子结点较小者,构造大顶堆找子结点较大者
- 三个边界取等问题
- 构造函数
for (int i=0; i <= maxN; i++),因为contains通过qp[pri]是否为-1判断,qp[maxN]即保存key[maxN]的索引倒序
- swim()
while (k > 1 && larger(k/2, k)),若k>=1,k=1时操作空元素pq[0]
- sink()
while (k*2 <= N),当k恰为2次幂时,层数加一,需要判断下沉.
- insert()在末尾操作只需swim(),change()和delete()涉及中间操作要先swim()在sink()
- merge()实现不唯一
private static void merge(In[] streams){
int N = streams.length;
IndexMinPQ pq = new IndexMinPQ(N);
//读入初始三个值
for (int i = 0; i < N; i++)
if (! streams[i].isEmpty())
pq.insert(streams[i].readString(), i);
StdOut.println(pq.showMin());
int i = pq.delMin();
while (!streams[i].isEmpty()){
pq.insert(streams[i].readString(), i);
StdOut.println(pq.showMin());
i = pq.delMin();
}
}</code></pre>
2.5应用
原目录：算法（第四版） / Ch2 排序
2.5应用
2.5.1将各种数据排序
Java的回调机制使得我们可以将任意实现Comparable接口的数据类型排序,只需重写compareTo(),在其中定义该数据的大小关系.
2.5.1.2指针排序
Java中,指针操作是隐式的,除了原始类型,我们的操作总是数据的引用(指针).指针排序增加了一层间接性.
2.5.1.4廉价的交换
使用引用的一个好处是不必移动整个元素,如果键值很长,交换的成本甚至大于比较的成本.
2.5.1.5-7 Comparable和Comparator
- Comparable
可以看做内比较器,当一个类支持和自己比较时,只需实现此接口,而比较的规则在compareTo()中定义,而Java中很多类都已经实现了此接口并定义了比较规则
以堆优先队列中的less(int i, int j)为例
private boolean less(int i, int j){
return pq[i].compareTo(pq[j]) < 0;
}
由于public class MaxPQ<Key extends Comparable<Key>>且pq为Key对象数组,测试中Key也为基本数据类型,此处直接compareTo().
- Comparator
可以看做外比较器,当一个类不支持和自己比较,或是对已有的内比较规则不满意,或想要有有针对多个不同键的比较方式可以自己构造外比较器
用法
- 编写一个外部类T的内部类xxxComparator并实现Comparator;
- 内部类中实现int compare(T a, T b)方法,根据自己确定的键种类和比较规则,返回int值;
- 外部类编写less(Comparator C, T v, T w)方法,调用c.compare(v, w)由返回值确定大小;
public class Person {
int height;
double weight;
//身高比较器
public class heightComparator implements Comparator<Person>{
public int compare(Person a, Person b){
if(a.height > b.height) return 1;
else if(a.height == b.height) return 0;
else return -1;
}
}
//体重比较器
public class weightComparator implements Comparator<Person>{
public int compare(Person a, Person b){
if(a.weight > b.weight) return 1;
else if(a.weight == b.weight) return 0;
else return -1;
}
}
}
2.5.1.8稳定性
能保留数组中重复元素相对位置的排序算法称为稳定算法
2.5.2 排序算法选择
算法 是否稳定 是否原地排序 时间复杂度 空间复杂度 备注 选择排序 否 是 N² 1 插入排序 是 是 介于N和N² 1 与输入有关 希尔排序 否 是 无法准确描述 1 快速排序 否 是 NlogN lgN 与概率有关 三向快排 否 是 介于N和NlogN lgN 与概率和输入分布有关 归并排序 是 否 NlogN N 堆排序 否 是 NlogN 1
- 与概率有关表示排序的性能保证依赖于随机的切分元素
- 归并排序需要辅助数组aux[]作为额外空间,故非原地排序
- 人们根据不同的递增序列改进希尔排序最坏情况比较次数(N4/3,N5/4...),但实际中递增序列生成函数差别不明显
- 快速排序是最快的通用排序算法
2.5.2.1将原始类型数据排序
一些应用将数字排序,更合理的做法是跳过引用将原始类型数据排序,例如排序double数组和Double数组,前者可以直接交换元素,后者交换引用.对于原始类型数据的排序,后者更低效.
2.5.2.2 Java系统库的排序算法
Java系统库的主要排序方法java.util.Arrays.sort(),根据不同的参数类型,实际上代表了一系列的排序方法:
- 每种原始数据类型有不同的排序方法
- 一个适用于所有实现了Comparable接口的数据类型排序方法
- 一个适用于实现了比较器Comparator的数据类型的排序方法
Java系统对原始数据类型使用(三向切分)快速排序,对引用类型使用归并排序,这些选择暗示着用速度和空间(对原始数据类型)来换取稳定性(对引用类型)
2.5.3 问题归约
归约指的是为解决某个问题而发明的算法应用于另一种问题.
2.5.3.1找出重复元素
小数组可以双层循环遍历查找,但较大数组不行,这时只能排序后记录重复元素个数
2.5.3.2逆序对数/Kendall tau距离
两个排列之间的Kt距离就是两组数列中顺序不同的数对数目,如0316254和1036425间的Kt距离就是4,因为0-1,3-1,2-4,5-4这四对相对顺序不一样.
2.5.3.4第k小元素
一般解决方式可以排序后找到第k个元素,但时间普遍在NlogN级别.
public static Comparable select(Comparable[] a, int k){
StdRandom.shuffle(a);
int lo = 0, hi = a.length-1;
while(hi > lo){
int j = partition(a, lo, hi);
if(j == k) return a[k];
else if(j > k) hi = j-1;
else if(i < k) lo = j+1;
}
return a[k];
}
select()采用归并排序中的partition(),使得a[j]左侧都是小于a[j]的元素,右侧都是大于a[j]的元素,当恰好j==k,问题解决,否则当j>k就继续二分左边数组,反正二分右边数组,最终会只剩下第k个元素,a[k]含有最小的(k+1)个元素.算法的增长级是线性的,假设每次都是二分,(N+N/2+N/4+...)知道找到第k小元素,和显然小于2N,比快排效率要高.
平均来说,基于切分的选择算法运行时间都是线性级别的
3.1 符号表
原目录：算法（第四版） / Ch3 查找
3 查找
3.1 符号表
定义:符号表是一种存储键值对的数据结构:支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到相应的值.
3.1.1 一些规定:
- 重复键:每个键只对应一个值,若新存入键值对和已有键冲突则新值会更新旧值
- 空(null)键:键(key)不能为空
- 空值:值(value)不允许为空
- 删除操作:
延时删除:将键对应值置空,然后一并删除空值键.put(key,null)可作为delete(key)的延时实现;即时删除:即delete()
3.1.2 有序符号表
API
public class ST<Key extends Comparable<Key>, Value>
方法 注释 ST() 创建符号表 void put(Key key, Value val) 存入键值对 Value get(Key key) 获取键key的对应值 void delete(Key key) 删去键值对key boolean contains(Key key) 判断键是否存在 boolean isEmpty() 表是否为空 int size() 表中键值对数量 Key min() 最小的键 Key max() 最大的键 Key floor(Key key) 小于等于key的最大键 Key ceiling(Key key) 大于等于key的最小键 int rank(Key key) 小于key的键个数 Key select(int k) 排名为k的键
- 排名(rank):找出小于指定键的键数;选择(select)找出排名为k的键,即表中比该键小的键数为k.对于0到size()-1的所有i都有
i == rank(select(i))且所有键都满足key = select(rank(key))
3.1.4无序链表中的顺序查找(见算法3.1)
3.1.5有序数组中的二分查找(见算法3.2)
3.3 平衡查找树
原目录：算法（第四版） / Ch3 查找
3.2 二叉查找树(见算法3.3)
3.3 平衡查找树
3.3.1 2-3查找树
定义:2-3查找树为一棵空树或由以下结点构成:
- 2-结点:含有一个键和两个指针,左链2-3子树键值都小于该结点,右链都大于
- 3-结点:含有两个键和三个指针,左链2-3子树键值小于该结点,中链键值介于该结点两个键之间,右链键值都大于该结点
3.3.1.1 查找
2-3查找树的查找和二叉查找树类似,根据键值大小进入子树递归查询,若无结果,返回NULL
3.3.1.2 插入
- 二叉树插入时,先进行查找,若命中key则更新val,否则return一个新结点挂在树的底部.但2-3查找树的插入分为5种操作
- 向2-结点插入新键
如果查找结束于一个2-结点,此时只需把2-结点替换为3-结点,将新键按照左小右大放置
- 向一棵只含有一个3-结点的树(子树)插入新键
此时先临时把新键存入该结点中,使之成为4-结点:含有3个键和4个指针,然后将其转化为3个2-结点,取三个键的中间值作为父结点,剩余两个作左右结点
- 向一个父结点为2-结点的3-结点插入新键
同样构造临时4-结点,然后取出中间值,移动到父结点中,剩余两个值拆开作为父结点的子结点
- 向一个父结点为3-结点的3-结点插入新键
构造临时4-结点,然后取出中间值,移动到父结点中,父结点此时也成为4-结点,则取出中间值作为父2-结点,拆分其余两值作为子结点 - 分解根节点
如果遇到某结点到根结点路径上全是3-结点,那根结点最终会成为4-结点,同理拆分为三个2-结点,树高加一
3.3.1.7 局部变换
- 2-3树插入算法的根本在于这些变化是局部的:除了相关的结点和链接之外不必修改或检查树的其他部分
3.3.1.8 全局性质
- 2-3树算法的局部变换不会影响数的全局有序性和平衡性:任意空链接到根结点的路径长度都是相等的
- 和二叉树比较:二叉树是自上而下生长,但2-3树是由下向上生长
算法分析
2-3树主要关注最坏情况下的性能,因为符号表实现中,一般无法控制用例的输入,对最坏情况的分析才能保证性能
在一棵大小N的2-3树中,查找和插入操作访问的结点不超过lgN个
证明:一棵含有N个结点的2-3树高度在log3N(全是3-结点)到lgN之间(全是2-结点)
B-树
原目录：算法（第四版） / Ch3 查找 › 3.3 平衡查找树
B-树
外部查找成本模型:探查:使用页(计算机中一块连续的数据)的访问次数(无论读写)作为外部查找算法成本模型
B-树
- 定义:作为2-3树拓展,但树由键的副本组成,每个副本关联一条链接,对于M阶B-树
- 每个结点(非根结点)有M/2~M-1对键和链接
- 对比B+树的链接数 = 键数-1
- 根结点个有少于M/2对键和链接,但不能少于2对
- 结构特点:M阶B-树(M为正偶数),可能的构成
- 仅一个外部k-结点
- 若干内部k-结点
- 对根结点:k在[2,M-1],对其他结点k在[M/2,M-1]
- 根结点到每个外部结点路径长度相同
- 结点
- 内部结点:仅保存页相关联键的副本
- 内部结点每个键与一个结点相关联,其子树中的键都大于等于结点关联键,小于内部结点中其余键
- 哨兵键:一个小于所有字符的键,方便查找
- 外部结点:指向实际数据的引用
- 操作
- 查找:被查找键存在于集合,查找结束于外部结点,但内部结点遇到被查键后可判断命中并结束,但总会找到对应外部结点
- 与B+树查找区别:B+树查找无论中途是否遇到,不能保证外部一定有查找键
- 插入:即查找未命中,到达树底,插入新键
- 当空间不足,则需要将其分裂,更新内部结点副本,若内部结点空间也不足,继续分裂直到根结点
B-树的页API: public class Page
返回类型 方法 描述 void add(Key key) 键插入外部页 void add(Page p) 打开内部页,向其中插入条目并关联p和p中最小键 boolean isExternal() 是否为外部页 boolean contains(Key key) key是否在页中 Page next(Key key) 可能含有key的子树 Page spilt() 将较大键移动到新页
- 对于contains()
- 当前为外部页,key在页中----返回true
- 当前为外部页,key不在页中----返回false
- 否则,递归在子树寻找
B-树集合实现
public class BTreeSET<Key extends Comparable<Key>>{
//初始化
private Page root = new Page(true);
public BTreeSET(Key sentinel){ add(sentinel);}
//查找
public boolean contains(Key key){
return contains(root, key);
}
private boolean contains(Page h, Key key){
if(h.isExternal()) return h.contains(key);//判断外部页是否含有键
return contains(h.next(key), key);//子树递归
}
//插入
public void add(Key key){
add(root, key);
if(root.isFull()){//结点已满
Page lefthalf = root;
Page righthalf = root.spilt();//分裂
root = new Page(false);
root.add(lefthalf);
root.add(righthalf);
}
}
public void add(Page h, Key key){
if(h.isExternal()){ h.add(key); return;}//抵达外部页,添加结点
Page next = h.next(key);
add(next, key);//否则继续递归向下
if(next.isFull)//当外部结点已满,向上分裂
h.add(next.spilt());
next.close();//关闭页
}
}
算法分析
- N个元素的M阶B-树一次查找或插入需要logMN~logM/2N次探查
最好情况下生成M-1向完全树,最坏时,根结点只有两个链接指向两棵M/2向完全树
HuffmanTree
原目录：算法（第四版） / Ch3 查找 › 3.3 平衡查找树
HuffmanTree 霍夫曼编码树
Huffman编码:为字母分配代码,代码长度取决于字母的相对使用频率或权重
Huffman树定义:Hf树每个叶子结点对应一个字母,叶子结点的权重就是对应字母的出现频率,它是一颗满树
意义:按照最小外部路径权重建立一棵树.一个叶结点的加权路径长度(WPL)定义为权重乘以深度.具有最小外部路径权重的二叉树就是,对于给定叶结点集合,WPL之和最小的二叉树,权重大的叶结点深度小,权重小的叶结点深度大.
实现
建立n个结点的Hf树.首先创建n个初始的Hf树,每个树只包含单一叶结点,然后取出其中权重最小的两棵树合成一个树,两个叶结点作为新结点的子结点,新结点的权重即为子结点权重和
本例使用基于堆的优先队列创建Hf树
类结构: HuffNode->HuffTree->Heap
Heap类(最小堆)
import edu.princeton.cs.algs4.StdOut;
public class Heap<Key extends Comparable<Key>> {
private int n;//实际大小
private int maxsize;//最大
private Key[] heap;
public Heap(Key[] heap, int n, int maxsize){
this.n = n;
this.maxsize = maxsize;
this.heap = heap;
}
public int size(){ return n;}
private boolean isleaf(int pos){ return pos >= n/2 && pos < n;}
private int lc(int pos){ return 2*pos+1;}
private int rc(int pos){ return 2*pos+2;}
private int parent(int pos){return (pos-1)/2 ;}
//构造堆有序
public void buildHeap(){
for (int i = n/2-1; i >= 0; i--){
sink(i);
}
}
private boolean less(int i, int j){ return heap[i].compareTo(heap[j])<0 ;}
private void swap(int i, int j){
Key temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
}
private void swim(int pos){
while (pos > 1 && less(pos, parent(pos))){
swap(pos, parent(pos));
pos = parent(pos);
}
}
private void sink(int pos){
while (!isleaf(pos)){
int j = lc(pos), rc = rc(pos);
if (less(rc, j) && rc < n) j = rc;
if (less(pos, j)) return;
swap(j, pos);
pos = j;
}
}
public void insert(Key k){
if (size() == maxsize){
StdOut.println("the heap is full");
return;
}
int curr = n++;
heap[curr] = k;
swim(curr);
}
public Key removefirst(){
Key first = heap[0];
swap(0, --n);
if(n != 0){
sink(0);
heap[n] = null;
}
//若heap[0] = null,最后的hufftree也被清空
return first;
}
}
- 和algs4中Heap算法不同之处在于此处数组无空头元素,所以在索引和removefirst()等方法有边界变化;且此处buildHeap()方法针对数组直接构造堆有序
HuffNode(abstract)类
public abstract class HuffNode<T> {
public abstract int weight();
public abstract boolean isLeaf();
}
LeafNode叶子结点类
public class LeafNode<T> extends HuffNode<T> {
private T word;//字符
private int weight;//频度
public LeafNode(T word, int weight){
this.word = word;
this.weight = weight;
}
@Override
public int weight(){ return weight;}
@Override
public boolean isLeaf(){return true;}
}
IntlNode内部结点类
public class IntlNode extends HuffNode {
private int weight;
private HuffNode lc;
private HuffNode rc;
public IntlNode(HuffNode lc, HuffNode rc){
weight = lc.weight()+rc.weight();
this.lc = lc;
this.rc = rc;
}
@Override
public boolean isLeaf(){ return false;}
@Override
public int weight(){ return weight;}
public HuffNode lc(){ return lc;}
public void setLc(HuffNode lc){this.lc = lc; }
public HuffNode rc(){ return rc;}
public void setRc(HuffNode rc){this.rc = rc;}
}
HuffTree类
public class HuffTree<T> implements Comparable<HuffTree<T>>{
private HuffNode<T> root;
//内部结点Hf树
public HuffTree(HuffTree<T> lc, HuffTree<T> rc){
root = new IntlNode(lc.root(), rc.root());
}
//叶结点Hf树
public HuffTree(T word, int wgt){
root = new LeafNode<T>(word, wgt);
}
public int weight(){ return root.weight();}
public HuffNode root(){ return root;}
//实现内部比较方法
@Override
public int compareTo(HuffTree<T> another){
if (root.weight() < another.weight()) return -1;
else if (root.weight() > another.weight()) return 1;
else return 0;
}
}
- implements Comparables接口,实现CompareTo()方法,若泛型HuffTree,则compareTo中参数也必须为HuffTree
- 实际上比较的就是HuffTree的权重和,所以HuffTree类实现接口和compareTo()方法
test类和静态buildHuff()
import edu.princeton.cs.algs4.StdIn;
public class test<T> {
public static void main(String[] args){
HuffTree treeArray[] = new HuffTree[100];
int i = 0;
while (! StdIn.isEmpty()){
treeArray[i++] = new HuffTree(StdIn.readChar(), StdIn.readInt());
StdIn.readChar();
}
buildHuff(treeArray,i);
}
public static HuffTree buildHuff(HuffTree [] treeArray, int count){
Heap forest = new Heap(treeArray, count, count);
forest.buildHeap();
HuffTree temp1, temp2, temp3 = null;
while (forest.size() > 1){
temp1 = (HuffTree) forest.removefirst();
temp2 = (HuffTree) forest.removefirst();
temp3 = new HuffTree(temp1, temp2);
forest.insert(temp3);
}
return temp3;
}
}
- 第一个readChar()读入word,第二个用readInt()读入weight则中间的空格会被忽略,需要额外一次readChar()读取两个word组中间的空格或回车
3.4 散列表
原目录：算法（第四版） / Ch3 查找
3.4散列表
- 定义:一种数组实现的无序符号表,需要使用算术操作将键转化为数组的索引来访问数组中的键值对
- 散列的查找算法:
- 用散列函数将被查找键值转化为数组索引
- 处理碰撞冲突,需要面对多个键散列到相同索引值的情况:拉链法和现象探测法
- 特点: 散列表在时间和空间取得权衡,是实现常数级别查找和插入的无序符号表
3.4.1 散列函数
- 定义:对于一个M个键值对的数组,需要有一种散列函数将任意键转化为数组范围内(0~M-1)的索引
3.4.1.2~5 不同类型键对应不同散列函数
- 正整数:除留余数法,选大小为素数M的数组,对任意正整数k,计算k/M的余数(k%M),就可以控制在0~M-1内,若M非素数,可能无法利用键中所有信息,如:键是十进制数,M是10k,则只能利用键的后k位,如232%100=32, 2531%100=31
- 浮点数:可以将01之间实数乘M变为0M-1范围,但有缺陷,高位的作用更大,最低位对结果影响几乎不计,修正方法:将键表示为二进制数后使用除留余数
- 字符串:将字符串看做大整数后除留余数,Java的charAt()返回一个char值即非负16位整数,若R比任何字符都大,相当于将字符串当作N位R进制值,除以M取余
int hash = 0;
for(int i = 0; i < s.length(); i++){
hash = (R*hash + s.charAt(i)) % M);
}
- 组合键:如日期,day(两位数),month(两位数),year(四位数),类比字符串
int hash = (((day*R + month) % M)*R + year) % M;
3.4.1.6 Java中约定
- Java令所有数据类型都继承了一个返回32bit整数的hashCode()方法,hashCode()方法必须和equals()方法一致,a.equals(b)为true -> a.hashCode()==b.hashCode(),反之不成立两个对象hash值相同对象也可能不同,还需要equals()判断
- 要为自定义数据类型编写散列函数,要同时重写hashCode()和equals(),因为默认散列函数会返回对象的内存地址.但Java为String,Integer,Double,File和URL这类对象都重写了hashCode()
3.4.1.7 将hashCode()返回值转换为索引
我们需要的是索引而非32位整数,因此需要结合hashCode()和除留余数法产生0~M-1索引
private int hash(Key x){
return (x.hashCode() & 0x7fffffff) % M;
}
- 这个方法会将符号位屏蔽,将32位整数变成31位非负整数,然后对M取模,M通常为素数
- Java中取模%操作可能是负数,所以不能直接x.hashCode()%M,且最大的整数Math.abs(x.hashCode())也会返回负值
均匀散列假设:散列函数能均匀且独立得将所有键散步在0~M-1之间
3.4.2 基于拉链法的散列表(算法3.5)
3.4.3 基于线性探测法的散列表(算法3.6)
3.5 应用
原目录：算法（第四版） / Ch3 查找
3.5 应用
3.5.1 符号表的选择
- 散列表:对比BST,散列表代码简单,查找时间最优
- BST:抽象结构简单,无需设计散列函数
- 红黑树:可以保证最坏情况的性能
- 一般情况下,不考虑有效操作,首先选择散列表,其次才是红黑树
符号表渐进性能总结
算法 最坏查找 最坏插入 平均查找命中 平均插入 顺序查找(无序链表) N N N/2 N 二分查找(有序数组) lgN N lgN N/2 BST N N 1.39lgN 1.39lgN 红黑树 2lgN 2lgN 1.00lgN 1.00lgN 拉链法 <lgN <lgN N/(2M) N/M 线性探测法 clgN clgN <1.5 <2.5
3.5.1.3 Java标准库
Java的TreeMap和HashMap分别是基于红黑树和拉链法散列表的符号表
4.1 无向图
原目录：算法（第四版） / Ch4 图
4 图
定义:由一组顶点和一组可连接两个顶点的边组成
4.1 无向图
定义:边只和两个顶点连接
4.1.1 术语表
- 自环:一条连接一个顶点和自身的边
- 平行边:连接同一对顶点的两条边
- 多重图:含有平行边的图
- 简单图:无平行边和自环的图
- 子图:由一幅图的所有边和所依附顶点组成的图(边诱导子图)
- 路径:由边顺序连接的一系列点
- 简单路径(基本道路):无重复顶点的路径
- 简单环(圈):起点终点相同的闭简单路径
- 连通图:任意一个顶点都存一条路径到任意一个顶点
- 树:无环连通图
- 森林:互不相连的树
- 生成树:含有连通图所有顶点且为树的连通图子图
- 生成树森林:所有连通子图生成树的集合
- 树的六个等价命题:对于G=(V,E)
- G不含简单环(圈)且G连通
- G有V-1条边且连通
- G有V-1条边且无简单环
- G连通,但删除任意一条边不再连通
- G无环,但加上任意一条边产生环
- G中任意一对顶点间仅存在一条简单路径
- 密度:已经连接的顶点对占所有可能连接的顶点对比例
- 稀疏/稠密图:图中不同边的数量在/不在顶点总数的一个小常数倍内
- 二分图:可以将所有结点分为两部分的图,每条边连接两点分属不同部分
4.1.2 无向图API:public class Graph
返回类型 方法 描述 Graph(int V) 创建V个顶点的无边图 Graph(In in) 从标准输入in读入一幅图 int V() 顶点数 int E() 边数 void addEdge(int v, int w) 添加边v-w Iterable adj(int v) 和v相邻的所有顶点 String toString() 对象的字符串表示
- 本节所有算法基于adj()抽象
- 第二个构造函数接收2E+2个整数:V,E,E对0~V-1的整数(边)
常用图处理代码
- 计算v的度数
public static int degree(Graph G, int v){
int degree = 0;
for(int w: G.adj(v))
degree++;
return degree;
}
- 计算所有顶点的最大度数
public static int maxDegree(Graph G){
int max = 0;
for(int v = 0; v < G.V(); v++){
if(max < degree(G, v)) max = degree(G, v);
return max;
}
}
- 计算所有结点平均度数
public static double avgDegree(Graph G){
return 2.0*G.E()/G.V();
}
- 计算自环个数
public static int loopNum(Graph G){
int num = 0;
for(int v = 0; v < G.V(); v++){
for(int w: G.adj(v)){
if(w == v) num++;
}
}
return num;
}
4.1.2.1 图的表示
- 需求:
- 必须为可能的各种类型图留出足够空间
- Graph的实例方法实现要快
- 对比:
- 邻接矩阵:使用V*V的boolean矩阵,true表示两点之间有连接,否则为false
- 第一个条件不满足:V²空间在数组极大时不实际
- 边类数组:使用Edge类,含有int v, int w表示两端点
- 第二个条件不满足:adj()的实现需要遍历所有元素
- 邻接表数组:使用一个以顶点为索引的列表数组(如拉链法散列表),每个元素都是和该顶点相邻的顶点列表
4.1.2.2 邻接表数据结构
- 实现:将每个顶点的所有相邻顶点保存在顶点对应元素指向的链表中,链表有Bag(类似Stack),addEdge(int v, int w)时,既要添加v-w也要添加w-v,所以邻接表中每条边出现两次
- 性能特点:
- 空间:和V(数组大小)+E(链表大小)成正比
- 添加一条边的时间为常数:链表插入
- 遍历顶点v相邻结点的时间和v的度数成正比:遍历链表
- 顺序问题:有上述说明可知,邻接表中每个元素对应链表的元素顺序取决于输入顺序和图本身,顺序不同的邻接表可以表示相同的图
Graph数据类型
public class Graph {
private final int V;//顶点数
private int E;//边数
private Bag<Integer>[] adj;//邻接表
public Graph(int V){
this.V = V;
this.E = 0;//构造无边图
adj = (Bag<Integer>[]) new Bag[V];
for (int v = 0; v < V; v++){
adj[v] = new Bag<Integer>();//对象数组单个元素需要实例化
}
}
public Graph(In in){
this(in.readInt());//读取V并执行第一个构造函数
int E = in.readInt();//读取E,边数(非实例变量E)
for(int i = 0; i < E; i++){
int v = in.readInt();
int w = in.readInt();
addEdge(v,w);
}
}
//加入边
public void addEdge(int v, int w){
adj[v].add(w);
adj[w].add(v);
E++;
}
public int V(){ return V; }
public int E(){ return E; }
//返回与v相邻所有点
public Iterable<Integer> adj(int v){
return adj[v];
}
//字符串显示邻接表
public String toString(){
String s = V + " vertices, " + E + " edges\n";
for(int v = 0; v < V; v++){
s += v + ": ";
for (int w: this.adj(v))
s += w + " ";
s += "\n";
}
return s;
}
}
4.1.2.3 图处理算法设计模式
- 图的实现和图的处理应该分离:构造一副图,将图作为参数传递给某个算法的类
4.1.3 深度优先搜索(算法4.1)
4.1.4 寻找路径(算法4.1)
4.1.5 广度优先搜索(算法4.2)
4.1.6 连通分量(算法4.3)
4.2 有向图
原目录：算法（第四版） / Ch4 图
4.2 有向图
定义:边是单向的,每条边连接的两个顶点是一个有序对,邻接性也是单向的
4.2.1 术语表
- 有向路径
- 有向环
4.2.2 有向图API:public class Digraph
返回类型 方法 描述 Digraph(int V) 创建V个顶点的无边有向图 Digraph(In in) 从标准输入in读入一幅有向图 int V() 顶点数 int E() 边数 void addEdge(int v, int w) 添加边v->w Iterable adj(int v) v指向的所有顶点 Digraph reverse() 该图的反向图 String toString() 对象的字符串表示
4.2.2.1 有向图的表示:邻接表
Digraph数据类型
import edu.princeton.cs.algs4.In;
public class Digraph {
private final int V;//点集
private int E;//有向边集
private Bag<Integer>[] adj;
public Digraph(int V) {
this.V = V;
E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for (int i = 0; i < V; i++)
adj[i] = new Bag<>();
}
public Digraph(In in){
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++){
int v = in.readInt();
int w = in.readInt();
addEdge(v, w);
}
}
public int V() { return V; }
public int E() { return E; }
public void addEdge(int v, int w) {
adj[v].add(w);
E++;
}
public Iterable<Integer> adj(int v) { return adj[v]; }//返回V指向所有结点
public Digraph reverse() {
Digraph R = new Digraph(V);
for (int v = 0; v < V; v++)
for (int w : adj(v))
R.addEdge(w, v);
return R;
}
}
4.2.3 有向图中的可达性(算法4.4)
4.2.4 环和有向无环图(算法4.5)
4.2.5 有向图的强连通性(算法4.6)
4.2.6 总结
- 4.2中接触到的各种有向图算法只有一种非基于DFS
问题 解决方法 参考 单点/多点可达性 DirectedDFS 算法4.4 单点有向路径 DepthFirstDirectedPaths 算法4.1(换名) 单点最短有向路径 BreadthFirstDirectedPath 算法4.2(换名) 有向环检测 DirectedCycle 算法4.5 深度优先顶点排序 DirectedFirstOrder 算法4.5 优先级调度问题 Topological 算法4.5 拓扑排序 Topological 算法4.5 强连通性 KosarajuSCC 算法4.6 顶点对可达性 TransitiveClosure 算法4.6
4.3 最小生成树
原目录：算法（第四版） / Ch4 图
4.3 最小生成树
定义:图的生成树是含有所有顶点的无环连通子图,加权图的最小生成树(MST)是一棵权值最小的生成树
约定
- 只限于连通图:由定义,最小生成树只存在于连通图
- 权值可为0或者负数
- 所有边的权重都不同,否则MST不唯一
4.3.1 原理
4.3.3.1 切分定理
切分:即把图所有顶点分成两个非空且不重叠的部分
横切边即连接这两部分,两端各属于不同部分的边
切分定理:加权图中,给定任意的切分,其横切边中权重最小者一定属于图的最小生成树
证明:反证法:设T为图的最小生成树,e为权重最小的横切边且不在T中,由树的性质,T中加入一条边必定成环,则连接e,此时环中至少含有另一条横切边f,而f权重大于e,则删去f保留e,的到更小的树,与前提矛盾
4.3.3.2 最小生成树的贪心算法
算法:使用切分定理:V个顶点的任意加权连通图中:在一种切分下,选出权重最小横切边,一定含于MST中;另一种切分下,同样操作;最终当选出V-1条不同的横切边时,即为MST
4.3.2 加权无向图的数据类型:加权边Edge->加权无向图EdgeWeightedGraph
加权边API:public class Edge implements Comparable
返回类型 方法 描述 Edge(int v, int w, double weight) 构造函数 double weight() 边的权重 int either() 两端点之一 int other() 另一个端点 int compareTo(Edge that) 权重比较 String toString() 字符串化
public class Edge implements Comparable<Edge>{
private final int v;
private final int w;
private final double weight;
public Edge(int v, int w, double weight){
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight(){ return weight;}
public int either(){ return v; }//一个端点
public int other(int vertex){//对侧端点
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new RuntimeException("Inconsistent edge");
}
public int compareTo(Edge that){//自然比较
if (this.weight() < that.weight()) return -1;
else if(this.weight() > that.weight()) return 1;
else return 0;
}
//每条边输出格式:点-点 权重
public String toString(){
return String.format("%d-%d %.2f",v,w,weight);
}
}
加权无向图API:public class EdgeWeightedGraph
返回类型 方法 描述 EdgeWeightedGraph(int V) 创建V结点的空图 EdgeWeightedGraph(In in) 从输入流建图 int V() 顶点数 int E() 边数 void addEdge(Edge e) 添加边e Iterable adj(int v) 与v关联所有边 Iterable edges() 图中所有边 String toString() 字符串化
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;
public class EdgeWeightedGraph {
private final int V;//总点数
private int E;//总边数
private Bag<Edge>[] adj;//邻接表
public EdgeWeightedGraph(int V){
this.V = V;
this.E = 0;
adj = (Bag<Edge>[])new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<>();
}
public EdgeWeightedGraph(In in){
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++)
addEdge(new Edge(in.readInt(),in.readInt(),in.readDouble()));
}
public void addEdge(Edge e){
int v = e.either(), w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public int V(){ return V;}
public int E(){ return E;}
//与v关联边
public Iterable<Edge> adj(int v){return adj[v];}
//所有边
public Iterable<Edge> edges(){
Bag<Edge> b = new Bag<>();
for (int v = 0; v < V; v++)
for (Edge e: adj(v))
//忽略自环
if (e.other(v) > v) b.add(e);
return b;
}
public String toString(){
String s = V + " vertices, " + E + " edges\n";
for (int v = 0; v < V; v++){
s += v + ": ";
for (Edge e:adj(v))
s += e + " ";
s += "\n";
}
return s;
}
public static void main(String[] args){
In in = new In(args[0]);
EdgeWeightedGraph G;
G = new EdgeWeightedGraph(in);
StdOut.print(G);
}
}
- 每条边在表中出现两次:和Graph每个顶点出现两次一样,一个Edge在addEdge时,需要给adj[v]和adj[w]同时add
- 平行边:EWG中运行保留权重不一样的平行边
- 自环:EWG中运行存在自环,但edges()未考虑自环
- 使用Edge辅助类的代价:
- 每个邻接表结点是指向Edge对象的引用,还要冗余信息:每个adj[v]都会保存v
- 使用对象本身的开销
- 一个Edge对象需要创建两个引用来指向
4.3.3 最小生成树API和用例(算法4.7)
4.3.4 Prim算法(算法4.7)
4.3.5 Prim算法即时实现(算法4.7)
4.3.6 Kruskal算法(算法4.8)
4.3.7 总结
- 最小生成树算法总结:
算法 空间 时间 延时Prim E ElogE 即时Prim V ElogV Kruskal E ElogE
4.4 最短路径
原目录：算法（第四版） / Ch4 图
4.4 最短路径
模型:加权有向图
问题:单点最短路径:给定加权有向图和s,求"s到给定v是否存在有向路径,若有,找出权重最小的"
4.4.1最短路径性质
- 并非所有顶点都可达
- 最短路径不一定唯一
- 最短路径树:SPT,包含s到所以可达顶点的最短路径
4.4.2 加权有向图
加权有向边API:public class DirectedEdge
返回类型 方法 描述 DirectedEdge(int v, int w, double weight) double weight() 边权重 int from() 边的顶点 int to() 边指向的顶点 String toString() 字符串化
public class DirectedEdge {
private final int v;//起
private final int w;//终
private final double weight;
public DirectedEdge(int v, int w, double weight){
this.v = v;
this.w = w;
this.weight = weight;
}
public double weight(){ return weight;}
public int from(){ return v; }
public int to(){ return w; }
public String toStirng(){
return String.format("%d->%d %.2f", v, w, weight);
}
}
加权有向图API:public class EdgeWeightedDigraph
返回类型 方法 描述 EdgeWeightedDigraph(int V) 创建V个顶点的无边图 EdgeWeightedDigraph(In in) 从标准输入in读入一幅有向图 int V() 顶点数 int E() 边数 void addEdge(DirectedEdge e) 添加边e Iterable adj(int v) v指向的所有顶点 Iterable edges() 图中所有边 String toString() 对象的字符串表示
import edu.princeton.cs.algs4.In;
public class EdgeWeightedDigraph {
private final int V;//顶点数
private int E;//边总数
private Bag<DirectedEdge>[] adj;//邻接表
public EdgeWeightedDigraph(int V){
this.V = V;
this.E = 0;
adj = (Bag<DirectedEdge>[])new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<>();
}
public EdgeWeightedDigraph(In in){
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++){
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
DirectedEdge e = new DirectedEdge(v,w,weight);
addEdge(e);
}
}
public void addEdge(DirectedEdge e){
adj[e.from()].add(e);
}
public int V(){ return V;}
public int E(){ return E;}
public Iterable<DirectedEdge> adj(int v){ return adj[v];}
public Iterable<DirectedEdge> edges(){
Bag<DirectedEdge> bag = new Bag<>();
for (int v = 0; v < V; v++)
for (DirectedEdge e: adj[v])
bag.add(e);
return bag;
}
}
最短路径API:public class SP
返回类型 方法 描述 SP(EdgeWeightedDigraph G, int s) double distTo(int v) s->v距离,不存在为∞ boolean hasPathTo(int v) 是否存在s->v Iterable pathTo(int v) s->v的路径,不存在为null
- 数据结构选择
- SPT中的边:顶点索引的DirectedEdge数组edgeTo[]
- 到起点距离: distTo[]
松弛(relaxation)
- 边的松弛:放松v->w,即检查s->w是否经s->v->w:若distTo[v]+(v->w)e.weight()<distTo[w],则v->w失效,更新edgeTo[w]为由s->w为v->w
private void relax(DirectedEdge e){
int v = e.from(), w = e.to();
if(distTo[w] > distTo[v] + e.weight()){
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
- 顶点的松弛:放松从一个顶点指出的所有边
private void relax(EdgeWeightedDigraph G, int v){
for(DirectedEdge e:G.adj(v)){
int w = e.to();
if(distTo[w] > distTo[v] + e.weight()){
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
}
}
}
SP中的查询方法
private double distTo(int v){ return distTo[v]};//s->v的距离
public boolean hasPathTo(int v){ return distTo[v] < Double.POSITIVE_INFINITY;}
public Iterable<DirectedEdge> pathTo(int v){
Stack<DirectedEdge> stack = new Stack<>();
for(DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()])
stack.push(e);
return stack;//后根入栈
}
SP算法理论基础
- 最短路径的最优性条件
- 命题:当且仅当从v到w的任意一条边满足distTo[w]<=distTo[v]+e.weight()时(即不存在有效边时),distTo[]中都为SP的长度
证明:书P420
- 通用最短路径算法:
- 将distTo[s]初始化为0,其他都初始化为∞
- 放松G中任意边,知道不存在有效边
- 对任意s可达的w,操作过后,distTo[w]即为s到w的最短路径长度,且edgeTo[w]为路径上最后一条边
- 通用算法没有指定放松顺序
4.4.4 Dijkstra算法(算法4.9)
4.4.5 无环加权有向图的最短路径算法(算法4.10)
4.4.6 一般加权有向图的最短路径问题(算法4.11)
4.4.7 总结
- 不同最短路径算法总结
算法 局限 时间(最坏) 最好 空间 优势 Dijkstra即时版本 边权必须为正 ElogV ElogV V 最坏时保证性能 利用Topo排序 只适合无环加权有向图 E+V E+V V 无环图最优算法 基于队列Bellman-Ford 不能存在负权重环 E+V VE V 应用广泛
图算法总结
原目录：算法（第四版） / Ch4 图
5.1 字符串排序
原目录：算法（第四版） / Ch5 字符串
5 String
本章内容
- 5.1/5.2: 字符串排序
- 5.3: 子字符串查找-KMP算法
- 5.4: 正则表达式
5.0.1 Java中关于String类的规定
- String对象由一系列char组成,char为16bits
- 不可变性:String对象不可变,因此可用于赋值,作为参数或返回
- 子字符串:Java中substring()方法实现了提取子字符串,可在常数时间完成,原理参考下图
- 字符数组Char[]和String的比较
操作 字符数组 字符串 声明 Char[] a String s 访问字符 a[i] s.charAt(i) 字符串长度 a.length s.length() 转换 a=s.toCharArray() s=new String(a)
5.1 字符串排序
5.1.1 键索引计数
- 描述:不同字符串按组分类,组的编号是一个较小的整数,算法根据编号对字符串排序
- 适用情况:小整数键索引的字符串
- 步骤:
- 频度统计(N个字符串)
for(i=0; i<N; i++)
count[a[i].key()+1]++;
- 频度->索引
for(int r=0; r<R; r++)
count[r+1] += count[r];
- 数据分类:字符串移动到辅助数组中排序
for(int i=0; i<N; i++)
aux[count[a[i].key()]++] = a[i];
- 写回
for(int i=0; i<N; i++)
a[i] = aux[i];
实现
int N = a.length;
String[] aux = new String[N];
int[] count = new int[R+1];
//四个步骤....
算法分析
- 命题:键索引计数法排序N个键值为0-R-1间整数的元素需要访问数组11N+4R+1次
证明:数组初始化是访问N+R+1次,步骤一:2N次;步骤二:2R次;步骤三:3N次,步骤四:2N次
5.1.2 低位优先的字符串排序(LSD)(算法5.1)
5.1.3 高位优先的字符串排序(MSD)(算法5.2)
5.1.4 三向字符串快速排序(算法5.3)
5.3 子字符串查找
原目录：算法（第四版） / Ch5 字符串
5.3 子字符串查找
5.3.1 常见查找算法
- 暴力算法
- KMP算法
- Boyer-Moore算法
- Rabin-Karp算法
5.3.2 暴力子字符串查找
算法描述
- 使用字符指针i跟踪文本,j跟踪模式,当首字母匹配后,i不在增加,只是j变化
实现
public static int search(String pat, String txt){
int M = pat.length();
int N = txt.length();
for (int i = 0; i < N; i++){
int j;
for (j = 0; j < M; j++){
if (pat.charAt(j) != txt.charAt(i))
break;
}
if (j == M) return i;//找到匹配
}
return N;//未找到匹配
}
算法分析
- 最坏情况:暴力算法需要~NM次字符比较
证明:最坏假设模式是AAAB,M=4,文本是AAAAAAAAAB,N=10,对于N-M+1=7个可能匹配位置,AAAB中每个字符都要和文本比对到B,为4次,攻M(N-M+1)=28次比较,一般M<<N,则成本~NM
- 实际情况:暴力算法运行和N+M成正比
暴力算法改进(显式回退)
算法描述
- 同样使用i,j跟踪模式和文本,但i始终增加,相当于初始算法的i+j指向已经匹配过的字符,若匹配失败,则i回退至本次匹配起始位置下一个字符,j指回模式开头
public static int searchPlus(String pat, String txt){
int i, M = pat.length();
int j, N = txt.length();
for (i = 0, j = 0; i < N && j < M; i++){
if (pat.charAt(j) == txt.charAt(i)) j++;
else {i -= j; j = 0;}
}
if (j == M) return i-M;//找到匹配
else return N;//未找到
}
算法5.6 KMP算法
算法5.7 Boyer-Moore算法
算法5.8 Rabin-Karp算法
5.4 正则表达式
原目录：算法（第四版） / Ch5 字符串
5.4 正则表达式
概述:正则表达式使用类似KMP中的抽象自动机来描述三种基本操作"连接,或,闭包",由三种基本操作来描述"模式",从而进行匹配
5.4.1 描述模式
- 语言:字符串集合
- 模式:语言的详细说明
- 连接操作: 当写出AB,即表示语言{AB},由AB连接而成
- 或操作:或预算"|"将两种选择包含在一种语言,A|B表示{A,B}
- 闭包操作:闭包允许模式的部分重复任意次数(含有0次),将"*"放在模式后,A*为{E,A,AA...}
- 优先级:闭包>连接,AB*表示{A,AB,ABB...}
- 空字符串E(Epsilon),存在于所有文本字符串
- 括号:用于改变优先级:(AB)*表示{E,AB,ABAB...}
5.4.2 缩略写法
- 字符集描述符
- 闭包简写
- 应用
5.4.3 非确定优先状态自动机NFA
- 因为或与闭包的存在,无法确定模式是否匹配,这是需要非确定自动,可以针对多种匹配可能猜出正确转换
5.4.4 NFA与DFA对比
- NFA特点
- 长M的regex每个字符在对于NFA中有且只有一个对应状态,起始为0,最终为接收状态
- 字母表中字符对应状态都有出边,指向下一个字符状态(黑边)
- 元字符"(,),|,*"对应状态至少一条出边(红边)可指向任意状态
- 状态出边可能不只一条,但黑边(指向下个字符)只有一条
- 约定所有模式都含在括号内
- 不同
- DFA字符是转换,NFA中字符是状态
- DFA只需读取txt中部分字符就能抵达停止状态,NFA需要一直读取到文本结束判断是否到接收状态
- 转换
- 匹配转换:当前状态字符和文本字符匹配,则由黑边进入下一状态
- E转换:自动机通过红边进入下一状态而无需接收字符,即与空字符串E匹配
5.4.5 模拟NFA运行
- 自动机表示
- 表达式本身和匹配转换:char[] re,当re[i]存在,则存在i到i+1匹配转换
- E转换: 有向图G,红边即连接两顶点的有向边
- NFA模拟和可达性
- 初始化:查找0状态通过E转换可达的所有状态初始化集合
- 检查匹配: 对集合每个状态检查是够与第一个字符匹配,检查完毕,则得到与第一个字符匹配的状态集合
- 依次输入其余字符,重复以上步骤,直到读取完毕
- 最终结果
- 状态集合有接受状态:匹配成功
- 不含接受状态:匹配不存在
- 对((A*B|AC)D)的NFA输入AABD模拟
//NFA模拟
public boolean recognizes(String txt){
Bag<Integer> pc = new Bag<>();
DirectedDFS dfs = new DirectedDFS(G,0);//有向图多点可达性,0开始的E转换
for (int v = 0; v < G.V(); v++)
if (dfs.marked(v)) pc.add(v);//初始化
for (int i = 0; i < txt.length(); i++){
Bag<Integer> match = new Bag<>();//匹配状态集合
for (int v: pc) {
if (v < M)//txt未读取完毕
if (re[v] == txt.charAt(i) || re[v] == '.')//匹配或通配
match.add(v + 1);
}
pc = new Bag<>();
dfs = new DirectedDFS(G,match);//用当前状态集合重建dfs
for (int v = 0; v < G.V(); v++)
if (dfs.marked(v)) pc.add(v);
}
for (int v: pc) if (v == M) return true;//最终集合有接受状态
return false;
}
算法分析
- 模拟长M的regex是否可识别长N的txt,最坏情况下颌MN成正比
证明:对txt中每个字符,会便利一个大小不超过M的集合并在E转换有向图中深度优先搜索,且图中边数不会超过2M
5.4.6 构造NFA
- 连接:无需其余处理,匹配转换就是连接关系
- 括号:将regex中左括号索引入栈,遇到右括号时,左括号弹出
- 闭包操作
- 单个字符后:在字符和状态间添加两条相互指向的E转换
- 右括号后:在对应左括号和间添加相互执行的E转换
- 或操作:如(A|B),添加两条E转换
- 左括号指向B中第一个字符
- |指向右括号
- 将(和|都压入栈中,遇到)时所需的(和|都会在栈顶,分别对应不同匹配
public class NFA {
private char[] re;//regex本身/匹配转换
private Digraph G;//epsilon转换
private int M;//状态数量
//NFA构造
public NFA(String regexp){
Stack<Integer> ops = new Stack<>();
re = regexp.toCharArray();//String转换为char[]
M = re.length;
G = new Digraph(M+1);
for (int i = 0; i < M; i++){
int lp = i;
if (re[i] == '(' || re[i] == '|') ops.push(i);//压入(和|
else if (re[i] == ')')//右括号
{
int or = ops.pop();
if (re[or] == '|'){//若弹出|
lp = ops.pop();//继续弹出(
G.addEdge(lp, or+1);//左括号->|后第一个字符
G.addEdge(or, i);//|->右括号
}
else lp = or;//无|,则只弹出(
}
//括号处理在闭包处理之前,否则lp的值总是i
if (i < M-1 && re[i+1] == '*'){//闭包处理
G.addEdge(lp, i+1);
G.addEdge(i+1, lp);
}
if (re[i] == '(' || re[i] == '*' || re[i] == ')')//添加(,),*后的E转换
G.addEdge(i, i+1);
}
}
//NFA模拟
public boolean recognizes(String txt){}
}
算法分析
- 构造长度M的regex对应NFA所需时间空间在最坏情况下和M成正比
证明:对regex中每个字符,最多添加三条E转换(*),且可能执行一到两次栈操作
- 一般用例
子字符串查找总结
原目录：算法（第四版） / Ch5 字符串
子字符串查找总结
源图片已失效：5-String/mindmap.png
各种字符串查找算法比较
