堆结构

许多应用程序都需要处理有序的元素，但是不一定要求它们全部有序，或是不一定要一次就将它们完全排好序。例如，你要实现一个进程调度算法，每一个进程都有一个优先级(~~当有电话到来时，你的游戏很可能会被打断~~)，所以电话程序的优先级会高于游戏程序的优先级。

所以当前面临的挑战是：一个电脑上每个时刻都会有许多不同的进程，怎么按照优先级去调度它们呢？也就是说，在每次调度的时候，我们都希望花费很少的时间去找到最重要的进程(或者最不重要的进程)，堆结构就很好的解决这个问题。

完全二叉树

二叉树是一种常见的结构，对于一个结点来说，它通常可以有两个子节点(left, right)，看起来是这样的：

用代码来表示：

1
2
3
4
5


type Tree struct {
    Val int // 值域
    Left *Tree
    Right *Tree
}

不过这里我们不会使用这种形式，可以使用数组来进行父子结点之间关系。

完全二叉树是一个特殊的二叉树，下面是维基百科对完全二叉树的介绍

在一颗二叉树中，若除最后一层外的其余层都是满的，并且最后一层要么是满的，要么在右边缺少连续若干节点，则此二叉树为完全二叉树（Complete Binary Tree）。具有n个节点的完全二叉树的深度 $log_{2}n+1$ 。深度为k的完全二叉树，至少有 $2^{\begin{aligned}k-1\end{aligned}}$ 个节点，至多有 $2^{\begin{aligned}k\end{aligned}}-1$ 个节点。

通俗点来说，完全二叉树就是满二叉树从后向前去除子节点后剩下的二叉树。简单来说，堆按照根节点与子节点的大小关系可以分为大根堆和小根堆。大根堆的根节点比所有的子节点大，小根堆的根节点比子节点都小。所以按照这种规则，大根堆的根节点一定是数组里面的最大值，小根堆的根节点一定是数组里面的最小值。

堆的实现

首先，对于一个不是堆结构的数组来说，第一步要做的就是heapify堆化，堆化需要用到两个辅助函数，

就是 sink和swim。

从名字上来看，sink就是向下交换，swim就是向上交换，对于一个数组，我们可以从第一个非叶子结点开始堆化，对于这些非叶子结点，我们每次都进行堆化，这样初始化到数组的第一个元素的时候，整个数组就是堆结构了。

sink方法

首先是找到这个数组的第一个非叶子结点，对于一个数组arr来说，我们假定它的长度是n，那么它的第一个非叶子结点就是(n-1) / 2，这里从大根堆开始建堆.

首先，一个堆结构看起来可能是这样的：

1
2
3


type MaxHeap struct {
	item []int
}

它的sink方法是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func (this *MaxHeap) sink(k int) {
	n := len(this.item)
	// 孩子结点
	for 2*k+1 < n {
		child := 2*k + 1
		if child+1 < n && this.item[child] < this.item[child+1] {
			child = child + 1
		}
		// 没必要交换
		if this.item[k] >= this.item[child] {
			break
		}
		// 交换两个元素
		this.item[k], this.item[child] = this.item[child], this.item[k]
		k = child
	}
}

上面这段代码的意思是，给定一个下标，让这个下标的元素向下交换，从而满足堆结构。然后就可以开始进行堆化的操作了

heapify方法

1
2
3
4
5
6
7


func (this *MaxHeap) heapify() {
	// 从非叶子结点开始
	n := len(this.item)
	for i := (n - 1) / 2; i >= 0; i-- {
		this.sink(i)
	}
}

经过此次操作，我们就已经有了堆结构，item切片的第一个元素就是数组中的最大值。

swim方法

但是，到目前为止，我们还没有让这个堆实现动态数据的添加和实现，当新增一个数据的时候，我们就把它添加到切片的结尾末尾，此时，这个新增的结点很可能会破坏掉原来的堆结构，这个时候，我们应该给新添加进来的元素找到合适的位置，swim方法就可以很好的实现。

1
2
3
4
5
6
7


func (this *MaxHeap) swim(k int) {
	for k > 0 && this.item[(k-1)/2] < this.item[k] {
		// 父节点比自己小
		this.item[(k-1)/2], this.item[k] = this.item[k], this.item[(k-1)/2]
		k = (k - 1) / 2 // 注意这里啊
	}
}

添加与删除

添加一个元素时，需要动态的调整位置

1
2
3
4


func (this *MaxHeap) insert(val int) {
	this.item = append(this.item, val)
	this.swim(len(this.item) - 1)
}

删除一个元素的时候(一般是根节点)，这里有一个trick，根节点与最后一个结点进行交换，然后再把新的结点sink使得找到合适的位置，这样做是因为，数组不适合频繁的添加删除元素，这样做可以更加高效！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func (this *MaxHeap) delMax() int {
	ans := this.item[0]
	this.item[0], this.item[len(this.item)-1] = this.item[len(this.item)-1], this.item[0]
	this.item = this.item[:len(this.item)-1] // 删除
	this.sink(0)
	return ans
}
func (this *MaxHeap) getMax() int {
	return this.item[0]
}

到此，我们就成功的实现了一个大顶堆，小顶堆的实现与之很相似，这里直接贴出代码

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


type MinHeap struct {
	item []int
}

func (this *MinHeap) heapify(nums []int) {
	this.item = nums
	n := len(this.item)
	for i := (n - 1) / 2; i >= 0; i-- {
		this.sink(i)
	}
}

func (this *MinHeap) sink(k int) {
	n := len(this.item)
	for 2*k+1 < n {
		child := 2*k + 1
		if child+1 < n && this.item[child+1] < this.item[child] {
			child = child + 1
		}
		if this.item[k] <= this.item[child] {
			break
		}
		this.item[k], this.item[child] = this.item[child], this.item[k]
		k = child
	}
}

func (this *MinHeap) swim(k int) {
	for k > 0 && this.item[(k-1)/2] > this.item[k] {
		this.item[k], this.item[(k-1)/2] = this.item[(k-1)/2], this.item[k]
		k = (k - 1) / 2
	}
}
func (this *MinHeap) genLength() int {
	return len(this.item)
}

func (this *MinHeap) insert(val int) {
	this.item = append(this.item, val)
	this.swim(len(this.item) - 1)
}

拓展：堆排序

在我们刚才构建大顶堆的时候，注意到每次都可以以 $O(logK)$的时间复杂度调整并获取最大值，所以，对于n组数来说，我们就可以以$O(nlogK)$的复杂度来进行排序，其中$K$是树的高度

这里是完整代码，需要注意交换的范围每次都是在缩小的

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45


package main

import (
	"fmt"
)

// ConstructMaxHeap 将输入数组转换为最大堆。
func ConstructMaxHeap(nums []int) {
	n := len(nums)
	for i := n/2 - 1; i >= 0; i-- {
		sink(nums, i, n)
	}
}

// sink 是辅助函数，用于下沉元素以保持最大堆性质。
func sink(nums []int, k int, n int) {
	for 2*k+1 < n {
		child := 2*k + 1
		if child+1 < n && nums[child] < nums[child+1] {
			child = child + 1
		}
		if nums[k] >= nums[child] {
			break
		}
		nums[k], nums[child] = nums[child], nums[k]
		k = child
	}
}

// heapSort 使用堆排序算法对输入的切片进行排序。
func heapSort(nums []int) {
	ConstructMaxHeap(nums)
	n := len(nums)
	for i := n - 1; i > 0; i-- {
		nums[i], nums[0] = nums[0], nums[i] // 交换最大元素到正确位置
		sink(nums, 0, i)                    // 重新构建堆
	}
}

func main() {
	nums := []int{3, 2, 1, 5, 6, 4}
	fmt.Println("Original array:", nums)
	heapSort(nums)
	fmt.Println("Sorted array:", nums)
}