左式堆
性质
零路径长
零路径长的定义为:
零路径长:从节点X到一个没有两个子节点的(有一个子节点或没有子节点)节点的最短距离
对于零路径长,有以下递归的计算方法:
- 每个节点的零路径长比子节点的最小零路径长大1
- NULL的节点的零路径长为-1,只有一个子节点或没有子节点的节点零路径长为0
左式堆
左式堆是特殊的优先堆,除了有序性(每个节点的数据小于其子节点)以外,还有具有与零路径长相关的性质:对于左式堆,要求任一节点的左子节点零路径长大于等于右子节点的零路径长
操作
合并操作
左式堆的基本操作是合并,合并的递归描述如下:
- 当输入的两个堆都是空的,输出空堆;当有一个堆是空的,则返回非空的堆
- 当两个堆非空时,比较两个根节点的大小,返回为:
- 堆根节点为原较小的根节点
- 左子树为原较小的跟节点的左子树
- 右子树为根节点较大的堆和跟节点较小堆右子树合并的结果
如下图所示:
对于最终结果,可能在根节点上出现不符合左式堆的性质的情况,出现这种情况时,交换左右子节点即可:
其他操作
有了核心操作合并,优先堆的其他操作可由合并实现:
- 插入:通过合并单个节点和现有堆实现
- 弹出:将根节点返回,并合并左右子堆
代码实现
节点数据结构体
1 2 3
| type NodeData struct { data int }
|
节点结构体
结构体
节点需要的特性有:
- Num:优先级标记,数值越低优先级越高
- Data:节点数据
- Depth:零路径长度
- Right和Left:左右子节点的指针
1 2 3 4 5 6 7
| type Node struct { Num int Data NodeData Left *Node Right *Node Depth int }
|
节点方法
构造方法
1 2 3
| func NewNode(Num int, Data NodeData) *Node { return &Node{Num, Data, nil, nil, 0} }
|
获取零路径长
1 2 3 4 5 6 7 8 9 10 11 12 13
| 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 } }
|
打印
1 2 3 4 5 6 7 8 9
| 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") } }
|
左式堆结构
结构体
1 2 3
| type LeftHeap struct { root *Node }
|
方法
合并方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| 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 }
|
调整方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 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 } }
|
插入方法
1 2 3 4 5
| func (l *LeftHeap) Push(InsertNum int, InsertData NodeData) { InsertNode := NewNode(InsertNum, InsertData) l.root = l.Merge(l.root, InsertNode) l.Modify() }
|
弹出方法
1 2 3 4 5 6 7 8 9
| 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 }
|
打印方法
1 2 3
| func (l *LeftHeap) Print() { l.root.Print("") }
|