堆

堆是一种特殊的完全二叉树

完全二叉树：二叉树如果不是满二叉树，那么缺失的一定是右节点

特点

• JS 中使用数组来模拟堆
• 左侧子节点的位置为 2 * index + 1
• 优测子节点的位置为 2 * index + 2
• 父节点位置为 (index - 1) / 2

应用场景

• 元素中的找出最大值、最小值
• 找出第 K 个最大(小)元素

大根堆

所有节点都大于或等于子节点

小根堆

所有节点都小于或等于子节点