文章結(jié)構(gòu)

1. 如何理解貪心算法
2. 貪心算法實(shí)例分析
3. 使用貪心算法實(shí)現(xiàn)哈夫曼編碼
4. 源碼地址
5. 說明

算法中基本的算法思想有：貪心算法扣甲、分治算法、回溯算法齿椅、動態(tài)規(guī)劃琉挖。這些算法思想并不是具體的算法，他們是用來指導(dǎo)我們設(shè)計(jì)具體的算法和編碼的算法思想涣脚。這篇文章我們開始看看貪心算法和它的實(shí)際應(yīng)用示辈，貪心算法有很多經(jīng)典的應(yīng)用：哈夫曼編碼、Prim和Kruskal最小生成樹算法遣蚀、Dijkstra單源最短路徑算法

1矾麻、如何理解貪心算法

貪心算法的思想是:每次都做出當(dāng)前最優(yōu)的選擇，通過多步選擇得出最終的最優(yōu)解芭梯。它適合解決上一步的選擇不會影響下一步的選擇的問題险耀。如果上一步的選擇會影響下一步的選擇，則使用貪心算法不一定能求出最優(yōu)解玖喘。

1.1 能夠使用貪心算法求解的問題舉例

問題：假如我們有一個(gè)能夠容納100Kg物品的袋子甩牺，可以裝各種物品，不管物品的體積±勰危現(xiàn)在我們有5種豆子贬派，每種豆子的總重量和總價(jià)值各不相同。那如何往背包里面裝這些豆子澎媒，使得最后背包里物品的總價(jià)值最大呢搞乏？

我們一眼就能知道這個(gè)問題的解法，先求出每種豆子的單價(jià)戒努，然后從單價(jià)高的豆子開始裝查描，裝完單價(jià)高的，再去裝次高的，直到袋子裝滿為止冬三。

這個(gè)問題就適合用貪心算法來解匀油，實(shí)際上上面的做法體現(xiàn)的就是貪心算法的思想（每次都做出當(dāng)前最優(yōu)的選擇）。這里第一步選擇裝單價(jià)最高的豆子之后勾笆，不會影響第二步去選擇裝次高的豆子的選擇敌蚜，同樣第二步也不會影響第三步去選擇單價(jià)排名第三的豆子。

1.2 不能使用貪心算法來求解的問題舉例

問題：假如我們要在一個(gè)有權(quán)圖中窝爪，從頂點(diǎn)S開始弛车，找一條到頂點(diǎn)T的最短路徑。

貪心算法的解決思路是蒲每，每次都選擇一條根當(dāng)前頂點(diǎn)相連的權(quán)最小的邊（每次都做出當(dāng)前最優(yōu)的選擇）纷跛，直到找到頂點(diǎn)T。按照這種思路邀杏，我們求出的最短路徑是S->A->E->T,路徑長度1+4+4=9;而實(shí)際的最短路徑是S->B->D->T贫奠，路徑長度2+2+2=6 。

為什么這里貪心算法得不到最優(yōu)解呢望蜡？我們第一步從S->A和第一步從S->B唤崭，下一步面對的頂點(diǎn)和邊是不一樣的。也就是我們前面的選擇會影響后面的選擇脖律，所以得不出最優(yōu)解谢肾。

2、貪心算法實(shí)例分析

接下來小泉，我們再看幾個(gè)能夠使用貪心算法求最優(yōu)解的問題芦疏。

2.1 分糖果

假設(shè)我們有m個(gè)糖果和n個(gè)小孩，糖果的個(gè)數(shù)比小孩的個(gè)數(shù)少微姊，糖果的重量不等酸茴，每個(gè)小孩對糖果大小的需求也不同，問如何分別糖果能盡可能滿足最多數(shù)量的孩子的需求柒桑。

我們用貪心算法怎么來解決這個(gè)問題呢弊决？我們先用最小的糖果來滿足對糖果需求最小的孩子的需求噪舀，然后再去從剩下的糖果中找最小的糖果滿足需求次小的孩子魁淳，按照這個(gè)思路，直到?jīng)]有糖果可以滿足小孩的需求了為止与倡。

2.2 錢幣找零

假設(shè)我們有1元界逛、2元、5元纺座、10元息拜、20元、50元、100元面額的紙幣各對應(yīng)c1少欺、c2喳瓣、c5、c10赞别、c20畏陕、c50、c100張仿滔。當(dāng)我們要支付k元的時(shí)候惠毁，我們?nèi)绾沃Ц叮沟檬褂玫腻X幣數(shù)量最小崎页。

我們用貪心算法怎么來解決這個(gè)問題呢鞠绰？先用面額大，然后在用面額小一點(diǎn)的飒焦，依次類推蜈膨，最后剩下的用1元來補(bǔ)

2.3 求一個(gè)非負(fù)數(shù)移除K個(gè)數(shù)字之后的最小值

在一個(gè)非負(fù)數(shù)a中，我們希望從中移除k個(gè)數(shù)字荒给，讓剩下的數(shù)字值最小丈挟，如何選擇移除哪k個(gè)數(shù)字呢？

使用貪心算法來求解這個(gè)問題志电？每一次移除都使當(dāng)前的數(shù)字是能得到的最小值：從高位開始曙咽，和低一位的數(shù)字比較，如果高位大挑辆，則移除高位例朱，如果地位大，則拿著地位和后面的繼續(xù)比較鱼蝉，直到高位大于低位時(shí)洒嗤，移除高位。移除k個(gè)數(shù)就重復(fù)這個(gè)過程k次魁亦。

3渔隶、使用貪心算法實(shí)現(xiàn)哈夫曼編碼

3.1 什么是哈夫曼編碼

哈夫曼編碼是一種十分有效的編碼方法，廣泛應(yīng)用于數(shù)據(jù)壓縮中洁奈，其壓縮率通常在20%~90%之間间唉。哈夫曼編碼通過采用不等長的編碼方式，根據(jù)字符頻率的不同利术，選擇不同長度的編碼呈野，對頻率越高的字符采用越短的編碼實(shí)現(xiàn)數(shù)據(jù)的高度壓縮。這種對頻率越高的字符采用越短的編碼來編碼的方式應(yīng)用的就是貪心算法的思想印叁。

哈夫曼編碼具體是什么呢被冒？我們采用一個(gè)實(shí)例來具體看一下军掂。

假如我們有一個(gè)包含1000個(gè)字符的文件，每個(gè)字符占1個(gè)byte(1byte=8bits)昨悼，則存儲這100個(gè)字符一共需要8000bits蝗锥，是否有更節(jié)省空間的存儲方式呢？

如果我們統(tǒng)計(jì)一下這1000個(gè)字符中總共有多少種字符率触，原來需要8bit是來表示一個(gè)字符玛追，我們使用更少的位數(shù)來表示這些字符，則可以減少存儲空間闲延。假設(shè)這1000個(gè)字符中總共有a痊剖、b、c垒玲、d陆馁、e、f共6種字符合愈，則我們只需要使用3個(gè)二進(jìn)制位來表示叮贩，那存儲這1000個(gè)字符就只需要3000bits，比原來更節(jié)省存儲空間佛析。

a(000)益老、b(001)、c(010)寸莫、d(011)捺萌、e(100)、f(101)

有沒有比這種方式更節(jié)省存儲空間的編碼方式呢膘茎？那就是哈夫曼編碼桃纯，哈夫曼編碼是怎么編碼的呢？它會根據(jù)字符出現(xiàn)的頻率給與字符不等長的編碼披坏，頻率越高的字符編碼越短态坦，頻率越高的字符編碼越長。當(dāng)然它不能像等長編碼一樣直接按固定長度去讀取二進(jìn)制位棒拂，翻譯成字符伞梯，為了能夠準(zhǔn)確讀取翻譯字符，它要求一個(gè)字符的編碼不能是另外一個(gè)字符的前綴帚屉。

假設(shè)a谜诫、b、c涮阔、d猜绣、e灰殴、f這6個(gè)字符出現(xiàn)的頻率依次降低敬特，則我們可以給與他們這樣的編碼

a(1)掰邢、b(01)、c(001)伟阔、d(0001)辣之、e(00001)、f(00000)

字符頻率和編碼皱炉，每種字符需要的總的存儲位數(shù)如圖怀估，我們可以看到使用哈夫曼編碼來存儲這1000個(gè)字符只需要2100bits，相同的方式下合搅，比等長bit壓縮更節(jié)省空間了多搀。

哈夫曼編碼的思想不難理解，但是我們?nèi)绾胃鶕?jù)字符出現(xiàn)的頻率的不同灾部，給不同的字符進(jìn)行不同長度的編碼呢康铭？

3.2 哈夫曼編碼實(shí)現(xiàn)過程

哈夫曼編碼的實(shí)現(xiàn)過程如下：

1. 將每個(gè)字符看做一個(gè)節(jié)點(diǎn)，以頻率的大小作為權(quán)重赌髓，將所有的字符放到優(yōu)先級隊(duì)列中
2. 從優(yōu)先級隊(duì)列中取兩個(gè)權(quán)重最小的節(jié)點(diǎn)从藤，創(chuàng)建一個(gè)新的節(jié)點(diǎn)作為他們的父節(jié)點(diǎn)，父節(jié)點(diǎn)的權(quán)重為兩個(gè)字節(jié)的權(quán)重之和锁蠕，然后將父節(jié)點(diǎn)插入優(yōu)先級隊(duì)列中夷野。然后再從優(yōu)先級隊(duì)列中取出兩個(gè)權(quán)重最小的節(jié)點(diǎn)，創(chuàng)建一個(gè)他們的父節(jié)點(diǎn)荣倾，權(quán)重等于兩個(gè)子節(jié)點(diǎn)之和悯搔，并插入優(yōu)先級隊(duì)列中。重復(fù)這個(gè)過程直到優(yōu)先級隊(duì)列中只有一個(gè)節(jié)點(diǎn)為止舌仍。
3. 優(yōu)先級隊(duì)列中只有一個(gè)節(jié)點(diǎn)的時(shí)候鳖孤，哈夫曼樹就創(chuàng)建好了，所有的字符對應(yīng)的節(jié)點(diǎn)都在這顆哈夫曼樹的葉子結(jié)點(diǎn)上抡笼，然后我們開始編碼苏揣，從根節(jié)點(diǎn)開始，指向左子節(jié)點(diǎn)的邊推姻，我們統(tǒng)統(tǒng)標(biāo)記為0平匈，指向右子節(jié)點(diǎn)的邊，我們通過標(biāo)記為1藏古，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路徑就是葉子節(jié)點(diǎn)對應(yīng)的哈夫曼編碼

上面的例子的計(jì)算編碼的過程圖示如下：

構(gòu)建哈夫曼樹的過程

計(jì)算編碼的過程

3.2 代碼實(shí)現(xiàn)

1. 構(gòu)建哈夫曼樹
2. 獲取哈夫曼編碼
3. 將編碼轉(zhuǎn)換成字符串

public class HuffmanTree {
    /**
     * 創(chuàng)建哈夫曼樹
     *
     * @param list
     * @param <T>
     * @return
     */
    public static <T> Node createTree(List<Node<T>> list) {
        if (list == null) {
            return null;
        }
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (int i = 0; i < list.size(); i++) {
            queue.add(list.get(i));
        }
        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();
            Node node = new Node(left.pow + right.pow, left, right);
            queue.add(node);
        }
        return queue.poll();
    }

    /**
     * 獲取哈夫曼編碼（編碼這里使用字符串表示）
     *
     * @param node
     * @param <T>
     * @return
     */
    public static <T> Map<T, String> getCode(Node<T> node) {
        if (node == null) {
            return null;
        }
        Map<T, String> map = new HashMap<>();
        if (node.left != null && node.left != null) {
            List<String> codes = new ArrayList<>();
            traverse(node, map, codes);
        } else {
            map.put(node.item, "0");
        }
        return map;
    }

    private static <T> void traverse(Node<T> node, Map<T, String> map, List<String> codes) {
        if (node.left == null && node.right == null) {
            StringBuilder builder = new StringBuilder();
            for (int i = 0; i < codes.size(); i++) {
                builder.append(codes.get(i));
            }
            map.put(node.item, builder.toString());
        }
        //左子樹
        if (node.left != null) {
            codes.add("0");
            traverse(node.left, map, codes);
            codes.remove(codes.size() - 1);
        }
        //右子樹
        if (node.right != null) {
            codes.add("1");
            traverse(node.right, map, codes);
            codes.remove(codes.size() - 1);
        }
    }

    /**
     * 根據(jù)哈夫曼編碼增炭，解析出字符串
     *
     * @param map
     * @param codeStr
     * @param <T>
     * @return
     */
    public static <T> String reCode(Map<T, String> map, String codeStr) {
        if (map == null) {
            return "";
        }
        //將key和value倒過來
        Map<String, T> map2 = new HashMap<>();
        for (T key : map.keySet()) {
            map2.put(map.get(key), key);
        }
        StringBuilder builder = new StringBuilder();
        while (codeStr.length() > 0) {
            for (String key : map2.keySet()) {
                if (codeStr.startsWith(key)) {
                    builder.append(map2.get(key));
                    codeStr = codeStr.replaceFirst(key, "");
                    break;
                }
            }
        }
        return builder.toString();
    }


    public static class Node<T> implements Comparable<Node> {
        T item;
        int pow;
        Node<T> left;
        Node<T> right;

        public Node() {
        }

        public Node(T item, int pow) {
            this.item = item;
            this.pow = pow;
        }

        public Node(int pow, Node<T> left, Node<T> right) {
            this.pow = pow;
            this.left = left;
            this.right = right;
        }

        @Override
        public int compareTo(Node o) {
            return pow - o.pow;
        }
    }
}

測試

/**
 * 驗(yàn)證編碼與反編碼
 */
@Test
public void test2() {
    int size = 20;
    //創(chuàng)建原始的數(shù)據(jù)
    char[] chars = getChars(size);
    //統(tǒng)計(jì)字符出現(xiàn)的頻率，構(gòu)建字符節(jié)點(diǎn)
    List<HuffmanTree.Node<Character>> list = getNodes(size, chars);
    print(list, " org node:");
    //創(chuàng)建哈夫曼樹
    HuffmanTree.Node<Character> root = HuffmanTree.createTree(list);
    //獲取哈夫曼編碼（這里以字符串表示二進(jìn)制）
    Map<Character, String> codeMap = HuffmanTree.getCode(root);
    print(codeMap, "node code:");
    //輸出原始數(shù)據(jù)
    System.out.println("   orgStr:" + new String(chars));
    //編碼原始數(shù)據(jù)
    StringBuilder codeBuilder = new StringBuilder();
    for (int i = 0; i < size; i++) {
        Character ch = chars[i];
        codeBuilder.append(codeMap.get(ch));
    }
    String codeStr = codeBuilder.toString();
    System.out.println("code:" + codeStr);
    //解析編碼
    String reCodeStr = HuffmanTree.reCode(codeMap, codeStr);
    System.out.println("recodeStr:" + reCodeStr);
}

測試結(jié)果

 org node:{a:1},{e:2},{f:3},{h:3},{j:1},{k:2},{n:1},{r:1},{t:1},{v:2},{w:1},{x:1},{z:1},
node code:{a:0010},{e:011},{f:101},{h:110},{j:0000},{k:1110},{n:0100},{r:0001},{t:11110},{v:100},{w:11111},{x:0101},{z:0011},
   orgStr:fxafkzhfkvnhvehjwter
code:101010100101011110001111010111101000100110100011110000011111111100110001
recodeStr:fxafkzhfkvnhvehjwter

我們可以看到編碼能夠再次轉(zhuǎn)換成原始的字符串拧晕，說明我們設(shè)計(jì)的哈夫曼編碼算法是正常的

4隙姿、源碼地址

完整的源碼和測試用例，請查看github之貪心算法

5厂捞、說明

文中圖片來源：極客時(shí)間输玷，王爭《數(shù)據(jù)結(jié)構(gòu)與算法之美》