简单链表实现

  • 一种是使用一个简单链表在表头以 O(1) 时间插入, 在查找最大/最小结点时遍历链表, 时间为 O(n)
  • 第二种是始终让链表保持有序, 这样插入时需要遍历链表, 插入时间为 O(n), 但删除只需要删除表头 O(1)

二叉树实现

使用一棵完全二叉树实现优先队列称为堆(heap), 根结点为最大值的称为最大堆, 为最小值的为最小堆

通常我们使用链表来实现二叉树, 但在这里我们使用一个数组来实现二叉树, 数组的大小为堆的大小 + 1, 第 0 个位置不放结点, 树按层序遍历依次填到数组中, 这样最大/最小的值始终在下标为 1 的位置, 使用 下标 / 2 可以轻易的拿到其对应的父结点. 当下标为 1 时, 1 / 2 = 0 这时我们可以判断已经遍历到根结点

使用数组表示二叉树
使用数组表示二叉树的例子

  • 对于任意结点 i, 其父结点为 i / 2, 其左子结点为 2i, 右结点为 2i + 1
  • 对于任意一棵子树, 都有根结点是最大或最小

插入新结点

  • 判断树是否为空, 为空则放到根结点即可. 不为空把新结点插入到最末尾的位置
  • 跟新结点的父结点对比大小, 即 i / 2 的位置, 大于(最大堆)/小于(最小堆)则交换位置
  • 循环上一步直到根结点

往上交换位置的操作称为上滤(percolate up)

堆上滤
堆上滤操作示例

删除根结点

这里举例删除最小堆的情况, 最大堆情况也是一样的, 只是下滤比较时找最大的值即可

  • 判断树是否为空, 不为空则取出根结点

  • 将树最后一个结点移到根结点

  • 比较左右子树和根结点的大小, 选取最小的结点

    1. 如果左右有比根结点小的则和根结点交换

    2. 如果左右结点都比根大, 则流程结束

  • 在交换结点值后, 以这个结点为新的子树, 重复上面的比较过程直到完结

堆下滤
堆下滤操作

堆的创建

  1. 一种方法是循环的将数据插入到堆中, 那么总时间为 O(NlogN)
  2. 根据上面删除最大结点时可知, 如果某棵树的左子树和右子树都已经是一个堆了, 那么从树的根结点开始下滤, 则最终树也是变成一个堆. 那么对于有 n 个结点完全二叉树, 我们是从最右边的倒数上一层为子树, 然后再依次把每一层作为一棵子树来排序来满足堆的有序性, 这样循环到根结点, 那么最终便可以得到一个堆, 其时间复杂度为 O(N). 倒数第二层的最右子树其父结点可以由树的大小 / 2 得到为 i, 然后循环条件为 i--, 便是向左移动得到左边子树

下面举例创建一个最大堆的过程

创建一个最大堆的过程
创建一个最大堆的过程, 时间复杂度 O(logN)

最大堆代码实现

https://github.com/ivicel/zju-data-structure

树的基本结构代码

需要注意的是, 底层数组的从下标 1 开始保存数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 树结点
type Node struct {
	val int
}

// 大小比较
// 大于返回 1, 小于返回 -1, 等于返回 0
func (node *Node) Equal(other *Node) int {
	if node.val == other.val {
		return 0
	} else if node.val > other.val {
		return 1
	} else {
		return -1
	}
}

// 最大堆
type PriorityQueue struct {
	size    int    // 当前队列大小
	maxSize int    // 队列的最大容量
	val     []Node // 存储数据结点
}

插入结点

这里插入新的结点需要注意几点:

  1. 判断堆是否已满, 因为我们一般在底层使用数组保存数据
  2. 将新结点保存到数组的最后一位(size++)和下标 0
  3. 循环判断比较结点大小, 使用下标 0 结点和父结点进行比较, 大于则交换
  4. 上面的循环判断, 因为我们从下标 1 开始保存数据, 循环最多到根结点, 根结点在交换后不会比新结点大, 所以我们可以以新结点和父结点大小比较作为循环结束条件
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
// 插入新的结点
func (q *PriorityQueue) Push(val int) error {
	if q.size == q.maxSize {
		return errors.New("队列已满, 插入失败")
	}

	// 将结点放到最后位置
	newNode := Node{val}
	q.size++
	q.val[q.size] = newNode
	// 上滤
	pos := q.size
	for q.val[0] = newNode; newNode.Equal(&q.val[pos/2]) > 0; pos = pos / 2 {
		// 大于时交换值
		q.val[pos], q.val[pos/2] = q.val[pos/2], q.val[pos]
	}

	return nil
}

删除结点

删除结点也就是获取堆中的最大值(根结点), 然后再使堆重新变成一个优先队列

  1. 判断堆不为空, 不能删除空堆
  2. 把最后一个结点保存到下标 0 和 1 的位置, 我们使用下标 0 的来作为比较基准, 如果大于这个值的结点, 则只要往上换到父结点, 循环完成后得到的位置便是下标 0 的结点的最终位置, 因为此时要么没有孩子结点, 要么孩子结点大
  3. 循环比较的条件为某个父结点存在左子结点, 因为若左孩子都不存在, 那也就是一个叶子结点, 比较完成
  4. 如果存在左孩子, 那么则判断是否存在右孩子并和左孩子比较大小, 保存更大结点的下标
  5. 和父结点比较, 不大于父结点的话则循环完成
  6. 大于父结点则, 这个结点换到父结点, 重复第 3 步
  7. 最后要记录把下标 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
42
// 删除最大值
func (q *PriorityQueue) Remove() (Node, error) {
	if q.size == 0 {
		return Node{}, errors.New("不能删除空树")
	}

	// 保存根结点
	node := q.val[1]
	q.val[1] = q.val[q.size]
	q.size--

	q.percolateDown(1)

	return node, nil
}

// 下滤
func (q *PriorityQueue) percolateDown(root int) {
	q.val[0] = q.val[root]
	// 如果左孩子都不存在的话, 那就是叶子结点了, 因为这是一棵完全二叉树
	for root*2 <= q.size {
		pos, rightPos := root*2, root*2+1

		// 如果右子树存在并且右 > 左, 那 pos = 右, 否则 pos = 左
		if rightPos <= q.size && q.val[pos].Equal(&q.val[rightPos]) < 0 {
			pos = rightPos
		}

		// 比较孩子结点和父结点的大小, pos 可能是左也可能是右
		// 不大于则说明最大结点就是父结点
		if q.val[pos].Equal(&q.val[0]) > 0 {
            // 结点换到上一层
			q.val[root] = q.val[pos]
            // 转到下一层
			root = pos
		} else {
			// 最大值就是父结点时, 不用交换
			break
		}
	}
	q.val[root] = q.val[0]
}

使用上面的方法在下滤时容易出错的地方

  1. 传入的参数为初始的父结点位置, 忘记要该结点保存到下标 0
  2. 循环完成后忘记将下标 0 的结点再保存回查找到的位置, 也就是上面 q.val[root] = q.val[0]

使用上面的方法好处就是减少了交换的次数, 这样如果数组里的保存的数据非指针则性能更好些, 如果我们比较时就直接交换父结点和子结点的值, 此时父结点就是相当下标 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
// 下滤
func (q *PriorityQueue) percolateDown(root int) {
	// 如果左孩子都不存在的话, 那就是叶子结点了, 因为这是一棵完全二叉树
	for root*2 <= q.size {
		pos, rightPos := root*2, root*2+1

		// 如果右子树存在并且右 > 左, 那 pos = 右, 否则 pos = 左
		if rightPos <= q.size && q.val[pos].Equal(&q.val[rightPos]) < 0 {
			pos = rightPos
		}

		// 比较孩子结点和父结点的大小, pos 可能是左也可能是右
		// 不大于则说明最大结点就是父结点
		if q.val[pos].Equal(&q.val[root]) > 0 {
            // 交换结点
			q.val[root], q.val[pos] = q.val[pos], q.val[root]
            // 转到下一层
			root = pos
		} else {
			// 最大值就是父结点时, 不用交换
			break
		}
	}
}

时间复杂度 O(N) 创建堆的方法

O(N) 复杂度创建堆需要注意的是

  1. 得到最右边的子树的根结点为 tree.size /2
  2. 注意我们的 i-- 后得到某个子树的根结点, 需要调整这棵子树而不只是这个结点的左右孩子
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 根据数组生成一个新堆
func CreateQueue(arr []int) *PriorityQueue {
	// 按默认顺序创建一个新堆
	size := len(arr)
	maxSize := size * 2
	queue := &PriorityQueue{
		size:    size,
		maxSize: maxSize,
		val:     make([]Node, 1, maxSize),
	}

	nodes := make([]Node, size)
	for i, val := range arr {
		nodes[i] = Node{val}
	}
	queue.val = append(queue.val, nodes...)

	// 调整排序
	for i := size / 2; i > 0; i-- {
		queue.percolateDown(i)
	}

	return queue
}

代码地址: https://github.com/ivicel/zju-data-structure

Reference