左式堆

性质

零路径长

零路径长的定义为：

零路径长：从节点X到一个没有两个子节点的（有一个子节点或没有子节点）节点的最短距离

对于零路径长，有以下递归的计算方法：

• 每个节点的零路径长比子节点的最小零路径长大1
• NULL的节点的零路径长为-1，只有一个子节点或没有子节点的节点零路径长为0

左式堆

左式堆是特殊的优先堆，除了有序性（每个节点的数据小于其子节点）以外，还有具有与零路径长相关的性质：对于左式堆，要求任一节点的左子节点零路径长大于等于右子节点的零路径长

操作

合并操作

左式堆的基本操作是合并，合并的递归描述如下：

• 当输入的两个堆都是空的，输出空堆；当有一个堆是空的，则返回非空的堆
• 当两个堆非空时，比较两个根节点的大小，返回为：
  • 堆根节点为原较小的根节点
  • 左子树为原较小的跟节点的左子树
  • 右子树为根节点较大的堆和跟节点较小堆右子树合并的结果

如下图所示：

对于最终结果，可能在根节点上出现不符合左式堆的性质的情况，出现这种情况时，交换左右子节点即可：

其他操作

有了核心操作合并，优先堆的其他操作可由合并实现：

• 插入：通过合并单个节点和现有堆实现
• 弹出：将根节点返回，并合并左右子堆

代码实现

节点数据结构体

type NodeData struct {
	data int
}

节点结构体

结构体

节点需要的特性有：

• Num：优先级标记，数值越低优先级越高
• Data：节点数据
• Depth：零路径长度
• Right和Left：左右子节点的指针

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("")
}