package main
import (
"container/heap"
"fmt"
)
// Node represents a tree node for Huffman encoding
// It holds frequency, character, and left/right children
type Node struct {
char rune
freq int
left *Node
right *Node
}
// PriorityQueue implements heap.Interface for Nodes
// It orders nodes by frequency ascending
type PriorityQueue []*Node
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].freq < pq[j].freq }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Node)) }
func (pq *PriorityQueue) Pop() interface{} {
n := len(*pq)
item := (*pq)[n-1]
*pq = (*pq)[:n-1]
return item
}
// buildHuffmanTree builds the Huffman tree from frequency map
func buildHuffmanTree(freqMap map[rune]int) *Node {
pq := &PriorityQueue{}
heap.Init(pq)
// Push all chars as leaf nodes
for ch, freq := range freqMap {
heap.Push(pq, &Node{char: ch, freq: freq})
}
// Merge nodes until one tree remains
for pq.Len() > 1 {
left := heap.Pop(pq).(*Node) // smallest freq node
right := heap.Pop(pq).(*Node) // second smallest
// Create new internal node with combined freq
merged := &Node{freq: left.freq + right.freq, left: left, right: right}
heap.Push(pq, merged) // push merged node back
}
return heap.Pop(pq).(*Node) // root node
}
// generateCodes traverses tree to assign binary codes
func generateCodes(node *Node, prefix string, codes map[rune]string) {
if node == nil {
return
}
// Leaf node: assign code
if node.left == nil && node.right == nil {
codes[node.char] = prefix
return
}
// Traverse left with '0'
generateCodes(node.left, prefix+"0", codes)
// Traverse right with '1'
generateCodes(node.right, prefix+"1", codes)
}
func main() {
freqMap := map[rune]int{'A': 5, 'B': 9, 'C': 12, 'D': 13, 'E': 16, 'F': 45}
root := buildHuffmanTree(freqMap)
codes := make(map[rune]string)
generateCodes(root, "", codes)
for ch, code := range codes {
fmt.Printf("%c: %s\n", ch, code)
}
}
left := heap.Pop(pq).(*Node) // smallest freq node
extract smallest frequency node to merge
right := heap.Pop(pq).(*Node) // second smallest
extract second smallest frequency node
merged := &Node{freq: left.freq + right.freq, left: left, right: right}
create new internal node combining two smallest nodes
heap.Push(pq, merged) // push merged node back
insert merged node back into priority queue
if node.left == nil && node.right == nil { codes[node.char] = prefix; return }
assign code to leaf node representing a character
generateCodes(node.left, prefix+"0", codes)
traverse left subtree adding '0' to code prefix
generateCodes(node.right, prefix+"1", codes)
traverse right subtree adding '1' to code prefix
F: 0
C: 100
D: 101
A: 1100
B: 1101
E: 111
