What structural property is always satisfied by an optimal Huffman Tree constructed for character frequencies?
An optimal Huffman tree is a full/strictly binary tree where every non-leaf node has exactly 2 children.
In Huffman Coding, if a text contains n distinct characters, how many total nodes (leaf + internal) will the resulting Huffman tree contain?
A strictly binary tree with n leaf nodes contains n - 1 internal nodes, giving a total of n + (n - 1) = 2n - 1 nodes.
What is the time complexity of building a Huffman Tree for n distinct characters using a Min-Heap priority queue?
Building a Min-Heap of n elements takes O(n). Then n-1 merge operations, each involving 2 Extract-Min and 1 Insert on the heap of size O(n), take (n-1) * O(log n) = O(n log n) total time.
In Huffman Coding, what is the length of the binary code for a character with frequency $f_{i}$ relative to total character count N?
By Shannon-Information theory, optimal prefix code lengths are inversely proportional to probability $p_{i} = f_{i} / N$, giving depth $d_{i} = ceil(-log_2(p_{i}))$.
In Job Sequencing with Deadlines, each job i takes 1 unit of time and has profit $p_{i}$ and deadline $d_{i}$. Which greedy policy maximizes total profit?
Greedy choice processes highest profit jobs first, placing each in its latest possible slot before its deadline to keep earlier slots open for other jobs.