Huffman Coding: Total Cost
Problem
Letters appear with the given frequencies. Huffman coding builds a tree: repeatedly take the two smallest weights, join them into one node whose weight is their sum, and put it back. The cost of each joining is that sum. Print the total of all the sums (this equals the total number of bits of the encoded text). With one letter the cost is 0.
Constraints
- 1 <= n <= 10^5
- 1 <= frequency <= 10^6
Examples
Input
6 5 9 12 13 16 45
Output
224
Solutions
Greedy rule: always join the two lightest nodes, so heavy nodes stay near the root and get short codes. A heap finds the two smallest in O(log n), so the whole build is O(n log n).
/*
* Problem : Total Huffman cost.
* Input : n and the frequencies.
* Output : The total cost.
* Approach: Min-heap
* Time : O(n log n)
* Space : O(n)
* Java : 8 or newer.
*/
import java.util.Scanner;
public class Main {
// This method solves the task. It receives the input and returns the answer.
static long solve(int[] a) {
// Step 1: A min-heap always gives the smallest weight first in O(log n).
java.util.PriorityQueue<Long> heap = new java.util.PriorityQueue<Long>();
for (int value : a) {
heap.add((long) value);
}
long cost = 0;
// Step 2: Join the two smallest weights and put the sum back. The joining costs that sum.
while (heap.size() > 1) {
long joined = heap.poll() + heap.poll();
cost += joined;
heap.add(joined);
}
return cost;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int size = scanner.nextInt();
int[] a = new int[size];
for (int i = 0; i < size; i++) {
a[i] = scanner.nextInt();
}
System.out.println(solve(a));
}
}
Hints (2)
- Why the two smallest?
- What does the heap give?