|
Make magic out of simple things.
在平凡中創(chuàng)造奇跡,。 基礎(chǔ)知識通常情況下我們把堆看成是一棵完全二叉樹,。堆一般分為兩種,，一種是最大堆，一種是最小堆,。最大堆要求根節(jié)點的值即大于左子樹的值,，又大于右子樹的值。也就是說最大堆根節(jié)點的值是堆中最大的,。最小堆根節(jié)點的值是堆中最小的,，前面我們講堆排序的時候介紹過堆，實際上他就是數(shù)組結(jié)構(gòu),，但因為數(shù)組中間有關(guān)聯(lián),，所以我們可以把它當(dāng)做一棵完全二叉樹來看，下面我們再來看一下堆的數(shù)據(jù)結(jié)構(gòu)是什么樣的,。
結(jié)點中的數(shù)字是數(shù)組元素的下標(biāo),，不是數(shù)組元素的值。所以如果我們知道父節(jié)點的下標(biāo)我們就可以知道他的兩個子節(jié)點（如果有子節(jié)點）,，如果知道子節(jié)點的下標(biāo)也一定能找到父節(jié)點的下標(biāo),，他們的關(guān)系是：
父節(jié)點的下標(biāo)=（子節(jié)點下標(biāo)-1）>>1；
左子節(jié)點下標(biāo)=父節(jié)點下標(biāo)*2+1,；
右子節(jié)點下標(biāo)=父節(jié)點下標(biāo)*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】
堆的刪除堆的添加會往上調(diào)整,，堆的刪除不僅會往下調(diào)整而且還有可能往上調(diào)整。堆中元素的刪除我們可以從堆頂刪除,，也可以從中間某個位置刪除,，如果從堆頂刪除的話我們只需要往下調(diào)整即可，因為堆頂沒有父節(jié)點,，不需要往上調(diào)整,。如果從中間刪除的話，我們先要往下調(diào)整,，如果往下調(diào)整沒有成功（比如在最小堆中,，他比兩個子節(jié)點都小）,，我們還要進行往上的調(diào)整,。調(diào)整的原理就是把數(shù)組最后一個元素放到要刪除的元素位置上，然后在刪除元素的位置上進行上下調(diào)整,，原理其實都差不多,，我們來看一下最小堆頂部元素刪除之后的調(diào)整。
上面是我們把堆頂元素1刪除之后堆的調(diào)整,，如果我們再把堆頂元素3刪除之后,，只需要用數(shù)組的最后一個元素5替換3，然后再往下調(diào)整即可……
代碼堆的添加和刪除我們都分析過了,，如果把前面的分析都搞懂的話,，那么堆的代碼就很容易寫了，我們來看下
1public class MyHeap<E> {
2 private Object[] data;//數(shù)據(jù)存放區(qū)
3 private int size;//堆的大小
4 private Comparator<? super E> comparator;//比較器
5
6 public MyHeap(int initialCapacity) {
7 this(initialCapacity, null);
8 }
9
10 public MyHeap(int initialCapacity, Comparator<? super E> comparator) {
11 if (initialCapacity < 1)
12 throw new IllegalArgumentException("堆的大小必須大于0");
13 this.data = new Object[initialCapacity];
14 this.comparator = comparator;
15 }
16
17 /**
18 * @param e 向堆中添加元素
19 * @return
20 */
21 public boolean add(E e) {
22 if (e == null)//不能為空
23 throw new NullPointerException();
24 if (size >= data.length)//如果堆的空間不夠了就擴容,，這里是擴大2倍
25 data = Arrays.copyOf(data, data.length << 1);
26 if (size == 0)//如果堆是空的,，直接添加就可以了，不需要調(diào)整,，因為就一個沒發(fā)調(diào)整
27 data[0] = e;
28 else//如果堆不是空的,，就要往上調(diào)整。
29 siftUp(e);
30 size++;//添加完之后size要加1
31 return true;
32 }
33
34 public int getSize() {
35 return size;
36 }
37
38 //刪除堆頂元素
39 public E remove() {
40 if (size == 0)
41 return null;
42 size--;
43 E result = (E) data[0];//獲取堆頂?shù)脑?/span>
44 E x = (E) data[size];//取出數(shù)組的最后一個元素
45 data[size] = null;//然后把最后一個元素的位置置空
46 if (size != 0)
47 siftDown(x);//這里實際上是把數(shù)組的最后一個元素取出放到棧頂,，然后再往下調(diào)整。
48 return result;
49 }
50
51 //訪問堆頂元素,，不刪除
52 public E peek() {
53 return (size == 0) ? null : (E) data[0];
54 }
55
56 /**
57 * 返回數(shù)組的值
58 *
59 * @param a
60 * @param <T>
61 * @return
62 */
63 public <T> T[] toArray(T[] a) {
64 if (a.length < size)
65 return (T[]) Arrays.copyOf(data, size, a.getClass());
66 System.arraycopy(data, 0, a, 0, size);
67 if (a.length > size)
68 a[size] = null;
69 return a;
70 }
71
72 /**
73 * 往上調(diào)整，往上調(diào)整只需要和父節(jié)點比較即可,，如果比父節(jié)點大就不需要在調(diào)整
74 *
75 * @param e
76 */
77 private void siftUp(E e) {
78 int s = size;
79 while (s > 0) {
80 int parent = (s - 1) >>> 1;//根據(jù)子節(jié)點的位置可以找到父節(jié)點的位置
81 Object pData = data[parent];
82 //和父節(jié)點比較,，如果比父節(jié)點大就退出循環(huán)不再調(diào)整
83 if (comparator != null) {
84 if (comparator.compare(e, (E) pData) >= 0)
85 break;
86 } else {
87 if (((Comparable<? super E>) e).compareTo((E) pData) >= 0)
88 break;
89 }
90 //如果比父節(jié)點小，就和父節(jié)點交換,，然后再繼續(xù)往上調(diào)整
91 data[s] = pData;
92 s = parent;
93 }
94 //通過上面的往上調(diào)整,，找到合適的位置，再把e放進去
95 data[s] = e;
96 }
97
98 /**
99 * 往下調(diào)整,，往下調(diào)整需要和他的兩個子節(jié)點（如果有兩個子節(jié)點）都要比較,，哪個最小就和哪
100 * 個交換，如果比兩個子節(jié)點都小就不用再交換
101 *
102 * @param e
103 */
104 private void siftDown(E e) {
105 int half = size >>> 1;
106 int index = 0;
107 while (index < half) {
108 int min = (index << 1) + 1;//根據(jù)父節(jié)點的位置可以找到左子節(jié)點的位置
109 Object minChild = data[min];
110 int right = min + 1;//根據(jù)左子節(jié)點找到右子節(jié)點的位置
111 if (right < size) {//如果有右子節(jié)點就執(zhí)行這里的代碼
112 //如果有右子節(jié)點,，肯定會有左子節(jié)點,。那么就需要左右兩個子節(jié)點比較，把小的賦值給minChild
113 if (comparator != null) {
114 if (comparator.compare((E) minChild, (E) data[right]) > 0)
115 minChild = data[min = right];
116 } else {
117 if (((Comparable<? super E>) minChild).compareTo((E) data[right]) > 0)
118 minChild = data[min = right];
119 }
120 }
121 //用節(jié)點e和他的最小的子節(jié)點比較,，如果小于他最小的子節(jié)點就退出循環(huán),，不再往下調(diào)整了，
122 if (comparator != null) {
123 if (comparator.compare(e, (E) minChild) <= 0)
124 break;
125 } else {
126 if (((Comparable<? super E>) e).compareTo((E) minChild) <= 0)
127 break;
128 }
129 //如果e比它的最小的子節(jié)點小,，就用最小的子節(jié)點和e交換位置,，然后再繼續(xù)往下調(diào)整。
130 data[index] = minChild;
131 index = min;
132 }
133 data[index] = e;
134 }
135}
這里的刪除和添加操作的都是堆頂?shù)脑?，所以添加的時候會調(diào)用siftUp進行往上調(diào)整,，刪除的時候會調(diào)用siftDown進行往下調(diào)整。我把注釋都寫在代碼中了,，這里就不再詳細介紹,。
堆排序通過上面的分析，我們知道最大堆就是堆頂元素始終保持的是最大值,，最小堆就是堆頂元素始終保持的是最小值,，假如在最小堆中我們把堆頂元素一個個給移除不就相當(dāng)于排序了嗎。我們來測試一下
1 int[] array = {10, 4, 8, 3, 5, 1};
2 System.out.print("數(shù)組原始的值：");
3 Util.printIntArrays(array);
4 MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
5 @Override
6 public int compare(Integer o, Integer t1) {
7 return (o - t1 > 0) ? 1 : -1;
8 }
9 });
10
11 for (int i = 0; i < array.length; i++) {
12 myHeap.add(array[i]);
13 }
14 System.out.println();
15 System.out.print("堆中元素的值：");
16 Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
17 System.out.println();
18 System.out.print("排序之后的值：");
19 for (int i = 0, length = myHeap.getSize(); i < length; i++) {
20 System.out.print(myHeap.remove() + "\t");
21 }
我們來看一下打印結(jié)果 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)建堆的結(jié)果完全一致。并且最后一行完成了從小到大的順序輸出
總結(jié)：上面我們主要分析是最小堆,，如果是最大堆代碼該怎么寫呢,，其實有兩種方式，一種是直接在上面代碼MyHeap類中修改,，還一種是在創(chuàng)建構(gòu)造函數(shù)的時候重寫比較器Comparator,，我們這里推薦使用第二種,，比如我們想按照從大到小的順序輸出，我們來看下該怎么寫
1 int[] array = {10, 4, 8, 3, 5, 1};
2 System.out.print("數(shù)組原始的值：");
3 Util.printIntArrays(array);
4 MyHeap myHeap = new MyHeap(10, new Comparator<Integer>() {
5 @Override
6 public int compare(Integer o, Integer t1) {
7 return (o - t1 < 0) ? 1 : -1;
8 }
9 });
10
11 for (int i = 0; i < array.length; i++) {
12 myHeap.add(array[i]);
13 }
14 System.out.println();
15 System.out.print("堆中元素的值：");
16 Util.printObjectArrays(myHeap.toArray(new Object[myHeap.getSize()]));
17 System.out.println();
18 System.out.print("排序之后的值：");
19 for (int i = 0, length = myHeap.getSize(); i < length; i++) {
20 System.out.print(myHeap.remove() + "\t");
21 }
我們只需修改一個字符即可,，就是在上面第7行把之前的大于號改為小于號,，我們來看下運行結(jié)果
1數(shù)組原始的值：10 4 8 3 5 1
2堆中元素的值：10 5 8 3 4 1
3排序之后的值：10 8 5 4 3 1
|
