贪心算法(贪心算法和动态规划有什么区别)

  本篇文章为你整理了贪心算法(贪心算法和动态规划有什么区别)的详细内容,包含有贪心算法几个经典例子 贪心算法和动态规划有什么区别 贪心算法经典例题 贪心算法的时间复杂度由什么决定 贪心算法,希望能帮助你了解 贪心算法。

  给定n个权值最为n个叶子的节点,构建成一颗二叉树。如果次树的带权路径长度最小,则称此二叉树为最优二叉树,也叫哈夫曼树。

  WLP:带权路径长度

  
给定4个叶子节点,权值分别为{2,3,5,8},可以构造出4中形状不同的二叉树,但它们的带权路径长度可能不同。

  如上图可看出:1、最后两个树的带权路径长度相同且也是最小的,所以可看作哈夫曼树

  ​ 2、权值最小的节点越靠下,越大越靠近根节点

  2.构建哈夫曼树

  (1)、在{2,3,5,8}这几个节点看作叶子节点(即后面没有子节点)

  (2)、在这几个节点中选出权值最小和次小的两个节点。构成一个新二叉树(最小为左字节的、次小为右子节点),新二叉树的权值为这两个权值之和.

  (3)、删除已经使用过的节点。将新创建的节点加入到还没被使用过的节点集合中,找出最小和次小的节点权值。又构成一颗新的二叉树。

  (4)、重复(2)的操作

  (5)、重复上面操作:删除已使用的节点,将新的节点加入未使用节点的集合中,发现只有一个节点,其权值为18.则此哈夫曼树创建完成,根节点权值为18.

  代码如下:

  

 

 

  import java.util.ArrayList;

  import java.util.Collections;

  import java.util.List;

   * 构造哈夫曼树

  public class test1 {

   public static void main(String[] args) {

   int[] arr={2,3,5,8};

   //调用自定义的哈夫曼树方法,生成哈夫曼树

   hafmantree(arr);

   * ,构造哈夫曼数方法

   * @param arry

   public static void hafmantree(int[] arry) {

   //创建集合用于存放节点值

   List Node nlis = new ArrayList Node

   //遍历集合

   for (int value : arry) {

   //将每个数组元素看作Node节点对象,并存入list集合内

   nlis.add(new Node(value));

   由于集合中存入的是一个个的Node对象,而Node对象已经被我们声明成了按照从小到大的可排序对象。

   所以这里我们为可以通过Collections工具类中的sort方法进行排序

   //循环条件:只有一个节点,即最终根节点

   while (nlis.size() 1) {

   Collections.sort(nlis);

   //查看集合中还未被使用的节点

   System.out.println(nlis);

   //到了这里说明集合中的所有节点(权值)都是按照从小到大的顺序

   //获取最小的节点值(二叉树左节点):子节点

   Node lileft = nlis.get(0);

   //获取第2小的节点值(二叉树右节点):子节点

   Node lireght = nlis.get(1);

   /*创建新的Node节点对象(二叉树):

   此节点对象是最小的两个节点之和所生成的最新的节点。三个节点可以看成一个二叉树,即:

   根节点(insternode对象)、左子节点(lileft.value)、右子节点(lireght.value)

   Node insternode = new Node(lileft.value + lireght.value);

   //此二叉树的左节点

   insternode.left = lileft;

   //此二叉树的右节点

   insternode.right = lireght;

   //删除已经被处理过的节点

   nlis.remove(lileft);

   nlis.remove(lireght);

   //将最新的节点加入到list集合中

   nlis.add(insternode);

   //重新对最新的list数组进行排序

   Collections.sort(nlis);

   //查看最终根节点

   System.out.println(nlis);

  
* ,构造哈夫曼数节点类,

   * 此类也可以看成一个二叉树:根节点(Node对象)、左节子点(left)、右字节点(right)

   * 实现Comparable接口:说明此类是可通过Collections工具类排序的,

  class Node implements Comparable Node {

   int value; //每个节点的值(权值)

   Node left; //每个二叉树的左指向节点

   Node right; //每个二叉树的右指向节点

   //构造方法,这里只需要初始化value实例变量,用于对象的赋值,而 left 与 right 本身就是此对象,可直接用于value赋值

   public Node(int value) {

   this.value = value;

   @Override

   public String toString() {

   return "Node{" +

   "value=" + value +

   };

   //支持从小到大排序

   @Override

   public int compareTo(Node o) {

   return this.value - o.value;

  

 

  结果:

  3.构建哈夫曼编码

  
遍历已经创建好了的哈夫曼树,从它的根节点遍历次树到叶子节点,左子路径编码:0 、右子路径编码:1

  
HFMTable(node,"",andindex);

   System.out.println(yezijied); //{32=1010, 97=1011, 98=1100, 115=01, 100=111, 103=1101, 104=001, 106=100, 44=000}

  创建哈夫曼编码表:将叶子节点以0、1表示。0===》向左子节点走。1===》向右子节点走

   yezijied:存放叶子节点对应的哈夫曼编码。此集合作业与全局

   andindex:拼接编码。(拼接对应的0或1,形参最终的哈夫曼编码)

   static Map Byte,String yezijied=new HashMap ();

   static StringBuilder andindex=new StringBuilder();

   * @param node:节点

   * @param index:路径表示:左路径为0.右路劲为1

   * @param sub:拼接路径,使其成为对应叶子节点的哈夫曼码

  public static void HFMTable(Node node,String index,StringBuilder sub){

   StringBuilder gitindex=new StringBuilder(sub);

   //拼接路径

   gitindex.append(index);

   //如果节点为空就不需要处理

   if (node!=null) {

   //如果当前节点不是叶子节点

   if (node.value == null) {

   //如果节点不为空就递归其左边节点。并设置向左为0

   HFMTable(node.left, "0", gitindex);

   //如果节点不为空就递归其右边节点。并设置向右为1

   HFMTable(node.right, "1", gitindex);

   } else {

   //为叶子节点就将其存入map集合中

   yezijied.put(node.value, gitindex.toString());

   第三步:

   @param nodes:已经存入list集合中的Node节点

   创建字符串的哈夫曼树结构

   public static Node HFMTree(List Node nodes){

   //循环条件:节点数必须大于1.如果等于1就是一个节点(根节点),没有分支

   while (nodes.size() 1){

   //排序list集合,根据权值(节点个数)从小到大排序

   Collections.sort(nodes);

   创建一个二叉树:

   feiyezijied:根节点

   nodeleft:左子节点

   noderight:右子节点

   //得到权值最小的两个节点.这两个节点分别可看作左右两个子节点

   Node nodeleft = nodes.get(0);

   Node noderight = nodes.get(1);

   //创建新的Node对象:这可以想象为两个叶子节点生成的根节点,

   // 由于哈夫曼数的原理,需要编码的值是叶子节点,而叶子节点上的父节点只是通过叶子节点虚拟创建的节点,

   // 是为了形成一整颗完整的树。所以它是没有字符串原始值,,其可用两个字节的权值之和标记

   Node feiyezijied=new Node(null,nodeleft.quanzhi+noderight.quanzhi);

   //Node对象的左字节点

   feiyezijied.left=nodeleft;

   //Node对象的右字节点

   feiyezijied.right=noderight;

   //删除原集合中的以使用的节点对象.即上面已经每次获得的集合中两个最小的节点

   nodes.remove(nodeleft);

   nodes.remove(noderight);

   //将新创建的Node节点加入list集合中

   nodes.add(feiyezijied);

   //重新对list集合排序

   Collections.sort(nodes);

   //返回最终根节点

   return nodes.get(0);

  
@param valus:传入需要编码的字符串,将其变成节点

   将需要编码的字符串,每个原始值(ASCIIM码)以节点(Node)对象形式传入list集合中。

   而节点对象Node初始化了value与quanzhi,所以节点对象是包括这两个值,所以将每个节点对象当作一个map.

   设k=value、v=quanzhi

   public static List Node ListAndNode(String valus){

   //将字符对象存入byte数组。

   byte[] bytes = valus.getBytes();

   //创建List集合

   List Node nodes=new ArrayList ();

   //创建Map集合

   Map Byte,Integer node=new HashMap ();

   //遍历bytes数组,得到每个字符串的原始值

   for (byte by:bytes){

   //先试着通过传入的第一个k获取v

   Integer index = node.get(by);

   //如果map集合中此原始值对应的个数还没有

   if (index==null){

   node.put(by,1);

   }else {

   node.put(by,index+1);

   //遍历map集合,并将每次遍历的元素,以Node对象的形式存入list集合

   for (Map.Entry Byte,Integer n:node.entrySet()){

   nodes.add(new Node(n.getKey(),n.getValue()));

   //最后返回此list集合

   return nodes;

   第一步:

   节点类:其本身可可看作一个概念性的二叉树

   Node对象本身可看作是一个二叉树的根节点

   实现Comparable接口:泛型规定此接口作用与此Node节点,说明此类是可排序的,通过 Collections.sort()

  class Node implements Comparable Node {

   Byte value; //原始值:字符本身的ASCIIM码。因为一段字符串中有许多相同的字符,但相同字符却对应这一个ASCIIM码

   int quanzhi; //此字符value在一段字符串中出现的次数

   Node left; //Node对象看作是二叉树的根节点,那么这就是此二叉树的左子节点

   Node right; //Node对象看作是二叉树的根节点,那么这就是此二叉树的右边子节点

   //构造器初始化 value 、quanzhi。

   public Node(Byte value, int quanzhi) {

   this.value = value;

   this.quanzhi = quanzhi;

   //重写toString:因为我们需要拿到这两个值

   @Override

   public String toString() {

   return "Node{" +

   "value=" + value +

   ", quanzhi=" + quanzhi +

   };

   //实现Comparable接口中的方法:手动设置排序规则

   @Override

   public int compareTo(Node o) {

   //设置为通过权值从小到大排序

   return this.quanzhi-o.quanzhi;

   //前序遍历

   public void qxbl(){

   //先输出当前节点,也就是根节点

   System.out.println(this);

   //如果左子节点不是null节点,就递归遍历输出左子节点.null表示不是叶子节点

   if (this.left!=null){

   this.left.qxbl();

   //同样递归右子节点

   if (this.right!=null){

   this.right.qxbl();

  

 

 

  以上就是贪心算法(贪心算法和动态规划有什么区别)的详细内容,想要了解更多 贪心算法的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: