今天我们就来看看堆这种数据结构。
源码已经上传到github
https://github.com/HobbyBear/codelearning/tree/master/heap
原理
在详细介绍堆之前，先来看一种场景，很多时候我们并不需要对所有元素进行排序，而只需要取其中前topN的元素，这样的情况如果按性能较好的排序算法，比如归并或者快排需要n*log( n)的时间复杂度，n为数据总量，排好序后取出前N条数据，而如果用堆这种数据结构则可以在n*log(N)的时间复杂度内找到这N条数据，N的数据量远远小于数据总量n。
接着我们来看看堆的定义和性质，堆是一种树状结构，且分为最小堆和最大堆，最大堆的性质有父节点大于左右子节点，最小堆的性质则是父节点小于左右子节点。如下图所示:
并且堆是一颗完全二叉树，完全二叉树的定义如下:
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
因为结点都集中在左侧，所以我们可以从上到下，从左到右对堆中节点进行标号，如下图所示:
从0开始对堆中节点进行标号后，可以得到以下规律:
父节点标号 = (子节点标号-1)/2
左节点标号 = 父节点标号 *2 + 1
右节点标号 = 父节点标号 *2 + 2
有了标号和父子节点的标号间的关系，我们可以用一个数组来保存堆这种数据结构，下面以构建一个最大堆为例，介绍两种构建堆的方式。
HeapInsert
heapInsert的方式是从零开始，逐个往堆中插入数组中的元素，并不断调整新的节点，让新节点的父节点满足最大堆父节点大于其子节点的性质，这个调整的过程被称作ShiftUp。当数组中元素全部插入完成时，就构建了一个最大堆。代码如下:
func HeapInsert(arr []int) *Heap {
h := &Heap{arr: make([]int, 0, len(arr))}
for _, num := range arr {
h.Insert(num)
}
return h
}
Heapify
heapify的方式是假设数组已经是一个完全二叉树了，然后找到树中的最后一个非叶子节点，然后通过比较它与其子节点的大小关系，让其满足最大堆的父节点大于其子节点的性质，这样的操作被称作ShifDown，对每个非叶子节点都执行ShifDown操作，直至根节点，这样就达到了将一个普通数组变成一个堆的目的。
如果堆的长度是n，那么最后一个非叶子节点是 n/2 -1 ，所以可以写出如下逻辑,
func Heapify(arr []int) *Heap {
h := &Heap{arr: arr}
lastNotLeaf := len(arr)/ 2 -1
for i:= lastNotLeaf;i >= 0; i-- {
h.ShiftDown(i)
}
return h
}
取出根节点
取出根节点的逻辑比较容易，将根节点结果保存，之后让它与堆中最后一个节点交换位置，然后从索引0开始进行ShiftDown操作，就又能让整个数组变成一个堆了。
func (h *Heap) Pop() int {
num := h.arr[0]
swap(h.arr, 0, len(h.arr)-1)
h.arr = h.arr[:len(h.arr)-1]
h.ShiftDown(0)
return num
}
ShiftUp,ShiftDown实现
下面我将shiftUp和shiftDown的源码展示出来，它们都是一个递归操作，因为在每次shiftUp或者shiftDown成功后，其父节点或者子节点还要继续执行shifUp或shiftDown操作。
// 从标号为index的节点开始做shifUp操作
func (h *Heap) ShiftUp(index int) {
if index == 0 {
return
}
parent := (index - 1) / 2
if h.arr[parent] < h.arr[index] {
swap(h.arr, parent, index)
h.ShiftUp(parent)
}
}
// 从标号为index的节点开始做shifDown操作
func (h *Heap) ShiftDown(index int) {
left := index*2 + 1
right := index*2 + 2
if left < len(h.arr) && right < len(h.arr) {
if h.arr[left] >= h.arr[right] && h.arr[left] > h.arr[index] {
swap(h.arr, left, index)
h.ShiftDown(left)
}
if h.arr[right] > h.arr[left] && h.arr[right] > h.arr[index] {
swap(h.arr, right, index)
h.ShiftDown(right)
}
}
if left >= len(h.arr) {
return
}
if right >= len(h.arr) {
if h.arr[left] > h.arr[index] {
swap(h.arr, left, index)
h.ShiftDown(left)
}
}
}