Golang实现的大顶堆demo

       大顶堆的节点的值大于或等于左右子节点的值。 

       堆通过slice实现并且从索引1处开始存储实际数据则具有如下性质：

其左孩子节点索引值为父亲节点索引值的2倍。  

       以下代码使用slice实现了大顶堆，使用arr[0]存储堆的大小。其核心代码是堆的上浮和下沉操作。其他插入和弹出操作均依赖于上浮和下沉操作。

       上浮操作主要是将末尾的元素通过迭代的方式依次和其父祖节点比较、交换，直到到达合适位置。具体代码如下：

func (h *Heap) pushUp() {
	tmp := h.Size()
	for h.arr[tmp] > h.arr[tmp/2] && tmp > 1 {
		h.arr[tmp], h.arr[tmp/2] = h.arr[tmp/2], h.arr[tmp]
		tmp = tmp / 2
	}
}

       下沉操作主要是将堆顶的元素通过递归的方式依次和其最大的子孙节点比较，交换，直到到达合适位置。具体代码如下：

func (h *Heap) pushDown(root int) {
	t := root
	left := 2 * root
	right := 2*root + 1
	if right <= h.Size() && h.arr[right] >= h.arr[t] {
		t = right
	}
	if left <= h.Size() && h.arr[left] >= h.arr[t] {
		t = left
	}
	if t != root {
		h.arr[root], h.arr[t] = h.arr[t], h.arr[root]
		h.pushDown(t)
	}
}

package main

import "fmt"


type Heap struct {
	arr []int
}

func (h *Heap) Size() int {
	return h.arr[0]
}
func (h *Heap) pushDown(root int) {
	t := root
	left := 2 * root
	right := 2*root + 1
	if right <= h.Size() && h.arr[right] >= h.arr[t] {
		t = right
	}
	if left <= h.Size() && h.arr[left] >= h.arr[t] {
		t = left
	}
	if t != root {
		h.arr[root], h.arr[t] = h.arr[t], h.arr[root]
		h.pushDown(t)
	}
}

//大顶堆
func (h *Heap) pushUp() {
	tmp := h.Size()
	for h.arr[tmp] > h.arr[tmp/2] && tmp > 1 {
		h.arr[tmp], h.arr[tmp/2] = h.arr[tmp/2], h.arr[tmp]
		tmp = tmp / 2
	}
}
func (h *Heap) Insert(v int) {
//在末尾添加元素
	h.arr = append(h.arr, v)
	h.updateSize(1)
	h.pushUp()
}
func (h *Heap) PopTop() int {
	if h.Size() < 1 {
		return -1
	}
//保存堆顶元素
	res := h.arr[1]
//将末尾元素放置到堆顶位置
	h.arr[1] = h.arr[h.Size()]
	h.updateSize(-1)
//pushDown函数的参数为根节点index
	h.pushDown(1)
	return res
}
func (h *Heap) updateSize(v int) {
	h.arr[0] += v
}

func NewHeap() *Heap {
	return &Heap{make([]int, 1)}
}

func main() {
	heap := NewHeap()
	for i := 0; i < 10; i++ {
		heap.Insert(i)
	}
	fmt.Println(heap.Size())

	for i := 1; i <= 10; i++ {
		fmt.Println(heap.PopTop())
	}
}