堆是每个双亲节点都大于（小于）子节点的特殊完全二叉树。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质

• 堆中某个节点的值总是不大于或不小于其父节点的值；
• 堆总是一棵完全二叉树。

堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储.

堆的操作和实现

堆化

在插入或删除操作后需要进行调整，让其重新满足堆的特性，这个调整的过程叫做堆化（heapify）。

上浮：当前元素不断向上和父节点比较大小

• 大顶堆：当前元素比父节点大，交换，让大的节点上去
• 小顶堆：当前元素比父节点小，交换，让小的节点上去

下沉：当前元素不断向下和两个孩子节点比较大小

• 大顶堆：当前元素与子节点中较大的比，比子节点小交换，让小的节点下去
• 小顶堆：当前元素与子节点中较小的比，比子节点大交换，让大的节点下去

插入

从下往上的堆化，在堆的尾部插入，满足完全二叉树条件，再进行堆化。

删除

把最后一个元素移到根节点的位置，满足完全二叉树的条件，再进行堆化

堆的应用

优先队列

堆是实现优先级队列最直接、最高效的方法。一般队列出队顺序只取决于入队顺序，而优先级队列的出队顺序总是按照元素自身的优先级。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素

堆排序

实现堆排序可分解为两个步骤，建堆和排序