堆的定义

1. 堆必须是一个完全二叉树

   1. 允许二叉树的最后一行不为满
   2. 最后一行的顺序必须是从左往右
   3. 最后一行元素之间不可以有间隔

2. 堆依照堆序性可以分为大根堆和小根堆：

   

堆的存储

这里以大根堆为例，从上到下，从左往右进行编号，按照编号保存到对应的数组中：

若节点下标为 i，左子节点下标为 2i + 1，右子下标为 2i + 2

堆的基本操作

这两个操作不同的翻译或者教材有不同的叫法

下滤

以大根堆为例，将破坏堆序性的根节点元素跟它的最大的子节点比较，如果小于它的最大子节点，则与之交换，持续比较交换，直到这个元素大于它的两个子节点（或者到底部）为止。

这个操作一般用于构建堆，下滤操作的复杂度为 O(logN)

上滤

以大根堆为例，将破坏堆序性的叶子节点元素，让它和它的父节点比较，若大于父元素则交换，直到小于它的父元素或者成为根节点为止。

这个一般用于插入元素到堆中，上滤操作的复杂度为 O(logN)

建堆的基本方法

自顶向下法

对应的操作为上滤，将元素一个一个插入到堆内，复杂度为 O(NlogN)

自下而上法

对应的操作为下滤，对倒数第二排的子树开始进行下滤操作，直到整体根节点下滤完毕，复杂度为 O(N)