基于最小堆实现Huffman树（golang实现）
package heap
import "fmt"
//最小堆
type MinHeap struct {
Size int
Heap []*HuffmanTree //存放元素的数组
}
//哈夫曼树结构体
type HuffmanTree struct {
Left,Right *HuffmanTree
Weight int
}
//初始化最小堆
func NewMinHeap() *MinHeap {
h := &MinHeap{
Size: 0,
Heap: make([]*HuffmanTree,1),
}
h.Heap[0] = &HuffmanTree{}
return h
}
//最小堆的插入
func (minH *MinHeap) Insert(item *HuffmanTree) {
minH.Size++
i := minH.Size
minH.Heap = append(minH.Heap,&HuffmanTree{})
for minH.Heap[i/2].Weight>item.Weight {
minH.Heap[i] = minH.Heap[i/2]
i = i/2
}
minH.Heap[i] = item
}
//判断堆是否为空
func (minH *MinHeap) IsEmpty() bool {
return minH.Size==0
}
//最小堆的删除
func (minH *MinHeap) Delete() *HuffmanTree {
if minH.IsEmpty() {
return nil
}
var parent,child int
minItem := minH.Heap[1]
for parent = 1;parent*2<=minH.Size ;parent = child {
child = parent*2
if child != minH.Size && minH.Heap[child].Weight>minH.Heap[child+1].Weight {
child++
}
if minH.Heap[minH.Size].Weight<= minH.Heap[child].Weight {
break
} else {
minH.Heap[parent] = minH.Heap[child]
}
}
minH.Heap[parent] = minH.Heap[minH.Size]
minH.Size--
return minItem
}
//获取哈夫曼树
func (minH *MinHeap) GetHuffmanTree() *HuffmanTree {
for minH.Size>1 {
T := &HuffmanTree{}
T.Left = minH.Delete()
T.Right = minH.Delete()
T.Weight = T.Left.Weight+T.Right.Weight
minH.Insert(T)
}
return minH.Delete()
}
//先序遍历
func (hum *HuffmanTree) Traversal() {
if hum != nil {
fmt.Printf("%v\t",hum.Weight)
hum.Left.Traversal()
hum.Right.Traversal()
}
}
//中序遍历
func (hum *HuffmanTree) Traversal2() {
if hum != nil {
hum.Left.Traversal2()
fmt.Printf("%v\t",hum.Weight)
hum.Right.Traversal2()
}
}