堆

堆

• 完全二叉树
• 最大堆：父节点 >= 子节点
• 最小堆：父节点 <= 子节点
• 堆，逻辑结构是一个二叉树，但它物理结构是一个数组，数组适合连续存储 + 节省空间

堆的查找原理

堆 vs BST

• 查询比BST慢
• 增删比BST快，维持平衡快
• 但是整体的时间复杂度都是O(logn)级别，即树的高度

堆的使用场景

• 特别适合 “堆栈模型”
• 堆的数据，都是在栈中引用的，不需要从root遍历
• 堆恰巧是数组形式，根据栈的地址，可用O(1)找到目标