Left-hand heap left-hand heap code implementation

Left-hand heap left-hand heap code implementation

Left pile


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


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:


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:


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


Node data structure

type NodeData struct {
    data int

Node 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


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


type LeftHeap struct {
    root *Node


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)
    return Small

Adjustment method

func (l *LeftHeap) Modify() {
    if l.root.Left == nil {
        if l.root.Right == nil {
        } else {
            l.root.Left, l.root.Right = l.root.Right, l.root.Left
    } else if l.root.Right == nil {
    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)

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)
    return returnData, nil

Printing method

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