go 实现堆的相关操作

package main

type Node struct {
    Value int
}

type Heap struct {
    list   []*Node
    length int
}

/**
 [ 将节点插入到堆 ]
 */
func (h *Heap)InsertNode(node *Node)  {
    h.list = append(h.list, node)
    h.length++

    // 自下而上调整堆, 借助堆的特性
    // 自下向上调整能保证整个堆是上一层比下一层大
    deep := h.length/2-1
    for i:=deep; i>=0; i-- {
        leftIndex := i*2+1
        rightIndex := i*2+2

        maxIndex := i   // 假设当前为最大
        if leftIndex < h.length && h.list[leftIndex].Value > h.list[i].Value {
            maxIndex = leftIndex
        }

        if rightIndex < h.length && h.list[rightIndex].Value > h.list[i].Value {
            maxIndex = rightIndex
        }

        if maxIndex != i {
            // 交换位置
            h.list[maxIndex], h.list[i] = h.list[i], h.list[maxIndex]
        } else {
            break
        }
    }
}

/**
[ 打印堆里面的数据 ]
 */
func (h *Heap) PrintHeap()  {

    println()
    for _,v := range h.list {
        print(v.Value)
        print(" ")
    }
    println()
}

/*
[ 获取最大的一个堆顶元素 ]
 */
func (h *Heap) GetTop() *Node {
    if h.length==0 {
        return nil
    }

    node := h.list[0]
    h.list = h.list[1:] // 将最后 一个元素提到 堆顶

    h.length --

    // 自上而下调整整个堆，借助堆的特性
    deep := h.length/2-1
    for i:=0; i<=deep; i++ {
        leftIndex := i*2+1
        rightIndex := i*2+2

        maxIndex := i   // 假设当前为最大
        if leftIndex < h.length && h.list[leftIndex].Value > h.list[i].Value {
            maxIndex = leftIndex
        }

        if rightIndex < h.length && h.list[rightIndex].Value > h.list[i].Value {
            maxIndex = rightIndex
        }

        if maxIndex != i {
            // 交换位置
            h.list[maxIndex], h.list[i] = h.list[i], h.list[maxIndex]
        } else {
            // 位置没动说明已经调整到合适的位置了
            break
        }
    }

    return node
}

func main()  {
    // 初始化堆
    arrList := []int{1, 2, 11, 3, 7, 8, 4, 5}
    myHeap := &Heap{}

    // 将数据插入堆
    for _, value := range arrList {
        // 插入节点
        myHeap.InsertNode(&Node{value})
    }

    // 打印堆里面的所有数据
    myHeap.PrintHeap()

    // println(myHeap.length)

    // 取出堆里面的数据
    for true {
        currentNode := myHeap.GetTop()
        if currentNode == nil {
            break
        } else {
            println(currentNode.Value)
        }
    }

}