HuffmanNode implements Comparable<HuffmanNode> { protected static HuffmanNode makeTree(final List<HuffmanNode> list) { HuffmanNode node1, node2, tmp; int size = list.size(); for (int i=0; i<size-1; i++) { node1 = list.get(i); int n = i; for (int j=i+1; j<size; j++) { tmp = list.get(j); if (node1.compareTo(tmp) < 0) { node1 = tmp; n = j; } } if (i != n) { Collections.swap(list, i, n); } } while (list.size() > 1) { size = list.size(); node1 = list.get(0); int n = 0; for (int i=1; i<size; i++) { tmp = list.get(i); if (node1.compareTo(tmp) >= 0) { node1 = tmp; n = i; } } list.remove(n); size = list.size(); node2 = list.get(0); n = 0; for (int i=1; i<size; i++) { tmp = list.get(i); if (node2.compareTo(tmp) >= 0) { node2 = tmp; n = i; } } list.remove(n); list.add(new HuffmanNode(node1, node2)); } return list.get(0); } protected  HuffmanNode(final long value, final int frequency, final int leafType); protected  HuffmanNode(final HuffmanNode left, final HuffmanNode right); int hashCode(); boolean equals(final Object obj); @Override int compareTo(final HuffmanNode node);  }
@Test(groups={"tree"}) public void testMakeTree() throws Exception { ArrayList<HuffmanNode> list = new ArrayList<>(10); list.add(new HuffmanNode('A', 2, HuffmanNode.LEAF_32)); nodeB = new HuffmanNode('B', 5, HuffmanNode.LEAF_32); list.add(nodeB); list.add(new HuffmanNode('C', 3, HuffmanNode.LEAF_32)); list.add(new HuffmanNode('D', 1, HuffmanNode.LEAF_32)); list.add(new HuffmanNode('E', 1, HuffmanNode.LEAF_32)); list.add(new HuffmanNode(256, 1, HuffmanNode.LEAF_EOF)); root = HuffmanNode.makeTree(list); assertEquals(root.getFrequency(), 13); }