1 heap是什么

堆（Heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。在队列中，调度程序反复提取队列中第一个作业并运行，因为实际情况中某些时间较短的任务将等待很长时间才能结束，或者某些不短小，但具有重要性的作业，同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

2 heap可以用来做什么

优先级队列、求 Top K 和求中位数

3 Go标准库中的实现

Go 标准库中 container/heap 原文地址为： https://golang.org/pkg/container/heap/

4 动手写一个大顶堆

 

package src

//"container/heap"）

type BigHeap struct {
	HeapList []int
	MaxNum   int
	Count    int
}

func (h *BigHeap) Insert(data int) {
	if h.Count >= h.MaxNum {
		return
	}
	h.Count += 1
	h.HeapList[h.Count] = data
	i := h.Count
	for i/2 > 0 && h.HeapList[i] > h.HeapList[i/2] {
		h.swap(i, i/2)
		i = i / 2
	}
}

func (h *BigHeap) swap(a, b int) {
	h.HeapList[a], h.HeapList[b] = h.HeapList[b], h.HeapList[a]

}

func (h *BigHeap) RemoveMax() {
	if h.Count == 0 {
		return
	}
	h.HeapList[1] = h.HeapList[h.Count]
	h.HeapList[h.Count] = 0
	h.Count -= 1
	h.heapify(h.Count, 1)

}

func (h *BigHeap) heapify(n, i int) { // 自上往下堆化
	for {
		maxPos := i
		if i*2 <= n && h.HeapList[i] < h.HeapList[i*2] {
			maxPos = i * 2
		}
		if i*2+1 <= n && h.HeapList[maxPos] < h.HeapList[i*2+1] {
			maxPos = i*2 + 1
		}
		if maxPos == i {
			break
		}
		h.swap(i, maxPos)
		i = maxPos
	}

}