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

问题描述

给定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;
    }
}
/**
 * 构造哈夫曼树
 * @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();
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

34911
来自专栏java一日一条

经典数据结构和算法回顾

最近想回过头来看看以前写的一些代码,可叹为何刚进大学的时候不知道要养成写博客的好习惯。现在好多东西都没有做记录,后面也没再遇到相同的问题,忘的都差不多了。只能勉...

461
来自专栏青玉伏案

算法导论之插入排序和归并排序

  作为一名前线的码农不时地看一下算法和数据结构还是很有必要的,虽然《算法导论》这本书很难啃,但还是有必要啃一下的。算法这东西和某种编程语言关系不大,在大学的课...

2087
来自专栏一英里广度一英寸深度的学习

二叉树的深度优先遍历与广度优先遍历

先遍历子节点,再遍历兄弟节点。 从根节点开始递归,如果存在子节点,继续遍历子节点。

1483
来自专栏CDA数据分析师

入门 | 一文带你了解Python集合与基本的集合运算

了解 Python 集合: 它们是什么,如何创建它们,何时使用它们,什么是内置函数,以及它们与集合论操作的关系

800
来自专栏菩提树下的杨过

javascript:算法笔记

入门级算法-线性查找-时间复杂度O(n)--相当于算法界中的HelloWorld //线性搜索(入门HelloWorld) //A为数组,x为要...

16910
来自专栏DOTNET

.Net多线程编程—Parallel LINQ、线程池

Parallel LINQ 1 System.Linq.ParallelEnumerable 重要方法概览: 1)public static ParallelQ...

2797
来自专栏机器之心

入门 | 一文带你了解Python集合与基本的集合运算

了解 Python 集合: 它们是什么,如何创建它们,何时使用它们,什么是内置函数,以及它们与集合论操作的关系

983
来自专栏机器学习从入门到成神

牛客网刷题汇总(一)附解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1392
来自专栏xcywt

《大话数据结构》 查找 以及一个简单的哈希表例子

第八章 查找 定义:查找就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。 8.2 查找概论 查找表(Search table):...

51112

扫码关注云+社区