ヘフマンツリーの構築

ヘフマンツリー:重み付きパスが最小のツリー

public class HuffmanTree
{
     publlic class Node implements Comparable
     {
          int weight;
          Node left = null;
          Node right = null;
          public Node (int weight)
          {
                this.weight = weight;
          }
          //  Comparable         Node      
           @Override
        public int compareTo(Node o) 
        {
            return -(this.value - o.value);//        
        }
     }
     //          
     public Node CreateHuffmanTree(int[] data)
     {
          //                 （              ）
          ArrayList list = new ArrayList();
          for(int i = 0; i < data.length; i++)
          {
               list.add(new Node(data[i]));
          }
          while(list.size() > 1)
          {
                //   list    
                Collections.sort(list);
                //             
                Node left = list.get(list.size() - 1);
                Node right = list.get(list.size() - 2);
                //               
                Node Parent = new Node(left.weight+right.weight);
                Parent.left = left;
                Parent.right = right;
                //              
                list.remove(left);
                list.remove(right);
                //             
                list.add(Parent);
          }
          //                   
          return list.get(0);
     }
     
}