TS数据结构与算法之堆有什么特点，和二叉树有什么关系

堆栈模型

• 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
• 堆的逻辑结构和物理结构