算法思想：贪心算法 (Greedy Algorithm)

贪心算法思想的核心非常简单，每次选择当前情况下的最优解，从而期望问题得到最优解。本质是一个证明局部最优解就是全局最优解的过程，贪心算法在有最优子结构的问题中尤为有效。

最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

在我们实际生活中也经常应用此思想，比如我们想买5斤橘子，会从铺子里面里面依次挑最好的、次好的、次次好的果子，总之，我们每次都挑铺子里最好的果子，直到满五斤。

思想

贪心算法适用的解决问题特征如下：

1. 有限制值，比如上面的只要5斤橘子
2. 有期望值，比如上面的期望买的果子都是最好的，我们假设”果子好“这个量有个评分的话，希望总分最高。
3. 在满足限制的情况下，期望值最高。

比如我们选择优惠券，会在满足订单条件下，选择优惠力度最大的一张券（如果可以叠加，那就是几张券）。

当遇到上述此类问题的时候，可以优先尝试使用贪心算法试着解决一下，就是每次选择当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据。比如上面的优果和劣果给限制值——重量的贡献是一样的，我们优先选择给期望值（果子的优劣）贡献更大的优果子。

贪心算法思想不一定能得到最优的结果，比如上面橘子是不可分割的，好橘子通常更大，所以个数可能不会有那么多，有可能只有15个5分的优橘子就已经满五斤了，那其总分是75分，那次果4分5斤可以装20个，那么总分就是80分，比第一种方式更优。（需要注意的是这里5分橘子每斤是15分，而次果是每斤20分，次果在算法上更加符合贪心算法思想，但是一方面橘子是不可分割的，在挑选的时候通常无法恰好找到满足重量的橘子，这里这个例子并不恰当需要结合生活实际体会）

实际上，用贪心算法解决问题的思路，并不总能给出最优解，因为问题的解也会影响问题本身。

再举个例子，我们需要从家里到医院，家到A的距离是3，到B的距离是2，到C的距离是1

  A   -1-    A1   -1-   A2 
3/                       \1
家 -2- B -2- B1 -2- B2 -2- 医院
1\                       /3
  C   -3-    C1   -3-  C2 

如果我们根据贪心算法思想选择最短的C路径，那么这条路径的总长度是1+3+3+3=10 而选择A路径，总长度是3+1+1+1=6。显然A路径才是最短路径。因为选择C路径开始，这个选择本身已经影响到了解决后续问题的解。

钱币找零问题

贪心算法最直观是放在钱币找零问题上。问题描述如下：

现发行的人民币有1角、5角、1元、5元、10元、20元、50元、100元这八种面额。顾客付款后收银员需要找零，假设需要找零N元，问需要如何找零使得使用的货币数量最少

这个问题还有一个变体如下：

现发行的人民币有1、5、10、20、50、100这六种面额。顾客购买N元商品，现需要付款，问如何凑出这个金额，使得使用的货币数量最少

我们很容易想到，我们优先使用面额较大的人民币凑，然后再使用小面额凑。比如我们要凑132元，那么我们优先使用100元，此时还需凑32元，那么我们再凑一张20元和一张10元，最后2元使用两张2元凑出来。总的使用人民币数量就是1张100 + 1张20元 + 1张+10元 + 2张1元 = 5张。

但是这种方法并不是在所有情况下都有效，比如面额是100、99、1 需要凑198元，那么按照上面的方式就是一张100+98张一元 = 99张。而最优解是2张99元。

哈夫曼编码

假设一个8mb的文件只有abcdef这六个字符组成，Java中char和short等长都是16位，而由于只有六个字符，那么我们实际上不需要16位就能存储下一个字符，如下：

此时我们原本的 3/16 的空间就能存下所有文件信息。大大节省的内存和磁盘空间。

这就是Huffman编码的出发点，它是一种压缩算法。
哈夫曼编码是一种不等长的编码系统，考虑解码的唯一性，它要求任何字符的编码都不能是另一个编码的前缀，如果一组编码中任一编码都不是其他任何一个编码的前缀，那么称这组编码为 前缀编码，其保证了编码被解码时的唯一性。

同时哈夫曼编码考察每个字符的出现频率，将出现频率高的字符赋予短编码，已最大程度的节省空间。这实际上就是贪心算法。

哈夫曼编码根据频率赋予不同长度的编码依赖霍夫曼树（哈夫曼树）的构建。

对于给定一组具有确定权值的叶结点，可以构造出不同的二叉树，其中，WPL 最小的二叉树 称为 霍夫曼树（Huffman Tree）。对于霍夫曼树来说，其叶结点权值越小，离根越远，叶结点权值越大。

WPL：树的带权路径长度（Weighted Path Length of Tree，WPL）,计算方式如下：

   [ ]
   / \
  [] []
  /\ /\
 2 3 5[]
      /\
     6  7

对于上面的树的带权路径长度，WPL = (2+3+5) × 2 + (6+7) × 3 = 56. 也就是每个叶子节点的权重与其高度的乘积的和。

哈夫曼树的构建过程如下：

• 从集合中取出频率最小的两个元素作为叶子节点放入树中，他们的频率之和构成一个虚拟节点，做成他们的父节点
• 将这两个最小元素移出集合，将他们的父节点放入到合集
• 再从集合中取出频率最小的两个元素做第一步相同的操作
• 重复步骤，直到只有两个元素，将这个最后两个元素取出放入到树中，他们的频率之和的构建成虚拟节点作为他们的父节点也就是作为根节点。

比如，有abcde五个字符，其频率分别对应是2、1、3、4、6

[2,1,3,4,6]
↓
[3,3,4,6]
/ \
1 2
↓
[6,4,6]
    / \
   3   3
  / \
 1   2
↓
[6,10]
   / \
  6   4
 / \
 3  3
/ \
1  2
↓
    [16]
    / \
   10  6
   / \
   6  4
  / \
  3  3
  /\
  1 2 

 

规定哈夫曼编码树的左分支代表 0，右分支代表 1，则从根结点到每个叶结点所经过的路径组成的 0、1 序列即为该叶结点对应字符的编码。

比如上面的树：

    [16]
   0/ \1
   10  6
  0/ \1
   6  4
 0/ \1
 3   3
0/\1
1 2 

可以得到编码如下：

这里的实现用到了[[堆1：堆与堆排序]]里面的堆

package cn.lishiyuan.algorithm.heap;  
  
  
import java.util.*;  
  
public class Huffman {  
  
    private HNode root;  
  
    int codeLength = -1;  
  
    private Map<Character, String> encodeMap = new HashMap<>();  
  
    private Map<String,Character> decodeMap = new HashMap<>();  
  
    private static class HNode implements Comparable<HNode> {  
        Character data;  
        HNode left;  
        HNode right;  
        boolean isV; // 是否是虚拟节点  
        int weight;  
        public HNode(Character data,int weight){  
            this.data = data;  
            this.weight = weight;  
            this.isV = false;  
  
        }  
  
        @Override  
        public int compareTo(HNode o) {  
            return weight - o.weight;  
        }  
    }  
  
  
  
    public Huffman(char[] chars){  
        // 通过频率构建树  
        // 统计频率  
        Map<Character,Integer> map = new HashMap<>();  
        for (char c : chars) {  
            map.put(c, map.getOrDefault(c,0) + 1);  
        }  
  
        List<HNode> nodes = new ArrayList<>();  
  
        for (char c : map.keySet()) {  
            nodes.add(new HNode(c,map.get(c)));  
        }  
  
        buildTree(nodes);  
  
        // 只有一个元素的时候  
        if (root.isV){  
            putCode(root,"");  
        }else {  
            // 如果只有根节点，直接标为1  
            putCode(root,"1");  
        }  
  
        for (String k : decodeMap.keySet()) {  
            if(k.length() > codeLength){  
                codeLength = k.length();  
            }  
        }  
  
    }  
  
    public Huffman(char[] chars,int[] weights){  
        if(weights.length != chars.length){  
            throw new IllegalArgumentException();  
        }  
        List<HNode> nodes = new ArrayList<>();  
        for(int i=0;i<weights.length;i++){  
            nodes.add(new HNode(chars[i],weights[i]));  
        }  
        buildTree(nodes);  
        // 只有一个元素的时候  
        if (root.isV){  
            putCode(root,"");  
        }else {  
            // 如果只有根节点，直接标为1  
            putCode(root,"1");  
        }  
        for (String k : decodeMap.keySet()) {  
            if(k.length() > codeLength){  
                codeLength = k.length();  
            }  
        }  
    }  
  
    private void buildTree(List<HNode> nodes){  
        // 小顶堆  
        Heap<HNode> heap = new Heap<>(Heap.HeapType.MIN,nodes.size());  
  
        for (HNode node : nodes) {  
            heap.add(node);  
        }  
  
        while (heap.size() > 1) {  
            HNode min = heap.removeTop();  
            HNode min2 = heap.removeTop();  
            HNode parent = new HNode(null, min.weight + min2.weight);  
            // 保证非虚拟节点在有右节点  
            if(min2.isV){  
                parent.left = min2;  
                parent.right = min;  
            }else {  
                parent.left = min;  
                parent.right = min2;  
            }  
  
            parent.isV = true;  
            heap.add(parent);  
        }  
  
        this.root = heap.removeTop();  
    }  
  
    private void putCode(HNode node,String code){  
        if (node == null) return;  
        if(node.isV){  
            // 虚拟节点  
            // 将当前高度的左边标记为0，右边标记为1  
            putCode(node.left,code + "0");  
            putCode(node.right,code + "1");  
        }else {  
            // 实际节点  
            encodeMap.put(node.data,code);  
            decodeMap.put(code,node.data);  
        }  
  
    }  
  
    /**  
     * 出参应当是byte数组，作为编码后的二进制流,这里只用做演示  
     * @param text  
     * @return  
     */  
    public String encode(String text){  
        char[] charArray = text.toCharArray();  
        StringBuilder stringBuilder = new StringBuilder();  
        for (char c : charArray) {  
            stringBuilder.append(encodeMap.get(c));  
        }  
        return stringBuilder.toString();  
    }  
  
    /**  
     * 入参应当是byte数组或者long数组之类的，然后视作二进制流来处理，这里只用做演示  
     * @param text  
     * @return  
     */  
    public String decode(String text){  
        // 解码  
        StringBuilder stringBuilder = new StringBuilder();  
        int start = 0;  
        while (start < text.length()){  
            // 是否存在响应的字符  
            for(int i = 1; i <= codeLength ; i++){  
                String code = text.substring(start, start + i);  
                Character c = decodeMap.get(code);  
                if(Objects.nonNull(c)){  
                    stringBuilder.append(c);  
                    start = start + i;  
                    break;                }  
            }  
  
        }  
        return stringBuilder.toString();  
    }  
  
}

注意： 在实际应用中应当是编码的结果应当是一个byte[]或者long[]然后将数组当作二进制流。