358. Huffman Coding - Total Encoded Length

Given n characters with their frequencies of occurrence in a message, build an optimal Huffman tree using the standard algorithm - repeatedly merge the two nodes with the smallest weight into a new node whose weight is their sum - and find the total number of bits required to encode the entire message with the resulting prefix codes (the sum, over every character, of its frequency times its code length in the tree). This total is the same regardless of how ties are broken during merging, so it's well-defined even though the exact codes aren't unique.

Input: The first line contains an integer n, the number of characters. The second line contains n space-separated integers, each character's frequency. Output: Print a single integer - the total number of bits required to encode the message with the optimal Huffman codes.

1 <= n <= 10^4, 1 <= frequency <= 10^6

This same min-heap 'always merge two smallest' technique appears in 'Minimum Cost of Ropes' and 'Minimum Cost to Connect N Ropes' too - Huffman coding is really just this same greedy merge idea applied specifically to build an optimal prefix-code tree.

Build an optimal Huffman tree from character frequencies and find the total number of bits needed to encode a message. Brute force: Try every possible way of assigning binary codes to characters directly, checking which assignment minimizes total encoded length - this is combinatorially enormous, when the Huffman merge procedure is provably optimal and vastly simpler. Optimised: Always merging the two SMALLEST-weight nodes first (via a min-heap) provably minimizes the total weighted code length - this greedy merge strategy is the entire foundation of Huffman coding, a cornerstone of lossless data compression.

Sort the frequencies once up front, then use two FIFO queues - one holding the original sorted leaf frequencies, one holding newly created merged-node weights (which are always produced in non-decreasing order) - and at each merge step just compare the fronts of the two queues to pick the two smallest in O(1), pushing their sum onto the merged-node queue. Because the merged weights come out already sorted relative to each other, no heap operations are needed during the n-1 merges at all, only queue pushes and pops; the only O(log n)-per-item cost is the single initial sort, so the total work spent merging drops from O(n log n) to O(n), leaving the sort as the sole log-factor cost. Time: O(n log n) Space: O(n)

Push every character's frequency into a binary min-heap, then repeatedly pop the two smallest weights, merge them into a new node whose weight is their sum, and push that sum back onto the heap, continuing until only one node remains; the total bits needed is accumulated as the sum of each merge's combined weight (since each merge adds that pair's contribution to every character's eventual code length). Using a heap instead of a linear scan brings each 'find the two smallest' step down to logarithmic time, which is the standard textbook implementation of Huffman coding. Time: O(n log n) Space: O(n)

Keep the current set of node weights in a plain unsorted array; at each of the n-1 merge steps, scan the whole array twice to find the two smallest weights, merge them into a new combined node, remove the two originals, and insert the new one back into the array. This directly follows Huffman's definition of the algorithm and is easy to verify as correct, but finding the two minimums by linear scanning every remaining step makes the whole construction quadratic in the number of characters. Time: O(n^2) Space: O(n)

1. Put every character's frequency into a min-heap. 2. Repeatedly pop the two SMALLEST weights, merge them into a new node whose weight is their sum, and push that sum back onto the heap - add this sum directly to a running total cost. 3. Keep merging until only one node remains; the running total of every merge's cost IS the final answer.

Time: O(n log n) - n-1 merges, each involving O(log n) heap operations. Space: O(n), for the heap holding all nodes.

n = 1 (a single character still needs 1 bit per occurrence), multiple characters sharing the same frequency, and n at its maximum of 10^4 with frequencies up to 10^6 to confirm the heap-based merging runs efficiently.

Be ready to explain that the total cost being 'the same regardless of tie-breaking' (as this problem notes) is because the SUM of all merge costs only depends on which weights get combined at which merge depths, not on the arbitrary order ties are broken in - a subtle but important correctness detail.