贪心算法(三)——最佳合并模式

问题描述

给定n个有序文件，每个文件的记录数分别为w1~wn，请给出一种两两合并的方案，使得总合并次数最少。

注意：
1. 外排序算法是将多个有序文件合并成一个有序文件的过程。
2. 在一次合并的过程中，两个文件中的所有记录都需要先从文件中读入内存，再在内存中排序，最后将排序的结果写入文件中。
3. 假设两个待排序文件记录数分别为n、m，那么将这两个文件合并成一个有序的文件需要进行n+m次读写。

问题转化

n个文件两两合并的过程可以用一棵扩充二叉树来表示。因为扩充二叉树只有度为2或0的节点，没有度为1的节点，这符合两两合并的过程。

在这棵扩充二叉树中：
1. 方形节点（外界点）表示原始的文件，圆形节点（内节点）表示合并过程中的文件；
2. 节点的权值表示文件的记录数
因此，n个文件合并过程的总读写次数为带权外路径长度之和。
要求最小的合并次数即为求最小的带权外路径长度之和。
因此，问题就转化为『如何求扩充二叉树的最小加权路径』。
这个问题可以用哈夫曼算法解决。

哈夫曼算法

思路

若要使得带权外路径长度最小，可以将权值大的节点尽量靠近根节点，这样路径短一些；而权值小的节点可以适当远离根节点，因为权值小，外路径稍微长一点也没事。

伪代码

1. 用一个优先权队列存储所有的初始节点；
2. 从队列中选出两个权值最小的节点，将它们的和作为它们的根节点，并放入队列中；
3. 循环这个过程，直到队列中只有一个节点为止，此时具有最小带权路径的扩充二叉树构造完毕！此时带权外路径长度即为最小的读写次数。

代码实现

/**
 * 构造二叉树的节点类
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val){
        this.val = val;
    }
}

• 1

/**
 * 构造哈夫曼树
 * @param w：所有节点的权值
 * @return 哈夫曼树的根节点
 */
TreeNode hfmTree(int[] w){
    // 将所有节点存入优先权队列，按照权值递增排序
    PriorityQueue<TreeNode> queue = new PriorityQueue<>(w.length, new Comparator<TreeNode>(){
        public int compare(TreeNode t1,TreeNodet2){
            return t1.val-t2.val;
        }
    });
    for(int i=0; i<w.length; i++){
        queue.offer(new TreeNode(w[i]));
    }
 
    // 构造哈夫曼树
    while( queue.size()>1 ){
        // 弹出最小的两个节点
        TreeNode node1 = queue.poll();
        TreeNode node2 = queue.poll();
        // 构造父节点
        TreeNode father = new TreeNode(node1+node2);
        father.left = node1;
        father.right = node2;
        // 父节点入队
        queue.offer( father );
    }
 
    return queue.poll();
}