Left-hand heap left-hand heap code implementation

Left-hand heap left-hand heap code implementation

Left pile

nature

Zero path length

The definition of zero path length is:

Zero path length: the shortest distance from node X to a node without two children (one child or no child)

For zero path length, there are the following recursive calculation methods:

  • The zero path length of each node is longer than the minimum zero path of the child node by 1
  • The zero path length of a NULL node is -1, and the zero path length of a node with only one child node or no child node is 0

Left pile

The left-type heap is a special priority heap. In addition to ordering (the data of each node is less than its child nodes), it also has properties related to zero path length : for the left-type heap, the left child node of any node is required The zero path length is greater than or equal to the zero path length of the right child node

operating

Merge operation

The basic operation of the left heap is merge, and the recursive description of merge is as follows:

  • When the two input heaps are empty, the output is empty; when one heap is empty, the non-empty heap is returned
  • When the two heaps are not empty, compare the sizes of the two root nodes and return as:
    • The heap root node is the original smaller root node
    • The left subtree is the left subtree of the original smaller root node
    • The right subtree is the result of merging the heap with the larger root node and the right subtree with the smaller node

As shown below:

merge_op.png

For the final result, there may be a situation that does not conform to the nature of the left-type heap on the root node. When this happens, just swap the left and right child nodes:

merge_change.png

Other operations

With core operation merging, other operations of the priority heap can be implemented by merging:

  • Insertion: achieved by merging a single node and existing heap
  • Pop: Return the root node and merge the left and right sub-heaps

Code

Node data structure

type NodeData struct {
    data int
}

Node structure

Structure

The features required by the node are:

  • Num: priority tag, the lower the value, the higher the priority
  • Data: node data
  • Depth: Zero path length
  • Right and Left: pointers to left and right child nodes
type Node struct {
    Num int
    Data NodeData
    Left *Node
    Right *Node
    Depth int
}

Node method

Construction method

func NewNode(Num int, Data NodeData) *Node {
    return &Node{Num, Data, nil, nil, 0}
}

Get zero path length

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
    }
}

print

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

Left stack structure

Structure

type LeftHeap struct {
    root *Node
}

method

Merge method

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
}

Adjustment method

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
    }
}

Insert method

func (l *LeftHeap) Push(InsertNum int, InsertData NodeData) {
    InsertNode := NewNode(InsertNum, InsertData)
    l.root = l.Merge(l.root, InsertNode)
    l.Modify()
}

Pop-up method

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
}

Printing method

func (l *LeftHeap) Print() {
    l.root.Print("")
}
Reference: https://cloud.tencent.com/developer/article/1110944 Left-hand heap left-hand heap code implementation-Cloud + Community-Tencent Cloud