目录
一，堆的定义和介绍
堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
堆就是用数组实现的二叉树。堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值。
- 堆总是一棵完全二叉树。
堆是非线性数据结构，相当于一维数组，有两个直接后继。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的使用场景：
- 构建优先队列
- 支持堆排序
- 快速找出一个集合中的最小值（或者最大值）
下面我们主要分析一种最为经典的堆实现 二叉堆 Binary Heap，并且只实现 最大堆。
二叉堆对应的是一个二叉树，所谓的二叉树就是每一个节点最多只能有两个子节点。
二叉堆（最大堆）所对应的二叉树的特点：
- 任何一个节点的值总是不大于其父节点的值。
- 必须是完全二叉树。
所谓的完全二叉树就是，(1)除了最后一层节点之外，其他层所有的节点个数必须是最大值。对于一个二叉树来说，第一层最多有1个节点，第二层最多有2个节点，第三层最多有4个节点，以此列推。(2)在最后一层虽然它的节点个数可以不是最大值，但是所有的节点必须集中在左侧。
二，如何用数组存储二叉堆？
使用数组实现二叉堆，是一个非常经典的实现。‘
我们之所以可以使用数组来存储一个二叉堆，正是因为堆是一颗完全二叉树。我们可以尝试一下，给这个完全二叉树自上到下、自左到右的每一个节点标上一个序列号，如下图所示。最顶端的节点是1，下面一层2、3，再下面一层4、5、6、7，以此类推。相当于依照层序自上到下，然后在每一层自左到右，按照这个顺序标上序列号。
这样标上序列号之后，我们就可以发现，对于每一个节点来说，左子节点的序列号都是它的序列号的2倍，右子节点的序列号都是它的序列号的2倍加1。
还要注意一点，这里是将根节点的序列号声明成了1，如果我们把根节点的序列号声明成0的话，后面依次类推0、1、2、3、4、5、6。这时候也有类似的性质，这时候具体的左右子节点的计算规则会发生一些改变，但是依然有相应的规律，有兴趣的同学可以尝试自己找一下这个规律。
不过对于堆来说，一个经典的实现，就是根节点从1开始标记。这样一来我们就可以把所有的这些数据存在数组中，而相应的我们刚刚标记的这些序列号，就是数组中的索引。
所以对于上图中的二叉堆而言，就可以用如下的数组进行存储。
大家要注意，0索引这里是不使用的，
现在我们有了这样一个数组之后，就可以非常轻松的使用我们之前讲的公式，找到数组中每个元素，它所对应的左子节点元素和右子节点元素。同理我们也可以找到数组每个元素的父节点元素。
parent(i) = i / 2 //求i元素的父节点元素，这里采用的是计算机的除法，如果不能整除则向下取整。
left child(i) = 2 * i //求i元素的左子节点元素。
right child(i) = 2 * i + 1 //求i元素的右子节点元素。
二叉堆代码实现的整体框架如下：
public class MaxHeap<T> {
private T[] data;
private int count;
/**
* 构造函数，构造一个空堆，可容纳capacity个元素
* @param capacity
*/
public MaxHeap(int capacity){
data = (T[]) new Object[capacity];
}
/**
* 返回堆中的元素个数
* @return
*/
public int size(){
return count;
}
/**
* 返回一个布尔值，表示堆中是否为空
* @return
*/
public boolean isEmpty(){
return count == 0;
}
/**
* 测试 MaxHeap
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
System.out.println("maxHeap size: " + maxHeap.size());
}
}三、向最大堆中插入元素 Shift up
我们先来看一下动态演示：
现在有一个已经存在的堆，如下图。
如果有一个新的元素52，需要加入到这个最大堆。通过上面的分析知道，这个堆我们使用了一个数据来实现，在这个最大堆中添加一个新的元素，相当于在数组的末尾添加一个元素。此时52就添加到了索引为11的位置，这样相当于最大堆变成了如下样子。
但是大家要注意，这个样子的二叉树是不满足最大堆的定义，所以接下来我们要进行一些列的操作，来维护最大堆的定义。那具体应该怎么做呢？
其实这个过程非常简单，在我们加入新元素之前，整个二叉树就是一个最大堆，所以问题肯定出现在新加入的元素上。 我们需要做的是将新加入的元素，调整到合适的位置，使得整个二叉树依然保持最大堆的性质。那么我们怎么调整这个顺序呢？
把新加入的元素和它的父节点元素进行比较。如果父节点元素比新加入元素小，违背了最大堆的定义，所以把这两个元素交换一下位置。交换完成后二叉树变成如下样子。
此时新元素是根节点的子树部分，已经满足最大堆的定义。那么下一步这个新元素52可能还是和它的父节点元素不满足最大堆的定义。所以这时候新加入的元素52再和它的父节点元素42进行比较，是否父节点原始比这个新元素还要小。在这里父节点元素41比新元素52小，所以他们又要交换一下位置，现在我们的二叉树就变成了如下样子。
此时新元素是根节点的子树部分，依然保持了最大堆的性质。那么现在到了这种状态，新元素52到了新的位置，它还有可能和它的父节点元素违背最大堆的定义。所以还需要再次比较一下新元素和它父节点元素，52比62要小，此时就不需要交换这两个元素的位置了。
经过这一些列的操作，我们依旧维持了整个二叉树最大堆的定义。我们可以看到新元素52从最底层逐渐往上升的过程，就是我们要分析的Shift Up过程。通过这样的方式我们成功的向最大堆中添加了新的元素。下面我们来看一下具体的代码实现。
/**
* 在堆的有关操作中，需要比较堆中元素的大小，所以E extends Comparable
* @param <E>
*/
public class MaxHeap<E extends Comparable> {
protected E[] data;
protected int count;
protected int capacity;
/**
* 构造函数，构造一个空堆，可容纳capacity个元素
* @param capacity
*/
public MaxHeap(int capacity){
data = (E[]) new Comparable[capacity + 1];
count = 0;
this.capacity = capacity;
}
/**
* 返回堆中的元素个数
* @return
*/
public int size(){
return count;
}
/**
* 返回一个布尔值，表示堆中是否为空
* @return
*/
public boolean isEmpty(){
return count == 0;
}
/**
* 向最大堆中插入一个新的元素
* @param t
*/
public void insert(E e){
if(count < capacity){
data[count + 1] = e;
count++;
shiftUp(count);
}
}
/**
* 最大堆核心辅助函数，把新插入的元素，移动到合适的位置。
* @param k
*/
private void shiftUp(int k){
while(k > 1 && data[k / 2].compareTo(data[k]) < 0){
swap(k / 2, k);
k = k / 2;
}
}
private void swap(int i, int j){
E temp = data[i];
data[i] = data[j];
data[j] = data[i];
}
}
四、从最大堆中取出元素 Shift Down
首先我们来看一下Shift Down的操作流程。
假设如下二叉树是当前最大堆的状态。
如果我们想从堆中取出一个元素，这里我们要注意。从堆中取出一个元素，只能取出根节点的元素。对于最大堆来说，相当于取出了优先级最大（值最大）的那个元素。
那么现在我们整个堆中相当于少了一个元素，怎么填补这个元素呢？
答案非常简单，我们只需要把整个堆的最后一个元素，放到整个堆的第一个元素的位置。这时候整个堆依然是一个完全二叉树，
前面的代码实现中，有一个count的成员变量，来描述当前堆中有多少个元素。这时候count--。这个例子中索引为11的元素16可以不动，我们在之后的操作中都已count为界，所以索引为11的元素不会被访问到。
这样一来首先我们整个堆拿出了一个元素，并且依然保持这它是一个完全二叉树。但是我们可以看出来，这个完全二叉树此时不是一个最大堆，这是因为我们从最下面取出一个元素放到最上面，这时候根节点元素不是整个堆中的最大值，会比它的子节点小。所以下面我们要做的事情，就是调整这些元素的位置，使得它保持最大堆的性质。
这个调整的过程其实是将根节点的元素，一步一步的向下移动，最终找到它合适的位置。这也就是为什么这个操作加Shift Down。
接下来我们看一下整个操作的动态演示。
这里我们将元素16向下移动，但是它可以向左也可以向右，那么究竟向哪个方向呢？
先比较一下左子节点和右子节点的大小，然后把较大的子节点元素和该元素比较，如果较大的子节点元素更大，则交换两个元素的位置，反之就不交换位置，结束整个Shift Down操作。或者当该元素已经在最下面一层（没有子节点），也需要结束整个Shift Down操作。
在这个例子里左节点元素52比右节点元素30大，左节点元素52比元素16大，所以元素16跟左节点元素52换。因为这样换完之后，才能保证元素52比元素16和元素32都要大。
接下来我们继续下移，比较元素16的左右两个子节点元素28和41。右节点元素41大于左节点元素28，右节点元素41大于元素16。所以元素16和右子节点元素41交换位置。
这时候元素16继续和它的子节点元素比较，此时的元素16只有左子节点，所以只需要比较元素16和左子节点元素15。元素16大于左子节点元素15，所以不需要进行交换。到此为止我们的Shift Down操作就结束了。
此时我们的最大堆成功的退出了一个元素62，之后经过Shift Down的操作，继续维持了最大堆的性质。那么下一步如果我们还要往外推出元素的话，根元素52就会推出去。然后元素15就会被换上去，再经过一些列的Shift Down操作，维持最大堆的性质。
下面我们来看一下具体的代码实现。
/**
* 在堆的有关操作中，需要比较堆中元素的大小，所以E extends Comparable
* @param <E>
*/
public class MaxHeap<E extends Comparable> {
protected E[] data;
protected int count;
protected int capacity;
/**
* 构造函数，构造一个空堆，可容纳capacity个元素
* @param capacity
*/
public MaxHeap(int capacity){
data = (E[]) new Comparable[capacity + 1];
count = 0;
this.capacity = capacity;
}
/**
* 返回堆中的元素个数
* @return
*/
public int size(){
return count;
}
/**
* 返回一个布尔值，表示堆中是否为空
* @return
*/
public boolean isEmpty(){
return count == 0;
}
/**
* 向最大堆中插入一个新的元素
* @param t
*/
public void insert(E e){
if(count < capacity){
data[count + 1] = e;
count++;
shiftUp(count);
}
}
/**
* 最大堆核心辅助函数，把新插入的元素，移动到合适的位置。
* @param k
*/
private void shiftUp(int k){
while(k > 1 && data[k / 2].compareTo(data[k]) < 0){
swap(k / 2, k);
k = k / 2;
}
}
/**
* 取出最大堆中，最大的元素
* @return
*/
public E extractMax(){
if(count <= 0){
return null;
}
E e = data[1];
swap(1, count);
count --;
shiftDown(1);
return e;
}
/**
* 最大堆核心辅助函数，把根节点的元素，移动到合适的位置。
* @param k
*/
private void shiftDown(int k){
while(k * 2 <= count){ //判断节点k是否有子节点，只要有右节点就一定有子节点
int j = k * 2; //在此轮循环中，data[k]和data[j]交换位置
if(j + 1 <= count && data[j + 1].compareTo(data[j]) > 0){
//有右子节点，并且右子节点元素比左子节点元素更大。
j ++;
}
// data[j] 是 data[2*k]和data[2*k+1]中的最大值
if(data[k].compareTo(data[j]) >= 0){
//节点k已经比它的所有子节点更大,不需要交换位置了。
break;
}
swap(k, j);
k = j;
}
}
private void swap(int i, int j){
E temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
五、总结
堆是一种灵活动态的数据结构，它能够在不停的添加和取出元素之后，一直保持着根节点元素最大（或这小）。正式由于这个特性，堆非常适合用来实现优先队列，也可以用来实现排序（堆排序）。