数据结构与算法学习六（基于JavaScript）---- 哈夫曼树

也称最优二叉树。是带权路径长度最小的二叉树。

概念：

1、路径长度

路径： 从树中的一个节点到另一个节点之间的分支构成这两点之间的路径
路径长度：路径上的分支条数，树的路径长度是从树的根节点到每个节点的路径长度之和。

2、带权路径长度

节点的带权路径长度为从该节点到根节点之间的路径长度与节点上权的乘积。树的带权路径长度为树中所有叶子节点的带权路径长度之和。记为WPL。
如下图：

图a WPL = 2*(2+4+5+7) = 36
图b WPL = 2+42+3(5+7) = 46
图c WPL = 7+52+3(2+4) = 35

其中图c 的WPL最小，为哈夫曼树。节点权值越大，距离根节点就越近。

哈夫曼算法：

哈夫曼算法是构造权值集合为{w0,w1…wn}的哈夫曼树，其算法思路如下：
1、根据给定的n个权值{w0,w1…wn},构造具有n棵扩充二叉树的森林 F={T0,T1,…Tn},对于每棵扩充二叉树Ti只有一个带权值的Wi的根节点，左右子树都为空。
2、重复一下步骤，直到F中只剩下一棵树为止
（1）、在F中选取两棵根节点的权值最小的扩充二叉树，把这两棵树作为左右子树构造一颗新的二叉树，这个新的二叉树的根节点的权值为其左右两棵子树根节点的权值之和
（2）、在F中删除第一步中选取的两棵二叉树
（3）、将第一步中构造的新的二叉树加入到F中
最后得到的就是哈夫曼树。

例子：如给定的权值集合为{7,5,2,4},构造哈夫曼树的过程如下：

哈夫曼编码：

在通信领域，经过哈夫曼编码的信息小于大量冗余数据，提高传输效率，是重要的数据压缩方法。

一段信息由a,b,c,d,e 5个字符组成，各自出现的概率是0.12 0.4 0.15 0.08 0.25 ，把这几个字符串编码成二进制的01序列，有两种方法：一种是定长编码，一种是变长编码。如下图

如果采用定长编码，平均编码长度为（0.12+0.4+0.15+0.08+0.25）3 = 3
如果采用变长编码，平均编码长度为 0.124+0.41+0.153+0.084+0.252 = 2.15

先入采用变长编码更加高效，变长编码的的二叉树表示如下

哈夫曼算法每次都要从F中找出权值最小的两个根节点，构造出新的树以后，删除这两个根节点并加入新构造的树，这个过程用最小堆来实现最合适。
先将森林里的根节点加入到一个最小堆中，循环n-1次，每次循环，先连续两次删除最小堆的堆顶，利用这两个堆顶，构造新的树并将新的树的根节点放入到最小堆中，堆顶就是哈夫曼树的根节点。

//定义存储编码和概率的类

// 编码
var CodeNode = function(code, rate){
    this.code = code;     // 字符
    this.rate = rate;     // 概率
};
//定义树节点
var TreeNode = function(data){
    this.data = data;
    this.leftChild = null;
    this.rightChild = null;
    this.parent = null;
};
// 准备数据
var code_dict = {
    "a": 0.12,
    "b": 0.4,
    "c": 0.15,
    "d": 0.08,
    "e": 0.25
};
var forest = [];

for(var key in code_dict){
    var item = new CodeNode(key, code_dict[key]);
    forest.push(new TreeNode(item));
}

//哈夫曼树类定义
function HuffmanTree(){
    var root = null;

    this.init_tree = function(arr){
        var min_heap = new MinHeap();
        min_heap.init(arr);
       
        for(var i = 0;i < arr.length - 1; i++){
            var first = min_heap.remove_min();
            var second = min_heap.remove_min();
                var new_item = new CodeNode("", first.data.rate + second.data.rate);
                var new_node = new TreeNode(new_item);
                console.log(min_heap.insert(new_node));
    
                new_node.leftChild = first;
                new_node.rightChild = second;
                first.parent = new_node;
                second.parent = new_node;
    
                root = new_node;           
        }
    };

    var get_code_from_tree = function(node, dict, code_str){
        if(!node.leftChild && !node.rightChild){
            // 页节点
            dict[node.data.code] = code_str;
            return;
        }

        if(node.leftChild){
            get_code_from_tree(node.leftChild, dict, code_str+"0");
        }
        if(node.rightChild){
            get_code_from_tree(node.rightChild, dict, code_str+"1");
        }
    };

    this.get_code = function(){
        // 获得最终的变长编码
        var code_dict = {};
        get_code_from_tree(root, code_dict, "");
        return code_dict;
    };

    this.print = function(){
        console.log(root);
    };
};
//最小堆实现
function MinHeap(size){
    var heap = new Array(size);
    var curr_size = 0;
    var max_size = size;


    var shif_down = function(start, m){
        // 从start这个位置开始,向下下滑调整
        var parent_index = start;                       // start就是当前这个局部的父节点
        var min_child_index = parent_index*2 + 1;       // 一定有左孩子,先让min_child_index等于左孩子的索引

        while(min_child_index <= m){
            // min_child_index+1 是左孩子的索引, 左孩子大于右孩子
            if(min_child_index < m && heap[min_child_index].data.rate > heap[min_child_index+1].data.rate){
                min_child_index = min_child_index+1;  // min_child_index永远指向值小的那个孩子
            }

            // 父节点的值小于等于两个孩子的最小值
            if(heap[parent_index].data.rate <= heap[min_child_index].data.rate){
                break;   // 循环结束,不需要再调整了
            }else{
                // 父节点和子节点的值互换
                var tmp = heap[parent_index];
                heap[parent_index] = heap[min_child_index];
                heap[min_child_index] = tmp;
                parent_index = min_child_index;
                min_child_index = 2*min_child_index + 1;
            }
        }

    };

    // 传入一个数组,然后调整为最小堆
    this.init = function(arr){
        max_size = arr.length;
        curr_size = max_size;
        heap = new Array(arr.length);
        // 填充heap, 目前还不是一个堆
        for(var i =0; i<curr_size;i++){
            heap[i] = arr[i];
        }

        var curr_pos = Math.floor(curr_size/2);      // 这是堆的最后一个分支节点
        while(curr_pos >= 0){
            shif_down(curr_pos, curr_size-1);        // 局部自上向下下滑调整
            curr_pos -= 1;                           // 调整下一个分支节点
        }
    };

    var shif_up = function(start){
        var child_index = start;         // 当前节点是叶节点
        var parent_index = Math.floor((child_index-1)/2);   // 找到父节点


        while(child_index > 0){
            // 父节点更小,就不用调整了
            if(heap[parent_index].data.rate <= heap[child_index].data.rate){
                break;
            }else{
                // 父节点和子节点的值互换
                var tmp = heap[child_index];
                heap[child_index] = heap[parent_index];
                heap[parent_index] = tmp;
                child_index = parent_index;
                parent_index = Math.floor((parent_index-1)/2);
            }
        }
    };

    this.insert = function(item){
        // 插入一个新的元素
        // 堆满了,不能再放元素
        if(curr_size == max_size){
            return false;
        }

        heap[curr_size] = item;
        shif_up(curr_size);
        curr_size++;
        return true;
    };

    //删除最小值
    this.remove_min = function(){
        if(curr_size <= 0){
            return null;
        }
        var min_value = heap[0];
        heap[0] = heap[curr_size-1];
        curr_size--;
        shif_down(0, curr_size-1);
        return min_value;
    };

    this.size = function(){
        return curr_size;
    };

    this.print = function(){
        console.log(heap);
    };
};
var huffman_tree = new HuffmanTree();
huffman_tree.init_tree(forest);
console.log(huffman_tree.get_code());