一、堆是完全二叉树的结构

1.只允许最后一行不满

2.最后一行必须从左往右排，中间不能有间隔

二、堆序性

1.小根堆，父节点都要更小

2.大根堆，父节点都要更大

三、堆的存储

因为是完全二叉树，所以可以根据层序遍历，来得到一个数组，此时，父节点为 i 时，左右子节点一定为 2i+1/2

四、堆有两个基本操作

  1. 上滤，通常用于插入新元素到根中时，向上调整位置时
  2. 下滤（因为必须要满足堆序性的话，所以对不满足的要操作），把根节点向下调整的操作叫下滤

五、自顶向下建堆法

  1. 插入堆
  2. 上滤

六、自下而上建堆法

对每个父节点进行下滤（从最下面的父节点开始）– 复杂度 O(N)

七、应用

  1. 优先队列：弹出最小元素 – 可以用来实现堆排序，用大根堆排序完，弹出的是正序，小根堆反序
  2. 插入：就是上滤