package main

type Node struct {
    Value int
}

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

/**
 [ 將節(jié)點(diǎn)插入到堆 ]
 */
func (h *Heap)InsertNode(node *Node)  {
    h.list = append(h.list, node)
    h.length++

    // 自下而上調(diào)整堆, 借助堆的特性
    // 自下向上調(diào)整能保證整個(gè)堆是上一層比下一層大
    deep := h.length/2-1
    for i:=deep; i>=0; i-- {
        leftIndex := i*2+1
        rightIndex := i*2+2

        maxIndex := i   // 假設(shè)當(dāng)前為最大
        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
        }
    }
}

/**
[ 打印堆里面的數(shù)據(jù) ]
 */
func (h *Heap) PrintHeap()  {

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

/*
[ 獲取最大的一個(gè)堆頂元素 ]
 */
func (h *Heap) GetTop() *Node {
    if h.length==0 {
        return nil
    }

    node := h.list[0]
    h.list = h.list[1:] // 將最后 一個(gè)元素提到 堆頂

    h.length --

    // 自上而下調(diào)整整個(gè)堆，借助堆的特性
    deep := h.length/2-1
    for i:=0; i<=deep; i++ {
        leftIndex := i*2+1
        rightIndex := i*2+2

        maxIndex := i   // 假設(shè)當(dāng)前為最大
        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 {
            // 位置沒(méi)動(dòng)說(shuō)明已經(jīng)調(diào)整到合適的位置了
            break
        }
    }

    return node
}

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

    // 將數(shù)據(jù)插入堆
    for _, value := range arrList {
        // 插入節(jié)點(diǎn)
        myHeap.InsertNode(&Node{value})
    }

    // 打印堆里面的所有數(shù)據(jù)
    myHeap.PrintHeap()

    // println(myHeap.length)

    // 取出堆里面的數(shù)據(jù)
    for true {
        currentNode := myHeap.GetTop()
        if currentNode == nil {
            break
        } else {
            println(currentNode.Value)
        }
    }

}