接口--Comparable接口【哈夫曼树】

我们在字符串中见到过CompareTo方法,知道这个方法是用于比较字符串顺序的,根据字典顺序进行排序。Java中很多类也都有CompareTo方法，甚至于排序算法的底层组成也是依赖于比较的，而这个比较就是依赖于各种数据类型的CompareTo或者Compare方法。Java中所有的compareTo方法都源于一个共同的接口，那就是Comparable。这个接口只有一个方法，那就是CompareTo。所有想要具有比较功能的类，都建议实现这个接口，而非是自己定义这个功能，这是面向对象的概念（将具有相同功能的事物抽象到一个共同的类或接口），并且为了多态也建议通过实现接口来进行向上转型，通过接口来操作具体实现，这也是面向接口编程要求我们做的。下面我们来具体了解一下Comparable接口。

此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的 compareTo 方法被称为它的自然比较方法。实现此接口的对象列表（和数组）可以通过 Collections.sort（和Arrays.sort）进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

在创建哈夫曼树的时候用到了给list中的元素排序：

public class Node implements Comparable<Node> {

    private int value;

    private Node left;

    private Node right;

    public Node(int value) {

        this.value = value;

    }

    @Override

    public String toString() {

        return "[value=" + value + "]";

    }

    public int compareTo(Node o) {

//        return this.value - o.value;//从小到大

        return -(this.value - o.value);//从大到小

    }

    public int getValue() {

        return value;

    }

}

public class TestHaffmanTree {

    public static void main(String[] args) {

        int[] arr = {3,7,8,29,5,11,23,14};

        Node nodeHaffman = creatHaffman(arr);

        System.out.println(nodeHaffman);

    }

    public static Node creatHaffman(int[] arr) {

        //先使用数组中的所有元素创建若干二叉树

        List<Node> list = new ArrayList<Node>();

        for (int value : arr) {

            list.add(new Node(value));

        }

        //循环处理

        while(list.size()>1) {

            //排序

            Collections.sort(list);

            //取出权值最小的两颗二叉树(已经排好序了，是最后两个)

            Node left = list.get(list.size()-1);

            Node right = list.get(list.size()-2);

            //创建一颗新的二叉树

            Node parent = new Node(left.getValue()+right.getValue());

            //把原来的两个二叉树移除

            list.remove(left);

            list.remove(right);

            //将新的二叉树放入list中

            list.add(parent);

        }

        //System.out.println(list.size());

        return list.get(0);//剩下的最后那一个就是哈夫曼树了

    }

}