第四部分 高级设计和分析技术

​ 设计和分析高效算法的三种重要技术：动态规划、贪心算法和摊还分析。

​ 动态规划通常用来解决最优化间题，在这类间题中，我们通过做出一组选择来达到最优解。在做出每个选择的同时，通常会生成与原间题形式相同的子间题。当多于一个选择子集都生成相同的子间题时，动态规划技术通常就会很有效，其关键技术就是对每个这样的子问题都保存其解，当其重复出现时即可避免重复求解。

​ 贪心算法通常用于最优化间题，我们做出一组选择来达到最优解。贪心算法的思想是每步选择都追求局部最优。贪心方法对很多间题都能求得最优解，而且速度比动态规划方法决得多。但是，我们并不总能简单地判断出贪心算法是否有效。

​ 我们使用摊还分析方法分析一类特定的算法，这类算法执行一组相似的操作组成的序列。摊还分析并不是通过分别分析每个操作的实际代价的界来分析操作序列的代价的界，而是直接分析序列整体的实际代价的界。这种方法的一个好处是，虽然某些操作的代价可能很高，但其他很多操作的代价可能很低。换旬话说，很多操作的运行时间都会在最坏清况时间之内。摊还分析并不仅仅是一种分析工具，它还是一种思考算法设计的方式，因为算法设计和算法运行时间的分析常常是交织在—起的。

第十五章 动态规划

​ 分治方法将问题划分为互不相交的子问题，递归地求解子问题，再将它们的解组合起来，求出原问题的解。与之相反，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）动态规划算法对每个子子问题只求解一次，将其解保存在一个表格中，从而无需每次求解一个子子问题时都重新计算，避免了这种不必要的计算工作。

​ 动态规划方法通常用来求解最优化问题(optimization problem) 。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解, 而不是最优解, 因为可能有多个解都达到最优值。

设计一个动态规划算法：

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值。
3. 计算最优解的值，通常采用自底向上的方法。
4. 利用计算出的信息构造一个最优解。

15.1 钢条切割

​ 给定一段长度为n 英寸的钢条和一个价格表p_i (i=l, 2, …, n),求切割钢条方案，使得销售收益 r_n最大。注意，如果长度为 n 英寸的钢条的价格 p_n 足够大，最优解可能就是完全不需要切割。

示例 1：

输入：n = 7, p = [1,5,8,9,10,17,17]
输出：18
解释：最优切割长度为 [1,6]或[2,2,3]，价格均为18。

示例 2：

输入：n = 10, p = [1,5,8,9,10,17,17,20,24,30]
输出：30
解释：最优切割长度为 [10]，即不切割，价格为30。

问题解析

​ 对于 r_n(n \ge 1), 我们可以用更短的钢条的最优切割收益来描述它：

​ 第一个参数 p_n 对应不切割，直接出售长度为 n 英寸的钢条的方案。其他 n-1个参数对应另外 n-1 种方案：对每个 i=1, 2, …, n-1, 首先将钢条切割为长度为 i 和 n-i 的两段，接着求解这两段的最优切割收益 r_i 和 r_{n-i} （每种方案的最优收益为两段的最优收益之和）。由千无法预知哪种方案会获得最优收益，我们必须考察所有可能的i, 选取其中收益最大者。如果直接出售原钢条会获得最大收益，我们当然可以选择不做任何切割。

​ 我们将钢条从左边切割下长度为i 的一段，只对右边剩下的长度为 n-i 的一段继续进行切割（递归求解），对左边的一段则不再进行切割。这样第一段的长度为n, 收益为 p_n, 剩余部分长度为 0, 对应的收益为 r_n=0 。等价公式为：

自顶向下递归算法

CUT-ROD(p, n)
  if n==0
    return 0
  q = -oo
  for i = 1 to n
    q = max(q, p[i] + CUT-ROD(p, n-i))
  return q

问题：当这个过程递归展开时，它所做的工作量（用n 的函数的形式描述）会爆炸性地增长。大概每当将 n 增大1, 程序运行时间差不多就会增加1 倍。

使用动态规划方法求解

​ 动态规划方法是付出额外的内存空间来节省计算时间，是典型的时空权衡例子。而时间上的节省可能是非常巨大的：可能将一个指数时间的解转化为一个多项式时间的解。如果子问题的数量是输入规模的多项式函数，而我们可以在多项式时间内求解出每个子间题，那么动态规划方法的总运行时间就是多项式阶的。

动态规划有两种等价的实现方法：

• 第一种方法称为带备忘的自顶向下法。此方法仍按自然的递归形式编写过程，但过程会保存每个子问题的解（通常保存在一个数组或散列表中）。当需要一个子问题的解时，过程首先检查是否已经保存过此解。如果是，则直接返回保存的值，从而节省了计算时间；否则，按通常方式计算这个子问题

  Java 实现

  public int memoZedCutRod(int n, int[] p) {
      if (n < 1 || n > p.length) {
          System.out.printf("expected 1 <= size <= %d but got %d.\n", p.length, n);
          return -1;
      }
  
      int[] r = new int[n + 1];
      Arrays.fill(r, Integer.MIN_VALUE);
      return memoizedCutRodAux(n, p, r);
  }
  
  public int memoizedCutRodAux(int n, int[] p, int[] r) {
      if(r[n] >= 0) return r[n];
      int q = Integer.MIN_VALUE;
      if (n == 0){
          q = 0;
      }else{
          for (int i = 1; i <= n; i++) {
              q = Math.max(q, p[i - 1] + memoizedCutRodAux(n - i, p, r));
          }
      }
      r[n] = q;
      return q;
  }
  

• 第二种方法称为自底向上法。这种方法一般需要恰当定义子问题”规模"的概念，使得任何子问题的求解都只依赖于“更小的“子问题的求解。因而我们可以将子问题按规模排序，按由小至大的顺序进行求解。当求解某个子问题时，它所依赖的那些更小的子间题都已求解完毕，结果已经保存。每个子问题只需求解一次，当我们求解它（也是第一次遇到它）时，它的所有前提子问题都已求解完成。

​ 两种方法得到的算法具有相同的渐近运行时间，仅有的差异是在某些特殊情况下，自顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，自底向上方法的时间复杂性函数通常具有更小的系数。

备忘录算法

MEMO-ZED-CUT-ROD(p,n)
  let r[0.. n] be a new array
  for j = 0 to n
    r[i] = -oo
  return MEMOIZED-CUT-ROD-AUX(p,n,r)

MEMOIZED-CUT-ROD-AUX(p,n,r)
  if r[n] >= 0
    return r[n]
  if n == 0
    q = 0
  else
    q = -oo
    for i = 1 to n
      q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p,n-i,r))
  r[n] = q
  return q

==Java 实现==

public int memoZedCutRod(int n, int[] p) {
    if (n < 1 || n > p.length) {
        System.out.printf("expected 1 <= size <= %d but got %d.\n", p.length, n);
        return -1;
    }

    int[] r = new int[n + 1];
    Arrays.fill(r, Integer.MIN_VALUE);
    return memoizedCutRodAux(n, p, r);
}

public int memoizedCutRodAux(int n, int[] p, int[] r) {
    if(r[n] >= 0) return r[n];
    int q = Integer.MIN_VALUE;
    if (n == 0){
        q = 0;
    }else{
        for (int i = 1; i <= n; i++) {
            q = Math.max(q, p[i - 1] + memoizedCutRodAux(n - i, p, r));
        }
    }
    r[n] = q;
    return q;
}

自底向上算法

BOTTOM-UP-CUT-ROD(p,n)
  let r[0.. n] be a new array
  r[0] = 0
  for j = 1 to n
    q = -oo
    for i = 1 to j
      q = max(q, p[i]+r[j-i])
    r[j] = q
  return r[n]

==Java 实现==

// 1 <= n <= p.length
public int bottomUpCutRod(int n, int[] p) {
    if (n < 1 || n > p.length) {
        System.out.printf("expected 1 <= size <= %d but got %d.\n", p.length, n);
        return -1;
    }

    int[] r = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int tmp = Integer.MIN_VALUE;
        for (int j = 1; j <= i; j++) {
            tmp = Math.max(tmp, p[j - 1] + r[i - j]);
        }
        r[i] = tmp;
    }
    return r[n];
}

算法分析

​ 自底向上算法和自顶向下算法具有相同的渐近运行时间。过程BOTTOM-UP-CUT-ROD 的主体是嵌套的双重循环，内层for 循环的迭代次数构成一个等差数列，不难分析过程的运行时间为 \Theta(n^2) 。自顶向下的MEMOIZED-CUT-ROD 的运行时间也是 \Theta(n^2)。

子问题图

​ 子问题图G=(V, E) 的规模可以帮助我们确定动态规划算法的运行时间。由于每个子问题只求解一次，因此算法运行时间等千每个子问题求解时间之和。通常，一个子问题的求解时间与子问题图中对应顶点的度（出射边的数目）成正比，而子问题的数目等千子问题图的顶点数。因此，通常情况下，动态规划算法的运行时间与顶点和边的数量呈线性关系。

重构解

​ 扩展动态规划算法，使之对每个子问题不仅保存最优收益值，还保存对应的切割方案。利用这些信息，我们就能输出最优解。

EXTENDED-BOTIOM-UP-CUT-ROD(p,n)
  let r[0.. n] and s[0.. n] be new arrays
  r[0] = 0
  for j= 1 to n
    q = -oo
    for i = 1 to j
      if q < p[i] + r[j-i]
        q = p[i] + r[i-i]
        r[j] = i
    r[j] = q
  return r and s

PRINT-CUT-ROD-SOLUTION(p,n)
  (r, s) = EXTENDED-BOTIOM-UP-CUT-ROD(p,n)
  while n > 0
    print s[n]
    n = n - s[n]

==Java 实现==

public int extendBottomUpCutRod(int n, int[] p) {
    if (n < 1 || n > p.length) {
        System.out.printf("expected 1 <= size <= %d but got %d.\n", p.length, n);
        return -1;
    }

    int[] r = new int[n + 1];
    int[] s = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        int tmp = Integer.MIN_VALUE;
        for (int j = 1; j <= i; j++) {
            if (tmp < p[j - 1] + r[i - j]) {
                tmp = p[j - 1] + r[i - j];
                s[i] = j - 1;
            }
        }
        r[i] = tmp;
    }
    printCutRodSolution(n, s);

    return r[n];
}

public void printCutRodSolution(int n, int[] s) {
    while (n > 0) {
        System.out.print((s[n] + 1) + ",");
        n = n - (s[n] + 1);
    }
    System.out.println();
}

15.2 矩阵链乘法

​ 给定一个n 个矩阵的序列（矩阵链）\left<A_1, A_2, ...， A_n \right>，我们希望计算它们的乘积： A_1A_2 \cdots A_n ，由于矩阵乘法满足结合律，因此任何加括号的方法都会得到相同的计算结果。

​ 矩阵链乘法问题(matrix-chain multiplication problem) 描述如下：给定n 个矩阵的链 \left<A_1, A_2, ...， A_n \right> 矩阵A_i 的规模为 p_{i-1} \times p_i(1 \le i \le n), 求完全括号化方案，使得计算乘积 A_1A_2 \cdots A_n 所需标量乘法次数最少。

示例 1：

输入：[30, 35, 15, 5, 10, 20, 25]
输出："((A0(A1A2))((A3A4)A5))"

用动态规划方法来求解

步骤1 : 最优括号化方案的结构特征

​ 为了构造一个矩阵链乘法问题实例的最优解，我们可以将问题划分为两个子问题 A_iA_{i+1} \cdots A_k 和 A_{k+1}A_{k+2} \cdots A_j, 的最优括号化问题），求出子问题实例的最优解，然后将子问题的最优解组合起来。我们必须保证在确定分割点时，已经考察了所有可能的划分点，这样就可以保证不会遗漏最优解。

步骤2: 一个递归求解方案

​ 对矩阵链乘法问题，我们可以将对所有 1 \le i \le j \le n 确定 A_iA_{i+1} \cdots A_j 的最小代价括号化方案作为子问题。令 m[i, j] 表示计算矩阵 A_{i..j} 所需标量乘法次数的最小值，那么，原问题的最优解计算 A_{1..n} 所需的最低代价就是 m[1, n]。

​ 假设 A_iA_{i+1} \cdots A_j 的最优括号化方案的分割点在矩阵 A_k 和 A_{k+1} 之间，其中 i \le k \lt j。那么， m[i, j] 就等于计算 A_k 和 A_{k+1} 的代价加上两者相乘的代价的最小值。由千矩阵 A_i 的大小为 p_{i-1}\times p_i , 易知 A_{i..k} 和 A_{k+1..j} 相乘的代价为 p_{i-1}p_kp_j 次标量乘法运算。因此，我们得到

因此，A_iA_{i+1} \cdots A_j 最小代价括号化方案的递归求解公式为：

步骤3: 计算最优代价

​ 采用自底向上表格法代替基于公式的递归算法来计算最优代价，过程MATRIX-CHAIN-ORDER 实现了自底向上表格法。此过程假定矩阵 A_i 的规模为 p_{i-1} \times p_i(i=1,2,\cdots,n)。它的输入是一个序列 p = \left<p_0,p_1.\cdots,p_n\right>，其长度为 p.length=n+1。过程用一个辅助表 m[1..n, 1..n] 来保存代价 m[i, j], 用另一个辅助表 s[1..n-1, 2..n]记录最优值 m[i,j] 对应的分割点 k。我们就可以利用表 s 构造最优解。

// 外两层循环为斜对角遍历算法
MATRIX-CHAIN-ORDER(p)
  n = p.length-1
  let m[1.. n, 1.. n] and s[1.. n-1, 2.. n] be new tables
  for i = 1 to n
    m[i,i] = 0
  for l = 2 to n   // l is the chain length
    for i = 1 to n-l+1
      j = i+l-1
      m[i,j] = oo
      for k = i to j-1
        q = m[i,k] + m[k+1,j]+p[i-1]p[k]p[j]
        if q < m[i,j]
          m[i,j] = q
          m[i,j] = k
  return m and s

==Java实现==

public static void matrixChainOrder(int[] matrixs) {
    int n = matrixs.length - 1;
    int[][] m = new int[n][n], s = new int[n][n];
    // 外两层循环为斜对角遍历算法
    for (int k = 0; k < n; k++) {
        for (int i = 0, j = k + 1; i < n && j < n; i++, j++) {
            m[i][j] = Integer.MAX_VALUE;
            for (int q = i; q < j; q++) {
                int tmp = m[i][q] + m[q + 1][j] + matrixs[i] * matrixs[q + 1] * matrixs[j + 1];
                if (tmp < m[i][j]) {
                    m[i][j] = tmp;
                    s[i][j] = q;
                }
            }
        }
    }
    // 暂不返回此处可以调用以下函数输出最优解
    // printOptimalParens(s, 0, n - 1)
}

算法分析

​ 简单分析MATRIX-CHAIN-ORDER 的嵌套循环结构，可以看到算法的运行时间为 O(n^3) 。循环嵌套的深度为三层，每层的循环变量(l 、i 和k) 最多取 n-1 个值。算法还需要 \Theta(n^2) 的内存空间来保存表m 和s 。因此，MA TRIX-CHAIN-ORDER 比起穷举所有可能的括号化方案来寻找最优解的指数阶算法要高效得多。

步骤4: 构造最优解

​ 表 s[1..n-1, 2..n] 记录了构造最优解所需的信息。每个表项 s[i, j] 记录了一个k 值，指出 A_iA_{i+1} \cdots A_j 的最优括号化方案的分割点应在 A_k 和 A_{k+1} 之间。因此，我们知道 A_{i..n} 的最优计算方案中最后一次矩阵乘法运算应该是 A_{1..s[1,n]} 和 A_{s[1,n]+1..n} 。我们可以用相同的方法递归地求出更早的矩阵乘法的具体计算过程，因为s[1,s[1,n]] 指出了计算 A_{1..s[1,n]} 时应进行的最后一次矩阵乘法运算； s[s[1,n]+1,n] 指出了计算 A_{s[1,n]+1..n} 时应进行的最后一次矩阵乘法运算。

PRINT-OPTIMAL-PARENS(s, i, j)
  if i == j
    print "A",
  else
    print "("
    PRINT-OPTIMAL-PARENS(s, i, s[i,j])
    PRINT-OPTIMAL-PARENS(s, s[i,j]+1, j)
    print ")"

==Java实现==

public static String printOptimalParens(int[][] s, int i, int j) {
    StringBuilder builder = new StringBuilder();

    if (i == j) {
        builder.append("A" + i);
    } else {
        builder.append("(");
        builder.append(printOptimalParens(s, i, s[i][j]));
        builder.append(printOptimalParens(s, s[i][j] + 1, j));
        builder.append(")");
    }
    return builder.toString();
}

附：带备忘录算法

MEMOIZED-MATRIX-CHAIN(p)
  n = p.length - 1
  let m[1.. n, 1.. n] be a new table
  for i = 1 to n
    for j = i to n
      m[i,j] = oo
  return LOOKUP-CHAIN(m, p, 1, n)
    
LOOKUP-CHAIN(m, p, i, j)
  if m[i,j] < oo
    return m[i,j]
  if i == j
    m[i,j] = 0
  else
    for k = i to j -1
      q = LOOKUP-CHAIN(m, p, i, k) + LOOKUP-CHAIN(m, p, k+1, j) + p[i-1]p[k]p[j]
      if q < m[i,j]
        m[i,j]=q
  return m[i,j]

==Java实现==

public static int memoiaedMatrixChain(int[] matrixs) {
    int n = matrixs.length - 1;
    int[][] m = new int[n][n];
    for (int i = 0; i < n; i++) {
        Arrays.fill(m[i], Integer.MAX_VALUE);
        m[i][i] = 0;
    }
    return lookupChain(m, matrixs, 0, n - 1);
}

public static int lookupChain(int[][] m, int[] matrixs, int i, int j) {
    if (m[i][j] != Integer.MAX_VALUE) return m[i][j];

    for (int q = i; q < j; q++) {
        int tmp = lookupChain(m, matrixs, i, q)
                + lookupChain(m, matrixs, q + 1, j)
                + matrixs[i] * matrixs[q + 1] * matrixs[j + 1];
        if (tmp < m[i][j]) {
            m[i][j] = tmp;
        }
    }
    
    return m[i][j];
}

15.3 动态规划原理

适合用动态规划方法求解的最优化问题应该具备的性质：

• 最优子结构

  ​ 用动态规划方法求解最优化问题的第一步就是刻画最优解的结构。如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构性质。使用动态规划方法时，我们用子问题的最优解来构造原问题的最优解。

  发掘最优子结构性质（==保持子问题空间尽可能简单，只在必要时才扩展它==）：

  1. 证明问题最优解的第一个组成部分是做出一个选择，例如，选择钢条第一次切割位置，选择矩阵链的划分位置等。做出这次选择会产生一个或多个待解的子问题。
  2. 对于一个给定问题，在其可能的第一步选择中，你假定已经知道哪种选择才会得到最优解。你现在并不关心这种选择具体是如何得到的，只是假定已经知道了这种选择。
  3. 给定可获得最优解的选择后，你确定这次选择会产生哪些子问题，以及如何最好地刻画子问题空间。
  4. 利用“剪切—粘贴" (cut-and-paste) 技术证明：作为构成原问题最优解的组成部分，每个子问题的解就是它本身的最优解。

  对于不同问题领域，最优子结构的不同体现在两个方面：

  • 原问题的最优解中涉及多少个子问题，以及

  • 在确定最优解使用哪些子问题时，我们需要考察多少种选择。

• 重叠子问题

  ​ 适合用动态规划方法求解的最优化问题应该具备的第二个性质是子问题空间必须足够“小"'，即问题的递归算法会反复地求解相同的子间题，而不是一直生成新的子问题。一般来讲，不同子问题的总数是输入规模的多项式函数为好。如果递归算法反复求解相同的子问题，我们就称最优化问题具有重叠子问题(overlapping subproblems) 性质。

自底向上和自顶向下（备忘录）

​ 在动态规划方法中，我们通常自底向上地使用最优子结构。也就是说，首先求得子问题的最优解，然后求原问题的最优解。在求解原问题过程中，我们需要在涉及的子问题中做出选择，选出能得到原问题最优解的子问题。原问题最优解的代价通常就是子问题最优解的代价再加上由此次选择直接产生的代价。

​ 通常情况下，如果每个子问题都必须至少求解一次，自底向上动态规划算法会比自顶向下备忘算法快（都是O(n3) 时间，相差一个常量系数），因为自底向上算法没有递归调用的开销，表的维护开销也更小。而且，对于某些问题，我们可以利用表的访问模式来进一步降低时空代价。相反，如果子问题空间中的某些子问题完全不必求解，备忘方法就会体现出优势了，因为它只会求解那些绝对必要的子问题。

15.4 最长公共子序列

​ 给定两个序列X 和Y, 如果Z 既是X 的子序列，也是Y 的子序列，我们称它是X 和Y 的公共子序列(common subsequence) 。

​ 最长公共子序列问题(longest-common-subsequence problem) 给定两个序列 X=\left<x_1, X_2, \cdots,X_m \right> 和Y=\left<y_1, Y_2, \cdots， Y_n \right>，求X 和Y 长度最长的公共子序列。本节将展示如何用动态规划方法高效地求解 LCS 问题。

示例 1：

输入：str1 = "abcbdab", str2 = "bdcaba" 
输出：4  
解释：最长公共子序列是 "bcba" ，它的长度为 4 。

示例 2：

输入：str1 = "abc", str2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

用动态规划方法来求解

步骤1 : 刻画最长公共子序列的特征

​ 令 X=\left\langle x_{1}, x_{2}, \cdots, x_{m}\right\rangle 和 Y=\left\langle y_{1}, y_{2}, \cdots, y_{n}\right\rangle 为两个序 列, Z=\left\langle z_{1}, z_{2}, \cdots, z_{k}\right\rangle 为 X 和 Y 的任意 LCS。

1. 如果 x_{m}=y_{n} , 则 z_{k}=x_{m}=y_{n} 且 Z_{k-1} 是 X_{m-1} 和 Y_{n-1} 的一个 LCS。
2. 如果 x_{m} \neq y_{n} , 那么 z_{k} \neq x_{m} 意味着 Z 是 X_{m-1} 和 Y 的一个 LCS。
3. 如果 x_{m} \neq y_{n} , 那么 z_{k} \neq y_{n} 意味着 Z 是 X 和 Y_{n-1} 的一个 LCS。

​ 上述定义可以证明两个序列的LCS 包含两个序列的前缀的LCS。因此， LCS 问题具有最困祖优子结构性质。我们马上还会看到，其递归算法也具有重叠子问题性质。

步骤2: 一个递归解

​ 在求 X=\left\langle x_{1}, x_{2}, \cdots, x_{m}\right\rangle 和 Y=\left\langle y_{1}, y_{2}, \cdots, y_{n}\right\rangle 的一个LCS 时，我们需要求解一个或两个子问题。如果 x_{m}=y_{n} , 我们应该求解 X_{m-1} 和 Y_{n-1} 的一个LCS。将 x_{m}=y_{n} 追加到这个LCS 的末尾，就得到X 和Y 的一个LCS 。如果 x_{m} \neq y_{n} 我们必须求解两个子问题：求 X_{m-1} 和 Y 的一个LCS 与 X 和 Y_{n-1} 的一个LCS 。两个LCS 较长者即为X 和Y 的一个LCS 。由千这些情况覆盖了所有可能性，因此我们知道必然有一个子问题的最优解出现在X 和Y 的LCS 中。

​ 我们定定义从 c[i ,j] 表示 X_i 和 Y_j 的LCS 的长度。如果 i = 0 或 j = 0, 即一个序列长度为0, 那么LCS 的长度为0 。根据LCS 问题的最优子结构性质，可得如下公式：

步骤3: 计算LCS 的长度

​ 过程LCS-LENGTH 接受两个序列 X=\left\langle x_{1}, x_{2}, \cdots, x_{m}\right\rangle 和 Y=\left\langle y_{1}, y_{2}, \cdots, y_{n}\right\rangle 为输人。它将 c[i, j] 的值保存在表 c[0.. m, 0.. n] 中，并按行主次序(row-major order) 计算表项（即首先由左至右计算c 的第一行，然后计算第二行，依此类推）。过程还维护一个表 b[1.. m, 1.. n],帮助构造最优解。b[i, j] 指向的表项对应计算 c[i, j] 时所选择的子问题最优解。过程返回表b和表c, c[m, n]保存了X 和Y 的LCS 的长度。

LCS-LENGTH(X,Y)
  m = X.length
  n = Y.length
  let b[1.. m, 1.. n] and c[0.. m, 0.. n] be new tables
  for i = 1 to m
    c[i,0] = 0
  for j = 0 to n
    c[0,j] = 0
  for i = 1 to m
    for j = 1 to n
      if x[i] == y[j]
        c[i,j]=c[i-1, j-1]+1
        b[i,j] = 1
      else if c[i-1,j] > c[i,j-1]
        c[i,j]=c[i-1,j]
        b[i,j] = 2
      else
        c[i,j]=c[i,j-1]
        b[i,j] = 3
  return c and b

==Java实现==

public static int lcsLength(String str1, String str2) {
    int m = str1.length(), n = str2.length();
    char[] x = str1.toCharArray(), y = str2.toCharArray();
    int[][] b = new int[m + 1][n + 1];
    int[][] c = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i][j] = 1;
            } else if (c[i - 1][j] > c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                b[i][j] = 2;
            } else {
                c[i][j] = c[i][j - 1];
                b[i][j] = 3;
            }
        }
    }
    // 此处可调用以下函数输出子序列字符串
    // printLcs(b, x, m, n);

    return c[m][n];
}

**步骤4: **构造LCS

​ 用LCS-LENGTH 返回的表b 快速构造X=\left\langle x_{1}, x_{2}, \cdots, x_{m}\right\rangle 和 Y=\left\langle y_{1}, y_{2}, \cdots, y_{n}\right\rangle 的LCS, 只需简单地从b[m, n]开始，并按值代表的方向追踪下去即可。当在表项 b[i, j] 中遇到1时，意味着 x_i=y_j 是LCS 的一个元素。按照这种方法，我们可以按逆序依次构造出LCS 的所有元素。下面的递归过程会按正确的顺序打印出X 和Y 的一个LCS。对它的起始调用为PRINT-LCS(b, X, X.length, Y.length) 。

PRINT-LCS(b,X, i, j)
  if i == 0 or j == 0
  		return
  if b[i,j] == 1
    PRINT-LCS(b,X, i-1, j-1)
    prnt x[i]
  else if b[i,j] == 2
    PRINT-LCS(b,X,i-1,j)
  else
    PRINT-LCS(b,X,i,j-1)

==Java实现==

public static void printLcs(int[][] b, char[] x, int i, int j) {
    if (i <= 0 || j <= 0) return;
    switch (b[i][j]) {
        case 1:
            printLcs(b, x, i - 1, j - 1);
            System.out.print(x[i - 1]);
            break;
        case 2:
            printLcs(b, x, i - 1, j);
            break;
        case 3:
            printLcs(b, x, i, j - 1);
            break;
    }
}

15.5 最优二叉搜索树

​ 最优二叉搜索树(optimal binary search tree) 问题：给定一个n 个不同关键字的已排序的序列 K=\left\langle k_{1}, k_{2}, \cdots, k_{n}\right\rangle（因此 k_{1} \lt k_{2} \lt \cdots \lt k_{n}），我们希望用这些关键字构造一棵二叉搜索树。对每个关键字 k_{i}, 都有一个概率 p_{i}, 表示其搜索频率。有些要搜画索的值可能不在K 中，因此我们还有n+1 个“伪关键字"d_{0}, d_{1}, \cdots, d_{n} 表示不在K 中的值。d_0表示所有小千 d_1 的值， d_n 表示所有大于 k_n 的值，对 i=1, 2, \cdots, n-1, 伪关键字 d_i, 表示所有在 k_i 和 k_{i+1} 之间的值。对每个伪关键字 d_i, 也都有一个概率 q_i, 表示对应的搜索频率。因此有如下公式：

在T 中进行一次搜索的期望代价如下，其中 depth_T 表示一个结点在树T 中的深度。

对于一个给定的概率集合，我们希望构造一棵期望搜索代价最小的二叉搜索树，我们称之为最优二叉搜索树。

示例 1：

输入：p = [0, 0.15, 0.1, 0.05, 0.1, 0.2], q = [0.05, 0.1, 0.05, 0.05, 0.05, 0.1]
输出：2.75
解释：最优平衡二叉树节点关系如下，期望代价为 2.75。
    k2是根
    k1是k2的左孩子
    d0是k1的左孩子
    d1是k1的右孩子
    k5是k2的右孩子
    k4是k5的左孩子
    k3是k4的左孩子
    d2是k3的左孩子
    d3是k3的右孩子
    d4是k4的右孩子
    d5是k5的右孩子

用动态规划方法来求解

步骤1 : 最优二叉搜索树的结构

​ 如果一棵最优二叉搜索树T 有一棵包含关键字 k_{i}, \cdots, k_{j} 的子树T', 那么T'必然是包含关键字 k_{i}, \cdots, k_{j} 忆和伪关键字 d_{i-1}, \cdots, d_{j} 的子问题的最优解。

步骤2: 一个递归算法

​ 求解包含关键字 k_{i}, \cdots, k_{j} 的最优二叉搜索树，其中i \ge 1, j \le n \text{且} j \ge i-1( 当j = i-1 时，子树不包含实际关键字，只包含伪关键字 d_{i-1}) 。定义e[i, j]为在包含关键字 k_{i}, \cdots, k_{j} 的最优二叉搜索树中进行一次搜索的期望代价。最终，我们希望计算出e[1, n] 。

​ 为了记录最优二叉搜索树的结构，对千包含关键字 k_{i}, \cdots, k_{j}(1 \le i \le j \le n) 的最优二叉搜索树，我们定义root[i, j] 保存根结点龙的下标 r。

​ 如果选取期望搜索代价最低者作为根结点，可得最终递归公式：

步骤3: 计算最优二叉搜索树的期望搜索代价

​ 用一个表 e[1.. n+1, 0.. n] 来保存 e[i, j] 值。第一维下标上界为 n+1 而不是n, 原因在千对于只包含伪关键字d_n 的子树，我们需要计算并保存e[n+1, n] 。第二维下标下界为0, 是因为对于只包含伪关键字 d_0 的子树，我们需要计算并保存 e[1,0] 。我们只使用表中满足 j \ge i - 1 的表项 e[i, j] 。我们还使用一个表root, 表项 root[i, j] 记录包含关键字 k_{i}, \cdots, k_{j}，龙的子树的根。我们只使用此表中满足 1 \le i \le j \le n 的表项 root[i, j] 。

​ 为了避免每次计算 e[i, j] 时都重新计算 w(i, j), 我们将这些值保存在表 w[1.. n+1, 0.. n] 中，这样每次可节省\Theta(j-i)次加法。对基本情况，令 w[i,i-1]=q_{i-1}(1 \le i n+1) 。对 j \ge i 的情况，可如下计算：

下面的伪代码接受概率列表 p_{1}, \cdots, p_{n} 和 q_{0}, \cdots, q_{n} 及规模n 作为输入，返回表 e 和root 。

OPTIMAL-BST(p,q,n)
  let e[1.. n+1,0.. n], w[1.. n+1,0.. n],and root[1.. n,1.. n] be new tables
  for i = 1 to n+1
    e[i,i-1] = q[i-1]
    w[i,i-1] = q[i-1]
  for l = 1 to n
    for i = 1 to n-l+l
      j = i+l-1
      e[i,j] = oo
      w[i,j] = w[i,j-1]+p[i]+q[j]
      for r = i to j
        t = e[i,r-l]+e[r+1,j]+w[i,j]
        if t < e[i,j]
          e[i,j] = t
          root[i,j] = r
  return e and root

==Java实现==

public static double optimalBst(double[] p, double[] q) {
    int n = p.length;
    double[][] e = new double[n + 1][n];
    double[][] w = new double[n + 1][n];
    int[][] root = new int[n + 1][n + 1];
    for (int i = 1; i <= n; i++) {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }

    for (int k = 1; k < n; k++) {
        for (int i = 1, j = k; i < n && j < n; i++, j++) {
            e[i][j] = Double.MAX_VALUE;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for (int r = i; r <= j; r++) {
                double tmp = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if (tmp < e[i][j]) {
                    e[i][j] = tmp;
                    root[i][j] = r;
                }
            }
        }
    }
    
    // 此处可调用以下函数输出二叉树的节点关系
    // printOptimalBST(root, 1, n - 1, -1);
    // constructOptimalBst(root);
    
    return e[1][n-1];
}

算法分析

​ 与MATRIX-CHAIN-ORDER 一样， OPTIMA-BST 的时间复杂度也是O(n^3) 。由于它包含三重for 循环，而每层循环的下标最多取n 个值，因此很容易得出其运行时间为 O(n^3) 。OPTIMAL-EST 的循环下标的范围与MATRIX-CHAIN-ORDER 不完全一样，但每个方向最多相差1 。

**步骤4: **构造最优二叉搜索树

利用root值来构造最优二叉搜索树

CONSTRUCT-OPTIMAL-BST(root)
  n = root.length - 1
  PRINT-OPTIMAL-BST(root, 1, n - 1, -1);
    
PRINT-OPTIMAL-BST(root,i,j,r)
  if j < i - 1
    return
  if j == i - 1
    if j < r
      print "d" + j + "是k" + r "的左孩子\n"
    else
      print "d" + j + "是k" + r "的右孩子\n"
    return
  curRoot = root[i][j];
  if r == -1
    print "k" + curRoot + "是根\n"
  else
    if curRoot < r
      print "k" + curRoot + "是k" + r + "的左孩子\n"
    else
      print "k" + curRoot + "是k" + r + "的右孩子\n"
  PRINT-OPTIMAL-BST(root,i,curRoot - 1,curRoot)
  PRINT-OPTIMAL-BST(root,curRoot + 1,j,curRoot)

==Java实现==

public static void constructOptimalBst(int[][] root) {
    // 矩阵个数为 root.length - 1，因此传入 root.length - 2
    // -1 表示当前无父节点（即根节点）
    printOptimalBST(root, 1, root.length - 2, -1);
}

public static void printOptimalBST(int[][] root, int i, int j, int r) {
    if (j < i - 1)
        return;
    if (j == i - 1) { // 虚拟键
        if (j < r) {
            System.out.printf("d%d是k%d的左孩子\n", j, r);
        } else {
            System.out.printf("d%d是k%d的右孩子\n", j, r);
        }
        return;
    }

    int curRoot = root[i][j];
    if (r == -1) {
        // 输出树根
        System.out.printf("k%d是根\n", curRoot);
    } else {
        // 内部结点
        if (curRoot < r) {
            System.out.printf("k%d是k%d的左孩子\n", curRoot, r);
        } else {
            System.out.printf("k%d是k%d的右孩子\n", curRoot, r);
        }
    }

    printOptimalBST(root, i, curRoot - 1, curRoot);
    printOptimalBST(root, curRoot + 1, j, curRoot);
}

第十六章 贪心算法

​ 贪心算法(greedy algorithm) 就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。贪心算法并不保证得到最优解，但对很多问题确实可以求得最优解。

16.1 活动选择问题

​ 调度竞争共享资源的多个活动的问题，假定有一个n 个活动(activity) 的集合 S=\{a_1, a_2, \cdots, a_n\} 这些活动使用同一个资源（例如一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个活动 a_i 都有一个开始时间 s_i 和一个结束时间 f_i 其中 0 \le s_i \lt f_i \lt \infty 。如果被选中，任务 a_i 发生在半开时间区间 [s_i, f_i) 期间。如果两个活动 a_i 和 a_j 满足 [s_i, f_i) 和 [s_j, f_j) 不重叠，则称它们是兼容的。也就是说，若 s_i \ge f_j 或 s_j \ge f_i，则 a_i 和 a_j 是兼容的。在活动选择问题中，我们希望选出一个最大兼容活动集。假定活动已按结束时间的单调递增顺序排序： f_1 \le f_2 \le \cdots \le f_n

示例 1：

输入：s = [1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12], f = [4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
输出：[1, 4, 8, 11]
解释：这四个活动的的活动时间互不重叠，且是最大的活动数。

活动选择问题的最优子结构

​ 令 S_{ij} 表示在 a_i 结束之后开始，且在 a_j 开始之前结束的那些活动的集合。假定我们希望求 S_{ij} 的一个最大的相互兼容的活动子集，进一步假定 A_{ij} 就是这样一个子集，包含活动 a_k 。由于最优解包含活动 a_k 我们得到两个子问题：寻找 S_{ik} 中的兼容活动（在 a_i 结束之后开始且 a_k 开始之前结束的那些活动）以及寻找skj 中的兼容活动（在 a_k 结束之后开始且在 a_j 开始之前结束的那些活动）。令 A_{ik} = A_{ij} \cap S_{ik} 和 A_{kj} = A_{ij} \cap S_{kj}，这样 A_{ik} 包含 A_{ij} 中那些在 a_k 开始之前结束的活动， A_{kj} 包含 A_{ij} 中那些在 a_k 结束之后开始的活动。因此，我们有 A_{ij} = A_{ik} \cup \{a_k\} \cup A_{kj}，而且 S_{ij} 中最大兼容任务子集 A_{ij} 包含 |A_{ij}| = |A_{ik}| + |A_{kj}| + 1 个活动。

​ 这样刻画活动选择问题的最优子结构，意味着我们可以用动态规划方法求解活动选择问题。如果用 c[i,j] 表示集合 S_{ij} 的最优解的大小，则可得递归式: c[i,j]=c[i,k]+c[k,j]+1，最终递推式如下：

​ 于是接下来可以设计一个带备忘机制的递归算法，或者使用自底向上法填写表项。

用贪心选择求解

​ 实际上，对千活动选择问题，我们只需考虑一个选择：贪心选择。

​ 现在考虑可选的活动，其中必然有一个最先结束。因此，直觉告诉我们，应该选择S 中最早结束的活动，因为它剩下的资源可供它之后尽量多的活动使用。（如果S 中最早结束的活动有多个，我们可以选择其中任意一个）。换句话说，由千活动已按结束时间单调递增的顺序排序，贪心选择就是活动 a_1 。

​ 寻找在a1 结束后开始的活动。为什么不需要考虑在a1 开始前结束的活动呢？因因为 s_1 \lt f_1 且f_1是最早结束的活动，所以不会有活动的结束时间早于 s_1 。因此，所有与 a_1 兼容的活动都必须在 a_1 结束之后开始。

​ 我们已经证明活动选择问题具有最优子结构性质。令 S_k=\{a_i\in S:s_i \ge f_k\} 为在 a_k 结束后开始的任务集合。当我们做出贪心选择，选择了a_1 后，剩下的 S_1 是唯一需要求解的子问题气最优子结构性质告诉我们，如果 a_1 在最优解中，那么原问题的最优解由活动 a_1 及子问题 S_1 中所有活动组成。

​ 我们可以反复选择最早结束的活动，保留与此活动兼容的活动，重复这一过程，直至不再有剩余活动。而且，因为我们总是选择最早结束的活动，所以选择的活动的结束时间必然是严格递增的。我们只需按结束时间的单调递增顺序处理所有活动，每个活动只考查一次。

递归贪心算法

​ 过程 RECURSIVE-ACTIVITYSELECTOR 的输入为两个数组 s 和 f, 表示活动的开始和结束时间，下标 k 指出要求解的子问题 S_k, 以及问题规模n 。它返回 S_k 的一个最大兼容活动集。我们假定输入的n 个活动已经按结束时间的单调递增顺序排列好。如果未排好序，我们可以在O(n lgn) 时间内对它们进行排序，结束时间相同的活动可以任意排列。为了方便算法初始化，我们添加一个虚拟活动 a_0 其结束时间 f_0 = 0, 这样子问题 S_0 就是完整的活动集S 。求解原间题即可调用 RECURSIVEACTIVITY-SELECTOR(s, f, 0, n) 。

RECURSIVE-ACTIVITY-SELECTOR(s, f, k, n)
  m = k+1
  while m <= n and s[m] < f[k]  // find the first activity in S, to finish
    m = m+l
  if m <= n
    return {a[m]} 并 RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
  else
    return {}

迭代贪心算法

​ 过程 GREEDY-ACTIVITY-SELECTOR 是过程 RECURSIVE-ACTIVITY-SELECTOR 的一个迭代版本。它也假定输入活动已按结束时间单调递增顺序排好序。它将选出的活动存入集合A中，并将A 返回调用者。

GREEDY-ACTIVITY-SELECTOR(s, f)
  n = s.length
  A = {a[1]}
  k = 1
  for m = Z to n
    if s[m] >= f[k]
      A = A 并 {am}
      k = m
  return A

==Java实现==

public static List<Integer> greedyActivitySelector(int[] start, int[] finish) {
    LinkedList<Integer> ans = new LinkedList<>();
    ans.add(0);
    for (int i = 1; i < start.length; i++) {
        if (start[i] >= finish[ans.peekLast()]) {
            ans.add(i);
        }
    }
   return ans;
}

算法分析

​ 与递归版本类似，在输入活动已按结束时间排序的前提下， GREEDY-ACTIVITYSELECTOR 的运行时间为 \Theta(n) 。

16.2 贪心算法原理

​ 贪心算法通过做出一系列选择来求出问题的最优解。在每个决策点，它做出在当时看来最佳的选择。这种启发式策略并不保证总能找到最优解，但对有些问题确实有效，如活动选择问题。

设计贪心算法步骤:

1. 将最优化问题转化为这样的形式：对其做出一次选择后，只剩下一个子问题需要求解。
2. 证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的。
3. 证明做出贪心选择后，剩余的子问题满足性质：其最优解与贪心选择组合即可得到原问题的最优解，这样就得到了最优子结构。

适合用贪心算法求解的最优化问题应该具备的性质：

• 贪心选择性质

  ​ 我们可以通过做出局部最优（贪心）选择来构造全局最优解。换句话说，当进行选择时，我们直接做出在当前问题中看来最优的选择，而不必考虑子问题的解。

​ 当然，我们必须证明每个步骤做出贪心选择能生成全局最优解。

​ 如果进行贪心选择时我们不得不考虑众多选择，通常意味着可以改进贪心选择，使其更为高效。

• 最优子结构

  ​ 如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。此性质是能否应用动态规划和贪心方法的关键要素。

  ​ 当应用于贪心算法时，我们通常使用更为直接的最优子结构。如前所述，我们可以假定，通过对原问题应用贪心选择即可得到子问题。我们真正要做的全部工作就是论证：将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解。这种方法隐含地对子问题使用了数学归纳法，证明了在每个步骤进行贪心选择会生成原问题的最优解。

贪心对动态规划的差异对比

​ 0-1 背包问题(0-1 knapsack problem) 是这样的：一个正在抢劫商店的小偷发现了n 个商品，第i 个商品价值v_i 美元，重 w_i 磅， v_i 和 w_i 都是整数。这个小偷希望拿走价值尽量高的商品，但他的背包最多能容纳 W 磅重的商品， W 是一个整数。他应该拿哪些商品呢？（对每个商品，小偷要么把它完整拿走，要么把它留下；他不能只拿走一个商品的一部分，或者把一个商品拿走多次。）

​ 在分数背包问题(fractional knapsack problem) 中，设定与0-1 背包问题是一样的，但对每个商品，小偷可以拿走其一部分，而不是只能做出二元(0-1) 选择。

​ 虽然两个问题相似，但我们用贪心策略可以求解分数背包问题，而不能求解0-1 背包问题。

分数背包问题

​ 为了求解分数背包问题，我们首先计算每个商品的每磅价值 v_i / w_i, 。遵循贪心策略，小偷首先尽量多地拿走每磅价值最高的商品。如果该商品已全部拿走而背包尚未满，他继续尽量多地拿走每磅价值第二高的商品，依此类推，直至达到重量上限 W。因此，通过将商品按每磅价值排序，贪心算法的运行时间为 O(nlgn)。

0-1背包问题

​ 考虑原问题的一部分,设 V(i,j) 表示将前 i (1 \le i \le n) 个物品装人容量为 j (1 \le j \le W) 的背包获得的最大价值,在决策 x_i 时,已确定了 (x_1,...,x_{i-1}),则问题处于下列两种状态之一:
​ (1）背包容量不足以装人物品 i,则装人前 i 个物品得到的最大价值和装人前 i-1 个物品得到的最大价值是相同的,即 x_i=0,背包不增加价值。
​ (2）背包容量可以装入物品 i,如果把第 i 个物品装人背包,则背包中物品的价值等于把前 i-1个物品装入容量为j-w_i,的背包中的价值加上第 i 个物品的价值 v_i ;如果第 i 个物品没有装人背包,则背包中物品的价值等于把前 i-1 个物品装人容量为 j 的背包中所取得的价值。显然,取二者中价值较大者作为把前 i 个物品装入容量为 j$ 的背包中的最优解。则得到如下递推式:

计算最优解

// C 为上述重量上限 W
KNAPSACK(v,w,C)
  n = v.length
  let val[0..n,0..C] be new tables
  for i = 0 to n
    val[i,0] = 0
  for j = 0 to C
    val[0,j] = 0
  for i = 1 to n
    for j = 1 to C
      if j < w[i - 1]
        val[i][j] = val[i - 1][j];
      else
        val[i][j] = max(val[i - 1][j], val[i - 1][j - w[i - 1]] + v[i - 1]);

  return V[n][C];

==Java实现==

public static int knapsack(int[] value, int[] weight, int W) {
    int len = weight.length;
    int[][] val = new int[len + 1][W + 1];
    for (int i = 1; i <= len; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < weight[i - 1]) {
                val[i][j] = val[i - 1][j];
            } else {
                val[i][j] = Math.max(val[i - 1][j], val[i - 1][j - weight[i - 1]] + value[i - 1]);
            }
        }
    }

    // 此处可调用以下函数输出具体选择的那些物品（编号）
    // System.out.println(printKnapsack(val, value, W));

    return val[len][W];
}

构造最优解

PRINT-KNAPSACK(val, v, C)
  m = val.length - 1
  n = val[0].length - 1;
  pre = val[m][n];
  while m > 0 and n > 0
    if val[m][n] == pre
      m = m - 1
    else
      print m + 1
      pre = val[m + 1][n] - v[m];
	  while n > 0 and val[m][n] > pre
        n = n - 1

==Java实现==

public static List<Integer> printKnapsack(int[][] val, int[] value, int W) {
    List<Integer> ans = new ArrayList<>();
    int m = val.length - 1, n = val[0].length - 1;
    int pre = val[m][n];
    while (m > 0 && n > 0) {
        if (val[m][n] == pre)
            m--;
        else {
            // 纵行确认
            ans.add(m + 1);
            pre = val[m + 1][n] - value[m];
            // 横行确认
            while (n > 0 && val[m][n] > pre) n--;
        }
    }

    return ans;
}

16.3 赫夫曼编码

​ 变长编码(variable-length code) 可以达到比定长编码好得多的压缩率，其思想是赋予高频字符短码字，赋予低频字符长码字。

​ 前缀码(prefix code沪，即没有任何码字是其他码字的前缀。

​ 文件的最优编码方案总是对应一棵满(full) 二叉树，即每个非叶结点都有两个孩子结点。定长编码实例不是最优的，因为它的二叉树表示并非满二叉树。

构造赫夫曼编码

​ 在下面给出的伪代码中，我们假定C 是一个n 个字符的集合，而其中每个字符 c \in C 都是一个对象，其属性c.freq 给出了字符的出现频率。算法自底向上地构造出对应最优编码的二叉树T。它从 |C| 个叶结点开始，执行 |C|-1 个“合并“操作创建出最终的二叉树。算法使用一个以属性 freq 为关键字最小优先队列Q, 以识别两个最低频率的对象将其合并。当合并两个对象时，得到的新对象的频率设置为原来两个对象的频率之和。

过程HUFFMAN 会生成一个最优前缀码

HUFFMAN(C)
  n = |C|
  Q = C
  for i = 1 to n-1
    allocate a new node z
    z.left = x = EXTRACT-MIN(Q)
    z.right = y = EXTRACT-MIN(Q)
    z.freq = x.freq + y.freq
    INSERT(Q, z)
  return EXTRACT-MIN(Q)   // return the root of the tree

==Java实现==

static class TreeNode {
    public char chr;
    public int freq;
    public String code = "";
    public TreeNode left, right;

    public TreeNode(char chr, int freq) {
        this.chr = chr;
        this.freq = freq;
    }

    public TreeNode(TreeNode left, TreeNode right) {
        this.freq = left.freq + right.freq;
        this.left = left;
        this.right = right;
    }

    public void encode() {
        if (this.left != null) {
            this.left.code = this.code + "0";
            this.left.encode();
        }

        if (this.right != null) {
            this.right.code = this.code + "1";
            this.right.encode();
        }
    }
}

public static TreeNode huffman(char[] chrs, int[] freqs) {
    Queue<TreeNode> queue = new PriorityQueue<>((o1, o2) -> o1.freq - o2.freq);
    for (int i = 0; i < chrs.length; i++) {
        queue.offer(new TreeNode(chrs[i], freqs[i]));
    }

    while (queue.size() > 1) {
        TreeNode left = queue.poll();
        TreeNode right = queue.poll();
        TreeNode parent = new TreeNode(left, right);
        queue.add(parent);
    }

    TreeNode root = queue.poll();
    // 编码（前缀码）
    root.encode();
    return root;
}

算法分析

​ 假定Q 是使用最小二叉堆实现的（参见第6 章）。对一个n 个字符的集合C, 我们在第2 行用BUILD-MIN-HEAP 过程将Q 初始化，花费时间为 O(n) 。for 循环执行了 n-1 次，且每个堆操作需要 O(lgn) 的时间，所以循环对总时间的贡献为 O(n\:lgn) 。因此，处理一个n 个字符的集合， HUFFMAN 的总运行时间为 O(n\:lgn) 。如果将最小二叉堆换为van Emde Boas 树，我们可以将运行时间减少为O(n\:lg\:lgn)。