数据结构和算法学习笔记五_树结构的实际应用(1)

package com.lxf.Tree;

import java.util.Arrays;
import java.util.Random;

public class HeapSort {
    public static void main(String[] args) {
        //获取一个数字字符串
        StringBuilder stringBuilder = new StringBuilder();
        Random random = new Random();
        for (int i = 0; i < 100000; i++) {
            stringBuilder.append(random.nextInt(500)+",");
        }
        //去掉最后一个,
        stringBuilder.setLength(stringBuilder.length()-1);
        //获取整数数组
        String[] splits= stringBuilder.toString().split(",");
        int[] nums = Arrays.stream(splits).mapToInt(Integer::valueOf).toArray();
        //获取开始时间
        long  start = System.currentTimeMillis();
        System.out.println("start = " + start);
        //堆排序排序算法
        heapSort(nums);
        //获取执行完的时间
        long end = System.currentTimeMillis();
        System.out.println("end = " + end);
        //计算执行时间
        long sub=end-start;
        System.out.println("花费时间="+sub);

        //三次测试：27.218秒 24.579秒 27.254秒
    }

    /**
     * 堆排序
     *
     * @param arr
     */
    public static void heapSort(int arr[]) {
        for (int i = arr.length - 1; i > 0; i--) {
            max_heapify(arr, i);
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
        }
    }

    /**
     * 构造大根堆
     *
     * @param arr 数组
     * @param n   当前构造大根堆数组的长度
     *            注意：这个树必须是完全二叉树
     */
    private static void max_heapify(int arr[], int n) {
        for (int j = (n - 1) / 2; j >= 0; j--) {
            int children = 2 * j + 1;
            if (children != n && arr[children] < arr[children + 1]) {
                children++;
            }
            if (arr[j] < arr[children]) {
                int temp = arr[j];
                arr[j] = arr[children];
                arr[children] = temp;
            }
        }
    }
}

二、赫夫曼树（哈夫曼树）

2.1、基本介绍

1. 给定 n 个权值作为 n 个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为

最优二叉树，也称为哈夫曼树(Huffman Tree), 还有的书翻译为霍夫曼树。

2. 赫夫曼树是带权路径长度最短的树，权值较大的结点离根较近

2.2、赫夫曼树几个重要概念和举例说明

1. 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路

中分支的数目称为路径长度。若规定根结点的层数为 1，则从根结点到第 L 层结点的路径长度为 L-1

2. 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结

点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积

3. 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为 WPL(weighted path

length) ,权值越大的结点离根结点越近的二叉树才是最优二叉树。

4. WPL 最小的就是赫夫曼树

2.3、赫夫曼树创建思路图解

问题：给你一个数列 {13, 7, 8, 3, 29, 6, 1}，要求转成一颗赫夫曼树.

构成赫夫曼树的步骤：

1. 从小到大进行排序, 将每一个数据，每个数据都是一个节点 ， 每个节点可以看成是一颗最简单的二叉树

2. 取出根节点权值最小的两颗二叉树

3. 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树根节点权值的和

4. 再将这颗新的二叉树，以根节点的权值大小 再次排序， 不断重复 1-2-3-4 的步骤，直到数列中，所有的数

据都被处理，就得到一颗赫夫曼树

5. 图解:

package com.lxf.huffmanTree;

import java.util.PriorityQueue;

public class HuffmanTreeDemo{
    public static void main(String[] args) {
        int[] arr={13,7,8,3,29,6,1};
        //创建哈夫曼树
        Node root = createHuffmanTree(arr);
        //前序遍历打印哈夫曼树
        //预期：67、29、38、15、7、8、23、10、4、1、3、6、13
        HuffmanTree huffmanTree = new HuffmanTree(root);
        huffmanTree.preOrder();
        //结果：67 29 38 15 7 8 23 10 4 1 3 6 13 
    }

    /**
     * 创建赫夫曼树的方法
     * @param arr
     */
    public static Node createHuffmanTree(int[] arr){
        //为了操作方便
        //1.遍历arr数组
        //2.将arr的每个元素构成一个Node
        //3.将Node放入PriorityQueue中(已实现Comparable接口，所以nodes是有序的)
        PriorityQueue<Node> nodes = new PriorityQueue<Node>();
        for (int value : arr) {
            nodes.offer(new Node(value));
        }
        //从nodes中反复取出最小的两个节点拼接成一个子树(子树的节点值为最小的两个节点和)
        while(nodes.size()!=1){
            //获取第一个节点
            Node left = nodes.poll();
            //获取第二个节点
            Node right = nodes.poll();
            //拼接节点
            Node parent=new Node(left.value+right.value);
            parent.left=left;
            parent.right=right;
            //再将节点加入
            nodes.add(parent);
        }
       return nodes.peek();
    }
}
/**
 * 定义BinaryTree二叉树
 */
class HuffmanTree {
    private Node root;

    public HuffmanTree() {
    }

    public HuffmanTree(Node root) {
        this.root = root;
    }
    //前序遍历
    public  void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }else{
            System.out.println("二叉树为空,无法遍历");
        }
    }

}
/**
 * 创建结点类
 * 为了让Node对象持续排序Collection集合排序
 * 让Node实现Comparable接口
 */
class Node implements Comparable<Node>{
    int value;//结点权值
    Node left;//指向左子结点
    Node right;//指向右子结点

    public Node(int value){
        this.value=value;
    }


    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    /**
     * 前序遍历的方法
     */
    public void preOrder(){
        System.out.print(this.value+" ");//先输出父节点的值
        //递归向左子树前序遍历
        if(this.left!=null){
            this.left.preOrder();
        }
        //递归向右子树前序遍历
        if(this.right!=null