零路径长的定义为:
零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离
对于零路径长,有以下递归的计算方法:
左式堆是特殊的优先堆,除了有序性(每个节点的数据小于其子节点)以外,还有具有与零路径长相关的性质:对于左式堆,要求任一节点的左子节点零路径长大于等于右子节点的零路径长
左式堆的基本操作是合并,合并的递归描述如下:
如下图所示:
merge_op.png
对于最终结果,可能在根节点上出现不符合左式堆的性质的情况,出现这种情况时,交换左右子节点即可:
merge_change.png
有了核心操作合并,优先堆的其他操作可由合并实现:
type NodeData struct {
data int
}
节点需要的特性有:
type Node struct {
Num int
Data NodeData
Left *Node
Right *Node
Depth int
}
func NewNode(Num int, Data NodeData) *Node {
return &Node{Num, Data, nil, nil, 0}
}
func (n *Node) GetDepth() int {
if n.Left == nil && n.Right == nil {
if n.Left.Depth > n.Right.Depth {
n.Depth = n.Right.Depth + 1
return n.Depth
}
n.Depth = n.Left.Depth + 1
return n.Depth
} else {
n.Depth = 0
return 0
}
}
func (n *Node) Print(indent string) {
fmt.Println(indent, n.Num, n.Data)
if n.Left != nil {
n.Left.Print(indent + "\t")
}
if n.Right != nil {
n.Right.Print(indent + "\t")
}
}
type LeftHeap struct {
root *Node
}
func (l *LeftHeap) Merge(Node1 *Node, Node2 *Node) *Node {
if Node1 == nil {
return Node2
} else if Node2 == nil {
return Node1
}
Big, Small := Node1, Node2
if Node1.Num < Node2.Num {
Big, Small = Node2, Node1
}
if Small.Right == nil {
Small.Right = Big
} else {
Small.Right = l.Merge(Small.Right, Big)
}
Small.GetDepth()
return Small
}
func (l *LeftHeap) Modify() {
if l.root.Left == nil {
if l.root.Right == nil {
return
} else {
l.root.Left, l.root.Right = l.root.Right, l.root.Left
return
}
} else if l.root.Right == nil {
return
}
if l.root.Left.Depth < l.root.Right.Depth {
l.root.Left, l.root.Right = l.root.Right, l.root.Left
}
}
func (l *LeftHeap) Push(InsertNum int, InsertData NodeData) {
InsertNode := NewNode(InsertNum, InsertData)
l.root = l.Merge(l.root, InsertNode)
l.Modify()
}
func (l *LeftHeap) DeleteMin() (NodeData, error) {
if l.root == nil {
return NodeData{}, errors.New("empty heap")
}
returnData := l.root.Data
l.root = l.Merge(l.root.Left, l.root.Right)
l.Modify()
return returnData, nil
}
func (l *LeftHeap) Print() {
l.root.Print("")
}