fork download
copy 
  1. import java.util.Scanner;
  2.  
  3. class HuffmanNode {
  4. 	int freq;
  5. 	String data;
  6.  
  7. 	HuffmanNode left;
  8. 	HuffmanNode right;
  9. }
  10.  
  11. public class Main {
  12.  
  13. 	public static void heapify(int A[], int i, int size) {
  14. 		int left = Left(i);
  15. 		int right = Right(i);
  16. 		int max = i;
  17. 		if (left < size && A[left] > A[max])
  18. 			max = left;
  19. 		if (right < size && A[right] > A[max])
  20. 			max = right;
  21.  
  22. 		if (max != i) {
  23. 			int temp = A[i];
  24. 			A[i] = A[max];
  25. 			A[max] = temp;
  26. 			heapify(A, max, size);
  27. 		}
  28. 	}
  29.  
  30. 	public static void buildHeap(int A[], int size) {
  31. 		for (int i = size / 2 - 1; i >= 0; i--) {
  32. 			heapify(A, i, size);
  33. 		}
  34. 	}
  35.  
  36. 	public static void heapSort(int A[], int size) {
  37. 		buildHeap(A, size);
  38. 		for (int treeSize = size - 1; treeSize >= 0; treeSize--) {
  39. 			int temp = A[0];
  40. 			A[0] = A[treeSize];
  41. 			A[treeSize] = temp;
  42. 			heapify(A, 0, treeSize);
  43. 		}
  44. 	}
  45.  
  46. 	public static int Left(int i) {
  47. 		return i * 2 + 1;
  48. 	}
  49.  
  50. 	public static int Right(int i) {
  51. 		return i * 2 + 2;
  52. 	}
  53.  
  54. 	public static int Parent(int i) {
  55. 		return (int) (i / 2);
  56. 	}
  57.  
  58. 	public static int HeapMax(int[] A) {
  59. 		return A[0];
  60. 	}
  61.  
  62.  
  63. 	public static int HeapExtractMax(int[] A) {
  64. 		if (A.length < 0) {
  65. 			return 0;
  66. 		}
  67. 		int max = A[0];
  68. 		A[0] = A[A.length - 1];
  69.  
  70.  
  71. 		return max;
  72. 	}
  73.  
  74. 	public static void HeapIncreaseKey(int[] A, int i, HuffmanNode key) {
  75. 		if (key.freq <= A[i]) {
  76. 			return;
  77. 		}
  78. 		A[i] = key.freq;
  79. 		while (i > 0 && A[Parent(i)] < A[i]) {
  80. 			int temp = A[i];
  81. 			A[i] = A[Parent(i)];
  82. 			A[Parent(i)] = temp;
  83. 			i = Parent(i);
  84. 		}
  85. 	}
  86.  
  87. 	public static void MaxHeapInsert(int[] A, HuffmanNode key) {
  88. 		int AHeapSize = A.length - 1;
  89. 		A[AHeapSize] = Integer.MIN_VALUE;
  90. 		HeapIncreaseKey(A, AHeapSize, key);
  91. 	}
  92.  
  93. 	public static int[] LossArr(int[] A) {
  94. 		int[] temp = new int[A.length - 1];
  95. 		for (int i = 0; i < A.length - 1; i++) {
  96. 			temp[i] = A[i];
  97. 		}
  98. 		return temp;
  99. 	}
  100.  
  101. 	public static int[] AddArr(int[] A) {
  102. 		int[] temp = new int[A.length + 1];
  103. 		for (int i = 0; i < A.length + 1; i++) {
  104. 			if (i < A.length) {
  105. 				temp[i] = A[i];
  106. 			} else {
  107. 				temp[i] = Integer.MIN_VALUE;
  108. 			}
  109.  
  110. 		}
  111. 		return temp;
  112. 	}
  113.  
  114. 	public static HuffmanNode Huffman(int[] C) {
  115. 		int[] Q = C;
  116. 		heapSort(Q, Q.length);
  117.  
  118. 		HuffmanNode root = new HuffmanNode();
  119. 		HuffmanNode rootTemp1 = new HuffmanNode();
  120. 		HuffmanNode rootTemp2 = new HuffmanNode();
  121. 		HuffmanNode rootTemp3 = new HuffmanNode();
  122. 		int mrtPoint = 0, rtPoint1 = 0, rtPoint2 = 0, rtPoint3 = 0;
  123. 		for (int i = 0; i < C.length - 1; i++) {
  124. 			HuffmanNode x = new HuffmanNode();
  125.  
  126. 			if (Q[0] != root.freq && Q[0] != rootTemp1.freq && Q[0] != rootTemp2.freq && Q[0] != rootTemp3.freq) {
  127. 				x.freq = HeapExtractMax(Q);
  128. 			} else if (Q[0] == root.freq && mrtPoint == 1) {
  129. 				x = root;
  130. 				HeapExtractMax(Q);
  131. 				// mrtPoint=0;
  132. 				// root=null;
  133. 			} else if (Q[0] == rootTemp1.freq && rtPoint1 == 1) {
  134. 				x = rootTemp1;
  135. 				HeapExtractMax(Q);
  136. 				rtPoint1 = 0;
  137. 			} else if (Q[0] == rootTemp2.freq && rtPoint2 == 1) {
  138. 				x = rootTemp2;
  139. 				HeapExtractMax(Q);
  140. 				rtPoint2 = 0;
  141. 			} else if (Q[0] == rootTemp3.freq && rtPoint3 == 1) {
  142. 				x = rootTemp3;
  143. 				HeapExtractMax(Q);
  144. 				rtPoint3 = 0;
  145. 			}
  146.  
  147. 			int[] temp = LossArr(Q);
  148. 			Q = temp;
  149. 			heapSort(Q, Q.length);
  150.  
  151. 			HuffmanNode y = new HuffmanNode();
  152.  
  153. 			if (Q[0] != root.freq && Q[0] != rootTemp1.freq && Q[0] != rootTemp2.freq && Q[0] != rootTemp3.freq
  154. 					|| Q[0] == x.freq) {
  155. 				y.freq = HeapExtractMax(Q);
  156. 			} else if (Q[0] == root.freq && mrtPoint == 1) {
  157. 				y = root;
  158. 				HeapExtractMax(Q);
  159. 				mrtPoint = 0;
  160. 			} else if (Q[0] == rootTemp1.freq && rtPoint1 == 1) {
  161. 				y = rootTemp1;
  162. 				HeapExtractMax(Q);
  163. 				rtPoint1 = 0;
  164. 			} else if (Q[0] == rootTemp2.freq && rtPoint2 == 1) {
  165. 				y = rootTemp2;
  166. 				HeapExtractMax(Q);
  167. 				rtPoint2 = 0;
  168. 			} else if (Q[0] == rootTemp3.freq && rtPoint3 == 1) {
  169. 				y = rootTemp3;
  170. 				HeapExtractMax(Q);
  171. 				rtPoint3 = 0;
  172. 			}
  173.  
  174. 			temp = LossArr(Q);
  175. 			Q = temp;
  176. 			heapSort(Q, Q.length);
  177.  
  178. 			HuffmanNode z = new HuffmanNode();
  179. 			z.left = x;
  180. 			z.right = y;
  181. 			z.freq = x.freq + y.freq;
  182. 			if (rtPoint1 == 0 && mrtPoint == 1) {
  183. 				rootTemp1 = root;
  184. 				rtPoint1 = 1;
  185. 			} else if (rtPoint1 == 1 && rtPoint2 == 0) {
  186. 				rootTemp2 = root;
  187. 				rtPoint2 = 1;
  188. 			} else {
  189. 				rootTemp3 = root;
  190. 				rtPoint3 = 1;
  191. 			}
  192. 			root = z;
  193. 			mrtPoint = 1;
  194.  
  195. 			temp = AddArr(Q);
  196. 			Q = temp;
  197. 			MaxHeapInsert(Q, z);
  198. 			heapSort(Q, Q.length);
  199. 		}
  200.  
  201. 		return root;
  202. 	}
  203.  
  204. 	public static void SaveCode(HuffmanNode root, String s) {
  205. 		if (root.left == null && root.right == null) {
  206. 			root.data = s;
  207. 			return;
  208. 		}
  209. 		SaveCode(root.left, s + "0");
  210. 		SaveCode(root.right, s + "1");
  211. 	}
  212.  
  213. 	public static void FindHuffman(HuffmanNode root, int find) {
  214. 		if (root.left == null && root.right == null) {
  215. 			if (root.freq == find) {
  216. 				System.out.println(root.data);
  217. 				return;
  218. 			}
  219.  
  220. 			return;
  221. 		}
  222. 		FindHuffman(root.left, find);
  223. 		FindHuffman(root.right, find);
  224.  
  225. 	}
  226.  
  227. 	public static void main(String[] args) {
  228.  
  229. 		Scanner sc = new Scanner(System.in);
  230. 		int size;
  231. 		size = sc.nextInt();
  232. 		if (size <= 0) {
  233. 			return;
  234. 		}
  235. 		int arr[] = new int[size];
  236. 		int[] temp = new int[size];
  237. 		for (int i = 0; i < arr.length; i++) {
  238. 			arr[i] = sc.nextInt();
  239. 			temp[i] = arr[i];
  240. 		}
  241.  
  242. 		HuffmanNode root = Huffman(temp);
  243. 		SaveCode(root, "");
  244. 		for (int i = 0; i < arr.length; i++) {
  245. 			FindHuffman(root, arr[i]);
  246. 		}
  247. 	}
  248. }
Success #stdin #stdout 0.23s 52952KB
comments (?)
stdin
copy 
10
90
45
49
6
30
3
57
87
66
52
stdout
copy 
00
111
https://ideone.com/Q6FrCM
language:
Java (HotSpot 12)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!