Huffman coding 🎉

 

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

class node {

String name;

String path;

int value;

node left, right;

node(String n, int v) {

this.name = n;

this.value = v;

}

}

class MyCompare implements Comparator<node> {

public int compare(node n1, node n2) {

if (n2.value == n1.value) {

return 0;

}

if (n2.value  > n1.value) {

return -1;

}

return 1;

}

}

class huffman {

ArrayList<node> nodes = new ArrayList<>();

node root;

String names[];

int values[];

huffman(String n[], int v[]) {

this.names = n;

this.values = v;

createNode();

findAllPaths();

}

void createNode() {

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

node temp = new node(names[i], values[i]);

nodes.add(temp);

}

}

private void findAllPaths() {

node temp = null;

while (nodes.size() > 1) {

node min1 = nodes.get(0);

nodes.remove(0);

Collections.sort(nodes, new MyCompare());

node min2 = nodes.get(0);

nodes.remove(0);

Collections.sort(nodes, new MyCompare());

temp = new node(min1.name + min2.name, min1.value + min2.value);

temp.left = min1;

temp.right = min2;

nodes.add(temp);

}

root = temp;

nodes.clear();

}

private void printTree(node temp) {

if (temp.right != null && temp.left != null) {

System.out.println(temp.left.name + " : " + temp.right.name);

printTree(temp.left);

printTree(temp.right);

}

}

void printTree() {

if (root != null) {

System.out.println("root name :" + root.name);

printTree(root);

}

}

private void findpath(String target, String track, node temp){

if(temp == null){

return;

}

if(target == temp.name){

temp.path = track;

nodes.add(temp);

return;

}

findpath(target, track+"0", temp.left);

findpath(target, track+"1", temp.right);

}

private void AddActualNode(){

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

String x =" ";

findpath(names[i],x , root);

}

}

void PrintAllNode(){

AddActualNode();

for(node e: nodes){

System.out.println(""+e.name+": "+e.value+ ": "+e.path);

}

}

}

class work {

public static void main(String args[]) {

String names[] = {"z", "j", "k", "m", "o"};

int values[] = {1, 2, 3, 3, 4};

huffman obj = new huffman(names, values);

obj.printTree();

obj.PrintAllNode();

}

}