什么是堆

堆是一种完全二叉树，且每个节点都大于等于（小于等于）其子节点的值。

大顶堆：每个节点都大于等于其子节点的堆
小顶堆：每个节点都小于等于其子节点的堆

如何存储堆

根据堆的定义，其为完全二叉树，则可以使用数组来存储堆。
使用数组存储堆相比于链式存储有以下优点：

  1. 访问任意位置元素时间复杂度为O(1)
  2. 访问每个节点的子(父)节点耗时与链式存储几乎无差异。假如某节点在数组的索引是x,则其父节点索引为 (x+1)/2-1，左右子节点分别为(x+1)*2-1与(x+1)*2
  3. 数组在内存中按顺序存储，对CPU更友好，缓存命中高

堆的操作

以下涉及堆均默认为小顶堆，大顶堆与其类似，只是判断大小逻辑需调整

向堆中增加元素

把新的元素放至堆的末位，为使其仍然符合堆的定义，则需要对其进行调整。
这个过程叫做堆化(heapify)：

将新元素与其父元素做比较，如果比父节点值小，则与父节点交换位置，以此类推，通过不断的与新父节点作比较与交换，最终到达合适的位置，正好满足堆的定义。

Go语言实现自下而上的堆化过程代码如下：

1
2
3
4
5
6
7
8
9
10
11
// 自下而上的堆化
func heapify(arr []int, x int) {

    for x > 0 {
        parent := (x+1)/2 - 1
        if arr[x] < arr[parent] {
            arr[x], arr[parent] = arr[parent], arr[x]
        }
        x = parent
    }
}

删除堆顶元素

从堆的定义中可知，对顶元素即为堆中的最小值，当删除该值时，需将剩下元素的最小值放到堆顶，而且其最小值必定是堆顶元素的子节点;
将最小值移上去后，还需填充该位置以满足其完全二叉树的性质，再去从该位置的子节点中找最小元素… 最终将堆中最后一行中的某个元素移到上一层，但此时可能不满足满二叉树的性质，又要将最后一个位置的值移到该位置（移了之后又可能不满足堆的性质，又要堆化），此过程还是比较麻烦的。

如果考虑将堆顶元素删除后，直接将最后一个元素移到此位置，则只需对其自上而下堆化即可:
0. 将堆顶元素删除，并将堆中最后一个元素放到堆顶

  1. 从堆顶开始，将堆顶视为当前元素
  2. 比较当前元素与子节点元素的大小，取出最小的，如果最小的为本身，则直接结束；
  3. 否则，交换最小的子节点元素与当前元素值，
  4. 将最小子节点作为当前节点，重复2，直到当前节点为叶子节点

Go语言实现自上而下的堆化过程代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func heapify2(arr []int, n int) {

	arrLen := len(arr)
	for {
		right := (n + 1) * 2
		left := right - 1
		if left >= arrLen {
			break
		}
		mini := n
		// 判断左右子节点，找出最小节点
		if right < arrLen && arr[right] < arr[mini] {
			mini = right
		}
		if arr[left] < arr[mini] {
			mini = left
		}
		// 如果最小节点是当前节点，则退出
		if mini == n {
			break
		}
		// 将最小位置的值与当前位置交换
		arr[mini], arr[n] = arr[n], arr[mini]
		n = mini
	}
}

如何基于堆实现排序

大致过程分为两步：建堆和排序

建堆

建堆有两种方法：

  1. 堆中元素从1个不断增加，增加到指定长度，这个过程使用了自下向上的堆化过程。时间复杂度为O(nlg(n))
  2. 从数组中间开始遍历到数组0索引位置，对每个位置实行自上而下的堆化过程。时间复杂度O(n)

第二种建堆方法Go实现：

1
2
3
4
5
6
7
func InitHeap(arr []int) {

	arrLen := len(arr)
	for i := arrLen/2 + 1; i >= 0; i-- {
		heapify(arr, i) // 调前边的实现
	}
}

排序

不断从堆中取出最小值，取得数据的序列即为从小到大的排序结果

1
2
3
4
5
6
7
8
9
10
// 删除堆顶元素
func RemoveTop(arr []int) int {

	ret := arr[0]
	len := len(arr)
	arr[0] = arr[len-1]
	arr = arr[0 : len-1]
	heapify(arr, 0) // 调前边的实现
	return ret
}