-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHuffManCoding.java
More file actions
50 lines (41 loc) · 1.16 KB
/
HuffManCoding.java
File metadata and controls
50 lines (41 loc) · 1.16 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
package Codes.GreddyAlgorithm;
import java.util.PriorityQueue;
class Node {
char ch;
int freq;
Node left, right;
Node (char c, int f, Node l, Node r){
ch=c;
freq=f;
left=l;
right=r;
}
}
public class HuffManCoding {
static void huffManCode(char arr[], int val[]){
PriorityQueue<Node> pq= new PriorityQueue<>((a, b)-> a.freq-b.freq);
for(int i=0;i<arr.length;i++)
pq.add(new Node(arr[i], val[i], null, null));
while(pq.size()>1){
Node l=pq.poll();
Node r=pq.poll();
pq.add(new Node('$', l.freq+r.freq,l, r));
}
printTree(pq.peek(), "");
}
static void printTree(Node root , String str){
if(root==null)
return;
if(root.ch!='$'){
System.out.print(root.ch+" "+str);
System.out.println();
}
printTree(root.left, str+"0");
printTree(root.right,str+"1");
}
public static void main(String[] args) {
char arr[]={'a', 'd', 'b', 'e', 'f'};
int val[]={10, 50, 20, 40, 80};
huffManCode(arr, val);
}
}