Breaking
Priority Queue

# Huffman Algorithm

Huffman coding is a lossless data compression algorithm and derives this table based on the estimated frequency of occurrence for each possible value of the source symbol.

Write a program to implement Huffman code for given string?

## Source Code

```package com.dsacode.DataStructre.priorityqueue;

import java.util.PriorityQueue;

abstract class HuffmanTree implements Comparable < HuffmanTree > {
public final int frequency;
public HuffmanTree(int freq) { frequency = freq; }

public int compareTo(HuffmanTree tree) {
return frequency - tree.frequency;
}
}

class HuffmanLeaf extends HuffmanTree {
public final char value;

public HuffmanLeaf(int freq, char val) {
super(freq);
value = val;
}
}

class HuffmanNode extends HuffmanTree {
public final HuffmanTree left, right;

public HuffmanNode(HuffmanTree l, HuffmanTree r) {
super(l.frequency + r.frequency);
left = l;
right = r;
}
}

public class HuffmanPriorityQueue {

public static HuffmanTree buildTree(int[] charFreqs) {
PriorityQueue < HuffmanTree > trees = new PriorityQueue < HuffmanTree >();

for (int i = 0; i < charFreqs.length; i++)
if (charFreqs[i] > 0)
trees.offer(new HuffmanLeaf(charFreqs[i], (char)i));

while (trees.size() > 1) {
HuffmanTree a = trees.poll();
HuffmanTree b = trees.poll();
trees.offer(new HuffmanNode(a, b));
}
return trees.poll();
}

public static void printCodes(HuffmanTree tree, StringBuffer prefix) {
assert tree != null;
if (tree instanceof HuffmanLeaf) {
HuffmanLeaf leaf = (HuffmanLeaf)tree;
System.out.println(leaf.value + "\t" + leaf.frequency + "\t" + prefix);
} else if (tree instanceof HuffmanNode) {
HuffmanNode node = (HuffmanNode)tree;

prefix.append('0');
printCodes(node.left, prefix);
prefix.deleteCharAt(prefix.length()-1);

prefix.append('1');
printCodes(node.right, prefix);
prefix.deleteCharAt(prefix.length()-1);
}
}

public static void main(String[] args) {
String test = "Hello world";

int[] charFreqs = new int;

for (char c : test.toCharArray())
charFreqs[c]++;

HuffmanTree tree = buildTree(charFreqs);

System.out.println("SYMBOL\tWEIGHT\tHUFFMAN CODE");
printCodes(tree, new StringBuffer());
}
}```

## Output

```SYMBOL  WEIGHT  HUFFMAN CODE
o   2   00
e   1   010
d   1   011
l   3   10
1   1100
w   1   1101
r   1   1110
H   1   1111```