Huffman coding: Difference between revisions
→{{header|Go}}: remove dependence on deprecated vector package
(→{{header|Go}}: remove dependence on deprecated vector package) |
|||
Line 1,278:
{{trans|Java}}
<lang go>package main
import (
"fmt"
"container/heap"
)
Line 1,286:
type HuffmanTree interface {
Freq() int
Less(y interface{}) bool
}
type HuffmanLeaf struct {
freq int
value int
}
type HuffmanNode struct {
freq int
left, right HuffmanTree
}
Line 1,315:
}
type treeHeap []interface{}
func (th treeHeap) Len() int { return len(th) }
func (th treeHeap) Less(i, j int) bool {
return th[i].(HuffmanTree).Less(th[j])
}
func (th *treeHeap) Push(ele interface{}) { *th = append(*th, ele) }
func (th *treeHeap) Pop() (popped interface{}) {
popped = (*th)[len(*th)-1]
*th = (*th)[:len(*th)-1]
return
}
func (th treeHeap) Swap(i, j int) { th[i], th[j] = th[j], th[i] }
func buildTree(charFreqs map[int]int) HuffmanTree {
var trees treeHeap
for c, f := range charFreqs {
trees
}
heap.Init(&trees)
for trees.Len() > 1 {
// two trees with least frequency
a := heap.Pop(&trees).(HuffmanTree)
b := heap.Pop(&trees).(HuffmanTree)
// put into new node and re-insert into queue
heap.Push(&trees, &HuffmanNode{a.Freq() + b.Freq(), a, b})
}
return heap.Pop(&trees).(HuffmanTree)
}
func printCodes(tree HuffmanTree, prefix
switch i := tree.(type) {
case *HuffmanLeaf:
// print out character, frequency, and code for this leaf (which is just the prefix)
fmt.Printf("%c\t%d\t%s\n", i.value, i.freq, string(
case *HuffmanNode:
// traverse left
prefix
printCodes(i.left, prefix)
prefix
// traverse right
prefix
printCodes(i.right, prefix)
prefix
}
}
Line 1,365 ⟶ 1,378:
// print out results
fmt.Println("SYMBOL\tWEIGHT\tHUFFMAN CODE")
printCodes(tree,
}</lang>
| |||