堆

堆是什么？

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

  完全二叉树是指每层节点全部填满，最后一层如果不是满的，则只缺少右边的若干节点。
  

• 所有节点都大于等于（最大堆）或者小于等于（最小堆）它的子节点

最小堆

最大堆

JS中的堆

• js中通常用数组表示堆
• 左侧子节点的位置为2*index + 1
• 右侧子节点的位置为2*index + 2
• 父节点的位置是 Math.floor((index - 1) / 2)

堆的应用

• 堆能快速高效的找出最大值，最小值
• 时间复杂度为O(1)
• 找出第K个最大（小）元素

第K个最大元素

• 构建一个最小堆，并将元素依次插入堆中
• 当堆的容量超过K，就删除堆顶
• 插入结束后，堆顶就是第K个最大元素