What is the complexity of Huffman Coding?

What is the complexity of Huffman Coding?

Approach: Analyze building the priority queue and the tree.

O(n log n). Creating a priority queue of n frequencies takes O(n), and performing n-1 merges (each involving O(log n) heap operations) takes O(n log n).

Follow-up: What is the complexity if frequencies are already sorted?

Key concepts: O(n log n), priority queue.