堆
堆结构非常重要
优先级列表
把一个数组理解成一个完全二叉树(脑补)
- 堆结构的 heapInsert 与 heapify
- 堆结构的增大和减少
- 如果只是建立堆的过程,时间复杂度为 O (N)
- 优先级队列结构,就是堆结构
二叉树
在不越界的情况下,第 i 个元素:
- 左节点:2 * i + 1
- 右节点:2 * i + 2
- 父节点:(i - 1) / 2(0 号元素的父节点还是 0,-1/2 = 0)
完全二叉树
- 满二叉树:任何一个非叶节点,一定有左节点和右节点
- 不是满二叉树:所有节点,
从左到右依次补齐
大根堆
任何一棵子树的最大值,都是这棵子树的头部
小根堆
任何一棵子树的最小值,都是这棵子树的头部
生成堆
headInsert
一个新节点加入堆中,同时这个节点向上调整的过程
- 新进来一个节点,它只可能和 H 个元素比较:H==>
完全二叉树的高度:O(logN)
- 建立大根堆的过程
- 时间复杂度:O (N)==> log1 + log2 + log3 …
heapify
堆中有一个值(X)发生变化了,怎么调整才能让这个堆仍然是大根堆
- 找到 X 的左节点和右节点,较大的值(M)和 X 比较
- 如果 X < M:X 和 M 交换
示例
有一个流,不断在吐出数(无序),随时找到流中的中位数
可行方案
- 方案一
- 用一个数组装这些数(O (1))
- 每次需要中位数的时候,对数组排序(O (NlogN))
- 取出中位数
- 方案二
- 使用两个数组(大根堆、小根堆),较小的 N/2 个都放在大根堆中,较大的 N/2 都放在小根堆中
- 当两个数组的长度大于 1 的时候,从多的数组中,减堆(
弹出大根堆/小根堆的堆顶
),放到少的数组中- 先把第一个和最后一个元素交换(最大值和最小值交换)
- 然后将 heap_size 减 1(从堆中去掉最大值)
- 然后经历一遍 heapify 的过程,继续保持大根堆、小根堆
- 大根堆和小根堆的堆顶,就是两个数组中的最大值和最小值
- 一直保持,较小的 N/2 个在大根堆中,较大的 N/2 个在小根堆中
- 这样就可以随时拿到中位数
代码实现
堆排序
时间复杂度 O (N*logN)
额外空间复杂度 O (1)
- 把数组通过 heap_insert 变成大根堆
- 把最后一个值和堆顶交换
- 把堆的大小减 1 ==> 最大值保持不变的放在了最后一个位置,已经不在堆中了
- 再从剩下的堆中,做 heapify 的调整(堆顶被交换成了最小值),又变成了大根堆
- 再把当前堆中的最后一个值,和堆顶交换
- … …

评论区