堆(go实现)

package main

import "fmt"

//初始化堆
var heap = []int{0}

//插入数据
func insertHeap(originHeap []int, element int) []int {
    heap := append(originHeap, element)
    lastIndex := len(heap) - 1
    //堆化
    for lastIndex/2 > 0 && (heap[lastIndex] > heap[lastIndex/2]) {
        heap[lastIndex], heap[lastIndex/2] = heap[lastIndex/2], heap[lastIndex]
        lastIndex = lastIndex / 2
    }
    return heap
}

//删除堆顶元素
func removeMax(originHeap []int) []int {
    length := len(originHeap)
    if length <= 1 {
        return originHeap
    }
    last := originHeap[length-1]
    originHeap[1] = last
    heap := originHeap[:length-1]
    return heapify(heap, length-1, 1)
}

func heapify(heap []int, n int, i int) []int {
    for {
        maxPos := i
        //比左边的子元素大
        if i*2 <= n && heap[i] < heap[i*2] {
            maxPos = i * 2
        }
        //比右边的子元素大
        if i*2+1 <= n && heap[maxPos] < heap[i*2+1] {
            maxPos = i*2 + 1
        }
        //maxPos == i 说明比左右子元素都小,跳出循环
        if maxPos == i {
            break
        }
        //交换父元素和子元素的值
        heap[i], heap[maxPos] = heap[maxPos], heap[i]
        i = maxPos
    }
    return heap
}

func main() {
    ret := insertHeap(heap, 1)
    ret = insertHeap(ret, 3)
    ret = insertHeap(ret, 8)
    ret = insertHeap(ret, 100)
    ret = insertHeap(ret, 5)
    ret = insertHeap(ret, 7)

    ret = removeMax(ret)
    fmt.Println(ret)
}