TS数据结构与算法之堆有什么特点,和二叉树有什么关系
2022-03-10 本文已影响0人
子十一刻
堆栈模型
- JS代码执行时
- 值类型变量,存储在栈
- 引用类型变量,存储在堆
堆
- 完全二叉树
- 最大堆:父节点 >= 子节点
- 最小堆:父节点 <= 子节点
堆是一种特殊的完全二叉树。所有父结点都比子结点要小的完全二叉树我们称为最小堆。反之,如果所有父结点都比子结点要大,这样的完全二叉树称为最大堆。
逻辑结构 VS 物理结构
- 堆,逻辑结构是一棵二叉树
- 但它物理结构是一个数组
- 数组:适合连续存储 + 节省空间(堆栈模型)
完全二叉树中父亲和儿子之间有着神奇的规律,我们只需用一个一维数组就可以存储完全二叉树。
10
/ \
/ \
14 25
/ \ / \
33 81 82 99
上图是一个堆(从小到大),物理结构可以用数组表示为:
// 忽略0节点
const heap = [-1, 10, 14, 25, 33, 81, 82, 99];
数据之间的节点关系可以按二叉树的逻辑结构使用如下公式查找:
const parentIndex = Math.floor(i / 2);
const leftIndex = 2 * i;
const rightIndex = 2 * i + 1;
如:数据14对应数组下标为2,则父节点索引就是 2/2 = 1
,对应数据为10;左子节点索引是 2*2=4
就是33; 右子节点索引是 2*2+1=5
就是81。
堆 VS BST
- 查询比 BST 慢
- 增删比 BST 快,维持平衡更快
- 但整体的时间复杂度都在 O(logn) 级别,即树的高度
堆的使用场景
- 特别适合“堆栈模型”
- 堆的数据,都是在栈中引用的,不需要从Root遍历
- 堆恰巧是数组形式,根据栈的地址,可用O(1)找到目标
小结
- 堆栈模型,堆的场景
- 堆的特点,堆和BST
- 堆的逻辑结构和物理结构