patternMinor
Is huffman coding tree a heap or a trie?
Viewed 0 times
huffmanheaptriecodingtree
Problem
I study Huffman Coding tree from "Data Structures and Algorithm Analysis" of Shaffer and it says that Huffman Coding tree is an opportunity to experience a search trie. However, the code implements it with a heap class.
As a result, I wonder if Huffman Coding tree is actually a heap or a trie? If it is a heap, is it a mimHeap or a maxHeap. I'm somehow confused because there are some online resources calling it a minHeap, as it should be a maxHeap.
Anyway, thank you very much in advance.
As a result, I wonder if Huffman Coding tree is actually a heap or a trie? If it is a heap, is it a mimHeap or a maxHeap. I'm somehow confused because there are some online resources calling it a minHeap, as it should be a maxHeap.
Anyway, thank you very much in advance.
Solution
A Huffman tree is a trie: its edges are labeled by $0,1$, and its paths spell out binary words.
Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two items with minimal probability, and merge them.
Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two items with minimal probability, and merge them.
Context
StackExchange Computer Science Q#96009, answer score: 5
Revisions (0)
No revisions yet.