先来看一下堆的定义，一般满足下面两个要求的二叉树就是堆
1.堆必须是完全二叉树
2.堆中每个节点的值都大于或等于(或者小于或等于)其左右节点的值。
如果堆中每个节点的值都大于或等于子树每个节点的值，我们称这种堆为大顶堆，如果堆中每个节点的值都小于或等于子树中每个节点的值，我们称这种堆为小顶堆。再带大家回顾一下完全二叉树的定义：要求除最后一层，其他节点都要求是满的，而且最后一层的节点需要靠左排列。
图中，第1，2张图为大顶堆，第3张图为小顶堆，第四张图不是堆
堆的存储之前说过，完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省空间的，因为不需要存储左右子节点的指针，只需要数组的下包运算，就可以找到某个节点的左右子节点和父节点，因此，堆也适合用数组来存储。下面看看一张图。
从图中可以看到，存储方式和完全二叉树的存储一样， 都是从下标1开始存储的，因此更加方便计算，即假设当前节点的下标为i,那么他的左子树节点下标为2i，右子树节点下标为2i+1，父节点下标为i/2。
感兴趣大家可以去看看我这篇关于树的基本讲解。树和二叉树
下面再来看看堆一般都支持哪些操作，其中比较常用的是往堆中插入元素，获取堆顶元素，删除堆顶元素，然后就是按照节点指针（也就是数组下标）删除任意元素。
对于大顶堆，堆顶元素就是最大值，获取堆顶元素，就是返回数组中下标为1的元素。因此时间复杂度为O(1)。
往堆中插入元素下面以大顶堆举例，如果把元素插入到堆的末尾，此时就不一定会满足堆的定义，所以我们需要对堆进行调整，调整的过程称为堆化。
堆化分为两种，自上而下和自下而上。我们先看看自下而上的堆化方法，其实很简单，假设要堆化的节点为a，那么顺着a所在的路径进行比对，如果a大于父节点，就将a和父节点进行交换，然后继续比对，直到a节点的值小于或等于父节点的值为止。
下面看看代码实现。
public class Heap{
private int[] a; //从1开始存储数据
private int n; //可以存储的最大堆个数
private int count; //堆中已经存储的数据个数
public Heap(int capacity){
a = new int[capacity + 1];
n = capacity;
count = 0;
}
public void insert(int data){
if(count >= n) return;
++count;
a[count] = data; //先将元素添加到数组末尾
int i = count; //记录当前节点的下标
while(i/2 > 0 && a[i] > ai/2[]){
swap(a,i,i/2); //交换下标元素位置
i = i/2;
}
}
}
删除堆顶元素
对于大顶堆，堆顶节点就是最大节点。当堆顶节点删除之后，我们需要把第二大节点(也就是左子节点和右子节点中的其中一个)放到堆顶，然后迭代的删除第二大节点，依此类推在，直到叶子节点被删除。
不过这种方式不是很好，图中也进行了标注，会产生数组空洞，也就是说，在数组中，会有一个下标不存储元素了，那么此时的堆就不是完全二叉树了。
接下来看看这种方法，将最后一个元素放入堆顶，采用自上而下的方法进行元素的交换，也就是说，将堆顶的元素与他的子节点进行对比，将不满足大小关系的节点进行位置互换，直到父子节点的满足大小关系为止。这种方式就避免了数组空洞。
现在看看代码
public void removeMax(){
if(count == 0) return;
a[1] = a[count];
--count;
heapify(a,count,1);
}
private void heapify(int[] a,int n,int i){
while(true){
int maxPos = i;
if(2*i < n && a[i] < a[2*i]) maxPos = 2*i; //左子树查询
if(2*i+1 < n && a[i] < a[2*i+1]) maxPos = 2*i+1; //右子树查询
if(maxPos == i) break; //相等直接break
swap(a,i,maxPos); //交换
i = maxPs; //重新定位下标
}
}
删除任意元素
之前说到一个特殊的删除情况，删除顶堆元素。现在来看看非顶堆元素的删除。这一般包含两类删除操作，按值删除节点和按节点指针(数组下标)删除节点。按值删除节点指的是删除值等于给定值的节点，所以在删除前，我们需要先找到这个节点，按节点指针指的是给定一个节点指针，不需要查找，直接删除它。因为堆是用数组来存储的，所以按节点指针删除节点实际上就是删除给定数组下标的元素。仍然可以用上面说的删除堆顶元素的位置，将最后一个元素替换到要删除的位置，然后进行堆化操作。
不过不同的是，我们需要根据替换元素与删除元素的大小关系进行确定用哪种堆化方式，如果替换元素大于删除元素，就进行自下而上的堆化；如果替换元素小于删除元素，就进行自上而下的堆化
堆的性能分析现在来看看上面堆上面四个操作的时间复杂度。
获取堆顶元素的时间复杂度是O(1)，插入元素，删除堆顶元素，按照节点指针删除任意元素这三个操作的核心逻辑是堆化。一个包含n个节点的完全二叉树，树的高度约为logN。堆化的过程顺着节点的路径进行比较，所以堆化的时间复杂度和树的高度成正比，为O(logn)。因此，这三个操作的时间复杂度为O(logn)。
