Great question—this is a super common point of confusion when you’re first wrapping your head around Huffman coding! Let’s break this down clearly:

1. The Standard, Efficient Implementation: Min-Heaps (Priority Queues) #

At its core, Huffman’s algorithm requires repeatedly doing two things:

• Extracting the two nodes with the smallest weights from your collection
• Merging them into a new node, then adding that node back into the collection

A min-heap (priority queue) is the ideal data structure for this because it’s optimized for exactly these operations:

• Extracting the minimum element takes O(log n) time
• Inserting a new element also takes O(log n) time
  This gives the overall algorithm an efficient O(n log n) time complexity, which is critical for handling large datasets (like real-world file compression scenarios).

2. The Simplified, Teaching-Focused Implementation: Ordered Lists #

The code you saw using an ordered list is a deliberate simplification for educational purposes. Here’s how it works:

• Instead of a heap, the code maintains a sorted list of nodes
• To get the two smallest elements, it just takes the first two items in the list
• After merging, it inserts the new node back into the correct position to keep the list sorted

While this works perfectly well for small example datasets, it’s much less efficient: each insertion or search for the minimum takes O(n) time, leading to an overall O(n²) time complexity. It’s easier to understand at a glance, though, because it avoids the more complex logic of heap operations (like "bubbling up" or "sinking down" elements).

3. Why the Discrepancy Between the Article’s Description and Code #

The article references min-heaps because that’s the industry-standard, production-ready approach for Huffman coding. The ordered list example is just a way to demonstrate the core logic of the algorithm without getting bogged down in the details of implementing a heap. It’s a common teaching trick—prioritizing clarity over efficiency so learners can grasp the fundamentals first.

Your observation is totally correct by the way! The discrepancy is just between the optimal practical implementation and a simplified educational example.

内容的提问来源于stack exchange，提问作者user7190448