左式堆

2018-03-27 本文已影响0人月见樽

左式堆

性质

零路径长

零路径长的定义为：

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

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

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

左式堆

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

操作

合并操作

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

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

如下图所示：

merge_op.png

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

merge_change.png

其他操作

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

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

代码实现

节点数据结构体

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

左式堆

左式堆

性质