# Poj Solution 1521

```http://poj.org/problem?id=1521

import java.math.BigDecimal;
import java.math.RoundingMode;

/**
* Accepted.
*
*
* @author hong
*
*/
public class Main {
private static Node[] nodes = new Node[1000];
private static boolean[] used = new boolean[1000];
private static int count = 0;
static int p = 0;

private static int getIndex(char s) {
for (int i = 0; i < p; i++) {
if (nodes[i].c == s) {
return i;
}
}

return -1;
}

/**
* Construct the Huffman Tree.
*
* @return
*/
private static void constructHuffmanTree() {

for (int i = 0; i < p; i++) {
used[i] = false;
}

while (true) {

// first find the min occurence for unused node, there always be such one node.
int min = Integer.MAX_VALUE;
int min1_index = 0;

for (int i = 0; i < p; i++) {
if (!used[i] && nodes[i].occur < min) {
min = nodes[i].occur;
min1_index = i;
}
}

// use the min1_index node.
used[min1_index] = true;

// try to find the second min node, if this node is not found, break the while.
int min2 = Integer.MAX_VALUE;
int min2_index = 0;

for (int i = 0; i < p; i++) {
if (!used[i] && nodes[i].occur < min2) {
min2 = nodes[i].occur;
min2_index = i;
}
}

if (min2 == Integer.MAX_VALUE) {
break;
}

used[min2_index] = true;

// construct a new Node.
Node newNode = new Node();
newNode.occur = nodes[min1_index].occur + nodes[min2_index].occur;
newNode.left = nodes[min1_index];
newNode.right = nodes[min2_index];

nodes[p] = newNode;
used[p] = false;
p++;
}
}

private static void travTree(Node tree, int depth) {
if (tree != null) {

tree.depth = depth;

if (tree.left == null && tree.right == null) {
// find a leaf.
count += tree.occur * depth;
}

if (tree.left != null) {
travTree(tree.left, depth + 1);
}

if (tree.right != null) {

travTree(tree.right, depth + 1);
}
}
}

/**
* @param args
*/
public static void main(String[] args) throws Exception {

while (true) {
String line = stdin.readLine().trim();

if ("END".equals(line)) {
break;
}

p = 0;

for (int i = 0; i < line.length(); i++) {

int index = getIndex(line.charAt(i));

if (index == -1) {
Node node = new Node(line.charAt(i));
node.occur = 1;

nodes[p] = node;
p++;
} else {
nodes[index].occur++;
}
}

constructHuffmanTree();

int current = 8 * line.length();

if (p == 1) {
count = line.length();

System.out.println(current + " " + count + " "
+ new BigDecimal(current * 1.0 / count).setScale(1, RoundingMode.HALF_UP));

} else {

count = 0;

travTree(nodes[p - 1], 0);

System.out.println(current + " " + count + " "
+ new BigDecimal(current * 1.0 / count).setScale(1, RoundingMode.HALF_UP));
}

}

}

static class Node {
char c;
int depth = 0;
int occur;
Node left = null;
Node right = null;

public Node(char c) {
this.c = c;
}

public Node() {
}

}

}

```
This entry was posted in poj. Bookmark the permalink.