通常情況下我們把堆看成是一棵完全二叉樹罚随。堆一般分為兩種玉工，一種是最大堆，一種是最小堆淘菩。最大堆要求根節(jié)點的值即大于左子樹的值遵班，又大于右子樹的值。也就是說最大堆根節(jié)點的值是堆中最大的潮改。最小堆根節(jié)點的值是堆中最小的狭郑，前面我們講堆排序的時候介紹過堆，實際上他就是數(shù)組結構汇在，但因為數(shù)組中間有關聯(lián)翰萨，所以我們可以把它當做一棵完全二叉樹來看，下面我們再來看一下堆的數(shù)據(jù)結構是什么樣的糕殉。
結點中的數(shù)字是數(shù)組元素的下標亩鬼，不是數(shù)組元素的值。所以如果我們知道父節(jié)點的下標我們就可以知道他的兩個子節(jié)點（如果有子節(jié)點）阿蝶，如果知道子節(jié)點的下標也一定能找到父節(jié)點的下標雳锋，他們的關系是：
父節(jié)點的下標=（子節(jié)點下標-1）>>1；
左子節(jié)點下標=父節(jié)點下標*2+1羡洁；
右子節(jié)點下標=父節(jié)點下標*2+2玷过；
堆的創(chuàng)建：
堆有兩種，一種是最大堆焚廊，一種是最小堆冶匹。顧名思義，最大堆就是堆頂?shù)脑厥亲畲蟮呐匚粒钚《丫褪嵌秧數(shù)脑厥亲钚〉慕腊Ｔ矶疾畈欢啵覀冎环治鲆粋€就行了袒餐，我們就以數(shù)組【10飞蛹，4谤狡，8，3卧檐，5墓懂，1】為例來畫個圖分析一下最小堆是怎么創(chuàng)建的。
這就是堆的創(chuàng)建霉囚，把元素加入到堆中的時候捕仔，都要和父節(jié)點進行比對，在最小堆中盈罐，如果比父節(jié)點小榜跌，就要和父節(jié)點交換，交換之后還要繼續(xù)和再和新的父節(jié)點對比……盅粪。同理在最大堆中钓葫，如果比父節(jié)點大，就要和父節(jié)點交換票顾。
我們看到上面堆創(chuàng)建之后數(shù)組的元素順序變?yōu)椤?础浮，4，3奠骄，10豆同，5，8】
堆的刪除
堆的添加會往上調整戚揭，堆的刪除不僅會往下調整而且還有可能往上調整诱告。堆中元素的刪除我們可以從堆頂刪除撵枢，也可以從中間某個位置刪除民晒，如果從堆頂刪除的話我們只需要往下調整即可，因為堆頂沒有父節(jié)點锄禽，不需要往上調整潜必。如果從中間刪除的話，我們先要往下調整沃但，如果往下調整沒有成功（比如在最小堆中磁滚，他比兩個子節(jié)點都小）宵晚，我們還要進行往上的調整垂攘。調整的原理就是把數(shù)組最后一個元素放到要刪除的元素位置上，然后在刪除元素的位置上進行上下調整淤刃，原理其實都差不多晒他，我們來看一下最小堆頂部元素刪除之后的調整。
上面是我們把堆頂元素1刪除之后堆的調整逸贾，如果我們再把堆頂元素3刪除之后陨仅，只需要用數(shù)組的最后一個元素5替換3津滞，然后再往下調整即可……
代碼
堆的添加和刪除我們都分析過了，如果把前面的分析都搞懂的話灼伤，那么堆的代碼就很容易寫了触徐，我們來看下
public class MyHeap<E> {
private Object[] data;//數(shù)據(jù)存放區(qū)
private int size;//堆的大小
private Comparator<? super E> comparator;//比較器
public MyHeap(int initialCapacity) {
this(initialCapacity, null);
}
public MyHeap(int initialCapacity, Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException("堆的大小必須大于0");
this.data = new Object[initialCapacity];
this.comparator = comparator;
}
/**
* @param e 向堆中添加元素
* @return
*/
public boolean add(E e) {
if (e == null)//不能為空
throw new NullPointerException();
if (size >= data.length)//如果堆的空間不夠了就擴容，這里是擴大2倍
data = Arrays.copyOf(data, data.length << 1);
if (size == 0)//如果堆是空的狐赡，直接添加就可以了撞鹉，不需要調整，因為就一個沒發(fā)調整
data[0] = e;
else//如果堆不是空的颖侄，就要往上調整孔祸。
siftUp(e);
size++;//添加完之后size要加1
return true;
}
public int getSize() {
return size;
}
//刪除堆頂元素
public E remove() {
if (size == 0)
return null;
size--;
E result = (E) data[0];//獲取堆頂?shù)脑? E x = (E) data[size];//取出數(shù)組的最后一個元素
data[size] = null;//然后把最后一個元素的位置置空
if (size != 0)
siftDown(x);//這里實際上是把數(shù)組的最后一個元素取出放到棧頂，然后再往下調整发皿。
return result;
}
//訪問堆頂元素崔慧，不刪除
public E peek() {
return (size == 0) ? null : (E) data[0];
}
/**
* 返回數(shù)組的值
*
* @param a
* @param <T>
* @return
*/
public <T> T[] toArray(T[] a) {
if (a.length < size)
return (T[]) Arrays.copyOf(data, size, a.getClass());
System.arraycopy(data, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
/**
* 往上調整，往上調整只需要和父節(jié)點比較即可穴墅，如果比父節(jié)點大就不需要在調整
*
* @param e
*/
private void siftUp(E e) {
int s = size;
while (s > 0) {
int parent = (s - 1) >>> 1;//根據(jù)子節(jié)點的位置可以找到父節(jié)點的位置
Object pData = data[parent];
//和父節(jié)點比較惶室，如果比父節(jié)點大就退出循環(huán)不再調整
if (comparator != null) {
if (comparator.compare(e, (E) pData) >= 0)
break;
} else {
if (((Comparable<? super E>) e).compareTo((E) pData) >= 0)
break;
}
//如果比父節(jié)點小，就和父節(jié)點交換玄货，然后再繼續(xù)往上調整
data[s] = pData;
s = parent;
}
//通過上面的往上調整皇钞，找到合適的位置，再把e放進去
data[s] = e;
}
/**
* 往下調整松捉，往下調整需要和他的兩個子節(jié)點（如果有兩個子節(jié)點）都要比較夹界，哪個最小就和哪
* 個交換，如果比兩個子節(jié)點都小就不用再交換
*
* @param e
*/
private void siftDown(E e) {
int half = size >>> 1;
int index = 0;
while (index < half) {
int min = (index << 1) + 1;//根據(jù)父節(jié)點的位置可以找到左子節(jié)點的位置
Object minChild = data[min];
int right = min + 1;//根據(jù)左子節(jié)點找到右子節(jié)點的位置
if (right < size) {//如果有右子節(jié)點就執(zhí)行這里的代碼
//如果有右子節(jié)點隘世，肯定會有左子節(jié)點可柿。那么就需要左右兩個子節(jié)點比較，把小的賦值給minChild
if (comparator != null) {
if (comparator.compare((E) minChild, (E) data[right]) > 0)
minChild = data[min = right];
} else {
if (((Comparable<? super E>) minChild).compareTo((E) data[right]) > 0)
minChild = data[min = right];
}
}
//用節(jié)點e和他的最小的子節(jié)點比較丙者，如果小于他最小的子節(jié)點就退出循環(huán)复斥，不再往下調整了，
if (comparator != null) {
if (comparator.compare(e, (E) minChild) <= 0)
break;
} else {
if (((Comparable<? super E>) e).compareTo((E) minChild) <= 0)
break;
}
//如果e比它的最小的子節(jié)點小械媒，就用最小的子節(jié)點和e交換位置目锭，然后再繼續(xù)往下調整。
data[index] = minChild;
index = min;
}
data[index] = e;
}
}
這里的刪除和添加操作的都是堆頂?shù)脑胤桌蹋蕴砑拥臅r候會調用siftUp進行往上調整痢虹，刪除的時候會調用siftDown進行往下調整。我把注釋都寫在代碼中了主儡，這里就不再詳細介紹奖唯。
堆排序
通過上面的分析，我們知道最大堆就是堆頂元素始終保持的是最大值缀辩，最小堆就是堆頂元素始終保持的是最小值臭埋，假如在最小堆中我們把堆頂元素一個個給移除不就相當于排序了嗎踪央。我們來測試一下
int[] array = {10, 4, 8, 3, 5, 1};
System.out.print("數(shù)組原始的值：");
Util.printIntArrays(array);
MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
@Override
public int compare(Integer o, Integer t1) {
return (o - t1 > 0) ? 1 : -1;
}
});
for (int i = 0; i < array.length; i++) {
myHeap.add(array[i]);
}
System.out.println();
System.out.print("堆中元素的值：");
Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
System.out.println();
System.out.print("排序之后的值：");
for (int i = 0, length = myHeap.getSize(); i < length; i++) {
System.out.print(myHeap.remove() + "\t");
}
我們來看一下打印結果
1數(shù)組原始的值：10 4 8 3 5 1
2堆中元素的值：1 4 3 10 5 8
3排序之后的值：1 3 4 5 8 10
我們看到堆中元素的值是【1，4瓢阴，3畅蹂，10，5荣恐，8】和我們最開始分析創(chuàng)建堆的結果完全一致液斜。并且最后一行完成了從小到大的順序輸出
總結：
上面我們主要分析是最小堆，如果是最大堆代碼該怎么寫呢叠穆，其實有兩種方式少漆，一種是直接在上面代碼MyHeap類中修改，還一種是在創(chuàng)建構造函數(shù)的時候重寫比較器Comparator硼被，我們這里推薦使用第二種示损，比如我們想按照從大到小的順序輸出，我們來看下該怎么寫
int[] array = {10, 4, 8, 3, 5, 1};
System.out.print("數(shù)組原始的值：");
Util.printIntArrays(array);
MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
@Override
public int compare(Integer o, Integer t1) {
return (o - t1 < 0) ? 1 : -1;
}
});
for (int i = 0; i < array.length; i++) {
myHeap.add(array[i]);
}
System.out.println();
System.out.print("堆中元素的值：");
Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
System.out.println();
System.out.print("排序之后的值：");
for (int i = 0, length = myHeap.getSize(); i < length; i++) {
System.out.print(myHeap.remove() + "\t");
}
我們只需修改一個字符即可嚷硫，就是在上面第7行把之前的大于號改為小于號检访，我們來看下運行結果
數(shù)組原始的值：10 4 8 3 5 1
堆中元素的值：10 5 8 3 4 1
排序之后的值：10 8 5 4 3 1
最后完全實現(xiàn)了從大到小的輸出僧诚。
