摘要：亦即總結(jié)常見的的數(shù)據(jù)結(jié)構(gòu)，以及在中相應(yīng)的實(shí)現(xiàn)方法，務(wù)求理論與實(shí)踐一步總結(jié)到位。中，使用鏈表作為其基礎(chǔ)實(shí)現(xiàn)。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。
前言
仿佛一下子，2017年就快過去一半了，研一馬上就要成為過去式了，我打算抓住研一的尾巴，好好梳理一下數(shù)據(jù)結(jié)構(gòu)與算法，畢竟這些基礎(chǔ)知識是很重要的嘛。所以準(zhǔn)備在這里搞一個系列的文章，以期透徹。
本系列將采用Java語言來進(jìn)行描述。亦即總結(jié)常見的的數(shù)據(jù)結(jié)構(gòu)，以及在Java中相應(yīng)的實(shí)現(xiàn)方法，務(wù)求理論與實(shí)踐一步總結(jié)到位。
首先給出Java集合框架的基本接口/類層次結(jié)構(gòu)：
java.util.Collection [I]
+--java.util.List [I]
+--java.util.ArrayList [C]
+--java.util.LinkedList [C]
+--java.util.Vector [C] //線程安全
+--java.util.Stack [C] //線程安全
+--java.util.Set [I]
+--java.util.HashSet [C]
+--java.util.SortedSet [I]
+--java.util.TreeSet [C]
+--Java.util.Queue[I]
+--java.util.Deque[I]
+--java.util.PriorityQueue[C]
java.util.Map [I]
+--java.util.SortedMap [I]
+--java.util.TreeMap [C]
+--java.util.Hashtable [C] //線程安全
+--java.util.HashMap [C]
+--java.util.LinkedHashMap [C]
+--java.util.WeakHashMap [C]
[I]：接口
[C]：類
本圖來源于網(wǎng)絡(luò)。
數(shù)組
數(shù)組是相同數(shù)據(jù)類型的元素按一定順序排列的集合，是一塊連續(xù)的內(nèi)存空間。數(shù)組的優(yōu)點(diǎn)是：get和set操作時間上都是O(1)的；缺點(diǎn)是：add和remove操作時間上都是O(N)的。
Java中，Array就是數(shù)組，此外，ArrayList使用了數(shù)組Array作為其實(shí)現(xiàn)基礎(chǔ),它和一般的Array相比，最大的好處是，我們在添加元素時不必考慮越界，元素超出數(shù)組容量時，它會自動擴(kuò)張保證容量。
Vector和ArrayList相比，主要差別就在于多了一個線程安全性，但是效率比較低下。如今java.util.concurrent包提供了許多線程安全的集合類（比如 LinkedBlockingQueue），所以不必再使用Vector了。
int[] ints = new int[10];
ints[0] = 5;//set
int a = ints[2];//get
int len = ints.length;//數(shù)組長度
鏈表
鏈表是一種非連續(xù)、非順序的結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的，鏈表由一系列結(jié)點(diǎn)組成。鏈表的優(yōu)點(diǎn)是：add和remove操作時間上都是O(1)的；缺點(diǎn)是：get和set操作時間上都是O(N)的，而且需要額外的空間存儲指向其他數(shù)據(jù)地址的項(xiàng)。
查找操作對于未排序的數(shù)組和鏈表時間上都是O(N)。
Java中，LinkedList 使用鏈表作為其基礎(chǔ)實(shí)現(xiàn)。
LinkedList linkedList = new LinkedList<>();
linkedList.add("affffd");//add
linkedList.set(0,"s");//set，必須先保證 linkedList中已經(jīng)有第0個元素
String s = linkedList.get(0);//get
linkedList.contains("s");//查找
linkedList.remove("s");//刪除
//以上方法也適用于ArrayList
隊列
隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端進(jìn)行刪除操作，而在表的后端進(jìn)行插入操作，亦即所謂的先進(jìn)先出（FIFO）。
Java中，LinkedList實(shí)現(xiàn)了Deque，可以做為雙向隊列（自然也可以用作單向隊列）。另外PriorityQueue實(shí)現(xiàn)了帶優(yōu)先級的隊列，亦即隊列的每一個元素都有優(yōu)先級，且元素按照優(yōu)先級排序。
Deque integerDeque = new LinkedList<>();
// 尾部入隊，區(qū)別在于如果失敗了
// add方法會拋出一個IllegalStateException異常，而offer方法返回false
integerDeque.offer(122);
integerDeque.add(122);
// 頭部出隊,區(qū)別在于如果失敗了
// remove方法拋出一個NoSuchElementException異常，而poll方法返回false
int head = integerDeque.poll();//返回第一個元素，并在隊列中刪除
head = integerDeque.remove();//返回第一個元素，并在隊列中刪除
// 頭部出隊，區(qū)別在于如果失敗了
// element方法拋出一個NoSuchElementException異常，而peek方法返回null。
head = integerDeque.peek();//返回第一個元素，不刪除
head = integerDeque.element();//返回第一個元素，不刪除
棧
棧（stack）又名堆棧，它是一種運(yùn)算受限的線性表。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算。這一端被稱為棧頂，相對地，把另一端稱為棧底。它體現(xiàn)了后進(jìn)先出（LIFO）
的特點(diǎn)。
Java中，Stack實(shí)現(xiàn)了這種特性，但是Stack也繼承了Vector，所以具有線程安全線和效率低下兩個特性，最新的JDK8中，推薦用Deque來實(shí)現(xiàn)棧，比如：
Deque stack = new ArrayDeque();
stack.push(12);//尾部入棧
stack.push(16);//尾部入棧
int tail = stack.pop();//尾部出棧，并刪除該元素
tail = stack.peek();//尾部出棧，不刪除該元素
集合
集合是指具有某種特定性質(zhì)的具體的或抽象的對象匯總成的集體，這些對象稱為該集合的元素，其主要特性是元素不可重復(fù)。
在Java中，HashSet 體現(xiàn)了這種數(shù)據(jù)結(jié)構(gòu)，而HashSet是在MashMap的基礎(chǔ)上構(gòu)建的。LinkedHashSet繼承了HashSet，使用HashCode確定在集合中的位置，使用鏈表的方式確定位置，所以有順序。TreeSet實(shí)現(xiàn)了SortedSet 接口，是排好序的集合（在TreeMap 基礎(chǔ)之上構(gòu)建），因此查找操作比普通的Hashset要快（log(N)）；插入操作要慢（log（N））,因?yàn)橐S護(hù)有序。
HashSet integerHashSet = new HashSet<>();
integerHashSet.add(12121);//添加
integerHashSet.contains(121);//是否包含
integerHashSet.size();//集合大小
integerHashSet.isEmpty();//是否為空
散列表
散列表也叫哈希表，是根據(jù)關(guān)鍵鍵值(Keyvalue)進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度，這個映射函數(shù)叫做散列函數(shù)。
Java中HashMap實(shí)現(xiàn)了散列表，而Hashtable比它多了一個線程安全性，但是由于使用了全局鎖導(dǎo)致其性能較低，所以現(xiàn)在一般用ConcurrentHashMap來實(shí)現(xiàn)線程安全的HashMap（類似的，以上的數(shù)據(jù)結(jié)構(gòu)在最新的java.util.concurrent的包中幾乎都有對應(yīng)的高性能的線程安全的類）。TreeMap實(shí)現(xiàn)SortMap接口，能夠把它保存的記錄按照鍵排序。LinkedHashMap保留了元素插入的順序。WeakHashMap是一種改進(jìn)的HashMap，它對key實(shí)行“弱引用”，如果一個key不再被外部所引用，那么該key可以被GC回收，而不需要我們手動刪除。
HashMap hashMap = new HashMap<>();
hashMap.put(1,"asdsa");//添加
hashMap.get(1);//獲得
hashMap.size();//元素個數(shù)
樹
樹（tree）是包含n（n>0）個節(jié)點(diǎn)的有窮集合，其中：
每個元素稱為節(jié)點(diǎn)（node）；
有一個特定的節(jié)點(diǎn)被稱為根節(jié)點(diǎn)或樹根（root）。
除根節(jié)點(diǎn)之外的其余數(shù)據(jù)元素被分為m（m≥0）個互不相交的結(jié)合T1，T2，……Tm-1，其中每一個集合Ti（1<=i<=m）本身也是一棵樹，被稱作原樹的子樹（subtree）。
樹這種數(shù)據(jù)結(jié)構(gòu)在計算機(jī)世界中有廣泛的應(yīng)用，比如操作系統(tǒng)中用到了紅黑樹，數(shù)據(jù)庫用到了B+樹，編譯器中的語法樹，內(nèi)存管理用到了堆（本質(zhì)上也是樹），信息論中的哈夫曼編碼等等等等，在Java中TreeSet和TreeMap用到了樹來排序（二分查找提高檢索速度），不過一般都需要程序員自己去定義一個樹的類，并實(shí)現(xiàn)相關(guān)性質(zhì)，而沒有現(xiàn)成的API。下面就用Java來實(shí)現(xiàn)各種常見的樹。
二叉樹
二叉樹是一種基礎(chǔ)而且重要的數(shù)據(jù)結(jié)構(gòu)，其每個結(jié)點(diǎn)至多只有二棵子樹，二叉樹有左右子樹之分，第i層至多有2^(i-1)個結(jié)點(diǎn)（i從1開始）；深度為k的二叉樹至多有2^(k)-1)個結(jié)點(diǎn)，對任何一棵二叉樹，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。
二叉樹的性質(zhì)：
1) 在非空二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2^(i-1), i>=1;
2) 深度為h的二叉樹最多有2^h-1個結(jié)點(diǎn)(h>=1)，最少有h個結(jié)點(diǎn);
3) 對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1;
4) 具有n個結(jié)點(diǎn)的完全二叉樹的深度為log2(n+1);
5)有N個結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲，則結(jié)點(diǎn)之間有如下關(guān)系：
若I為結(jié)點(diǎn)編號則 如果I>1，則其父結(jié)點(diǎn)的編號為I/2；
如果2I<=N，則其左兒子（即左子樹的根結(jié)點(diǎn)）的編號為2I；若2I>N，則無左兒子；
如果2I+1<=N，則其右兒子的結(jié)點(diǎn)編號為2I+1；若2I+1>N，則無右兒子。
6)給定N個節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹，其中h(N)為卡特蘭數(shù)的第N項(xiàng)，h(n)=C(2*n, n)/(n+1)。
7)設(shè)有i個枝點(diǎn)，I為所有枝點(diǎn)的道路長度總和，J為葉的道路長度總和J=I+2i。
滿二叉樹、完全二叉樹
滿二叉樹：除最后一層無任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個子結(jié)點(diǎn)；
完全二叉樹：若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～(h-1)層) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹；
滿二叉樹是完全二叉樹的一個特例。
二叉查找樹
二叉查找樹，又稱為是二叉排序樹（Binary Sort Tree）或二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：
1) 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
2) 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
3) 左、右子樹也分別為二叉排序樹；
4) 沒有鍵值相等的節(jié)點(diǎn)。
二叉查找樹的性質(zhì)：對二叉查找樹進(jìn)行中序遍歷，即可得到有序的數(shù)列。
二叉查找樹的時間復(fù)雜度：它和二分查找一樣，插入和查找的時間復(fù)雜度均為O(logn)，但是在最壞的情況下仍然會有O(n)的時間復(fù)雜度。原因在于插入和刪除元素的時候，樹沒有保持平衡。我們追求的是在最壞的情況下仍然有較好的時間復(fù)雜度，這就是平衡二叉樹設(shè)計的初衷。
二叉查找樹可以這樣表示：
public class BST, Value> {
private Node root; // 根節(jié)點(diǎn)
private class Node {
private Key key; // 排序的間
private Value val; // 相應(yīng)的值
private Node left, right; // 左子樹，右子樹
private int size; // 以該節(jié)點(diǎn)為根的樹包含節(jié)點(diǎn)數(shù)量
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
public BST() {}
public int size() {//獲得該二叉樹節(jié)點(diǎn)數(shù)量
return size(root);
}
private int size(Node x) {獲得以該節(jié)點(diǎn)為根的樹包含節(jié)點(diǎn)數(shù)量
if (x == null) return 0;
else return x.size;
}
}
查找：
public Value get(Key key) {
return get(root, key);
}
private Value get(Node x, Key key) {//在以x節(jié)點(diǎn)為根的樹中查找key
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) return get(x.left, key);//遞歸左子樹查找
else if (cmp > 0) return get(x.right, key);//遞歸右子樹查找
else return x.val;//找到了
}
插入：
public void put(Key key, Value val) {
root = put(root, key, val);
}
private Node put(Node x, Key key, Value val) {在以x節(jié)點(diǎn)為根的樹中查找key，val
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = put(x.left, key, val);//遞歸左子樹插入
else if (cmp > 0) x.right = put(x.right, key, val);//遞歸右子樹插入
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);
return x;
}
刪除：
public Key min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) return x;
else return min(x.left);
}
public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node x) {//刪除以x為根節(jié)點(diǎn)的子樹最小值
if (x.left == null) return x.right;
x.left = deleteMin(x.left);
x.size = size(x.left) + size(x.right) + 1;
return x;
}
public void delete(Key key) {
root = delete(root, key);
}
private Node delete(Node x, Key key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = delete(x.left, key);//遞歸刪除左子樹
else if (cmp > 0) x.right = delete(x.right, key);//遞歸刪除右子樹
else { //該節(jié)點(diǎn)就是所要刪除的節(jié)點(diǎn)
if (x.right == null) return x.left;//沒有右子樹，把左子樹掛在原節(jié)點(diǎn)父節(jié)點(diǎn)上
if (x.left == null) return x.right;//沒有左子樹，，把右子樹掛在原節(jié)點(diǎn)父節(jié)點(diǎn)上
Node t = x;//用右子樹中最小的節(jié)點(diǎn)來替代被刪除的節(jié)點(diǎn)，仍然保證樹的有序性
x = min(t.right);
x.right = deleteMin(t.right);
x.left = t.left;
}
x.size = size(x.left) + size(x.right) + 1;
return x;
}
平衡二叉樹
平衡二叉樹又被稱為AVL樹，具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。它的出現(xiàn)就是解決二叉查找樹不平衡導(dǎo)致查找效率退化為線性的問題，因?yàn)樵趧h除和插入之時會維護(hù)樹的平衡，使得查找時間保持在O(logn)，比二叉查找樹更穩(wěn)定。
ALLTree 的 Node 由 BST 的 Node 加上 private int height; 節(jié)點(diǎn)高度屬性即可，這是為了便于判斷樹是否平衡。
維護(hù)樹的平衡關(guān)鍵就在于旋轉(zhuǎn)。對于一個平衡的節(jié)點(diǎn)，由于任意節(jié)點(diǎn)最多有兩個兒子，因此高度不平衡時，此節(jié)點(diǎn)的兩顆子樹的高度差2.容易看出，這種不平衡出現(xiàn)在下面四種情況：
1、6節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度比右子樹7節(jié)點(diǎn)大2，左子樹3節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度大于右子樹4節(jié)點(diǎn)，這種情況成為左左。
2、6節(jié)點(diǎn)的左子樹2節(jié)點(diǎn)高度比右子樹7節(jié)點(diǎn)大2，左子樹2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度小于右子樹4節(jié)點(diǎn)，這種情況成為左右。
3、2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度比右子樹5節(jié)點(diǎn)小2，右子樹5節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度大于右子樹6節(jié)點(diǎn)，這種情況成為右左。
4、2節(jié)點(diǎn)的左子樹1節(jié)點(diǎn)高度比右子樹4節(jié)點(diǎn)小2，右子樹4節(jié)點(diǎn)的左子樹3節(jié)點(diǎn)高度小于右子樹6節(jié)點(diǎn)，這種情況成為右右。
從圖2中可以可以看出，1和4兩種情況是對稱的，這兩種情況的旋轉(zhuǎn)算法是一致的，只需要經(jīng)過一次旋轉(zhuǎn)就可以達(dá)到目標(biāo)，我們稱之為單旋轉(zhuǎn)。2和3兩種情況也是對稱的，這兩種情況的旋轉(zhuǎn)算法也是一致的，需要進(jìn)行兩次旋轉(zhuǎn)，我們稱之為雙旋轉(zhuǎn)。
單旋轉(zhuǎn)是針對于左左和右右這兩種情況，這兩種情況是對稱的，只要解決了左左這種情況，右右就很好辦了。圖3是左左情況的解決方案，節(jié)點(diǎn)k2不滿足平衡特性，因?yàn)樗淖笞訕鋕1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的左子樹X子樹，所以屬于左左情況。
為使樹恢復(fù)平衡，我們把k1變成這棵樹的根節(jié)點(diǎn)，因?yàn)閗2大于k1，把k2置于k1的右子樹上，而原本在k1右子樹的Y大于k1，小于k2，就把Y置于k2的左子樹上，這樣既滿足了二叉查找樹的性質(zhì)，又滿足了平衡二叉樹的性質(zhì)。
這樣的操作只需要一部分指針改變，結(jié)果我們得到另外一顆二叉查找樹，它是一棵AVL樹，因?yàn)閄向上一移動了一層，Y還停留在原來的層面上，Z向下移動了一層。整棵樹的新高度和之前沒有在左子樹上插入的高度相同，插入操作使得X高度長高了。因此，由于這顆子樹高度沒有變化，所以通往根節(jié)點(diǎn)的路徑就不需要繼續(xù)旋轉(zhuǎn)了。
代碼：
private int height(Node t){
return t == null ? -1 : t.height;
}
//左左情況單旋轉(zhuǎn)
private Node rotateWithLeftChild(Node k2){
Node k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), k2.height) + 1;
return k1; //返回新的根
}
//右右情況單旋轉(zhuǎn)
private Node rotateWithRightChild(Node k2){
Node k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k1.size = k2.size;
k2.size = size(k2.right)+size(k2.left)+1;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.right), k2.height) + 1;
return k1; //返回新的根
}
雙旋轉(zhuǎn)是針對于左右和右左這兩種情況，單旋轉(zhuǎn)不能使它達(dá)到一個平衡狀態(tài)，要經(jīng)過兩次旋轉(zhuǎn)。同樣的，這樣兩種情況也是對稱的，只要解決了左右這種情況，右左就很好辦了。圖4是左右情況的解決方案，節(jié)點(diǎn)k3不滿足平衡特性，因?yàn)樗淖笞訕鋕1比右子樹Z深2層，而且k1子樹中，更深的一層的是k1的右子樹k2子樹，所以屬于左右情況。
為使樹恢復(fù)平衡，我們需要進(jìn)行兩步，第一步，把k1作為根，進(jìn)行一次右右旋轉(zhuǎn)，旋轉(zhuǎn)之后就變成了左左情況，所以第二步再進(jìn)行一次左左旋轉(zhuǎn)，最后得到了一棵以k2為根的平衡二叉樹樹。
代碼：
//左右情況
private Node doubleWithLeftChild(Node k3){
try{
k3.left = rotateWithRightChild(k3.left);
}catch(NullPointerException e){
System.out.println("k.left.right為："+k3.left.right);
throw e;
}
return rotateWithLeftChild(k3);
}
//右左情況
private Node doubleWithRightChild(Node k3){
try{
k3.right = rotateWithLeftChild(k3.right);
}catch(NullPointerException e){
System.out.println("k.right.left為："+k3.right.left);
throw e;
}
return rotateWithRightChild(k3);
}
AVL查找操作與BST相同，AVL的刪除與插入操作在BST基礎(chǔ)之上需要檢查是否平衡，如果不平衡就要使用旋轉(zhuǎn)操作來維持平衡:
private Node balance(Node x) {
if (balanceFactor(x) < -1) {//右邊高
if (balanceFactor(x.right) > 0) {//右左
x.right = rotateWithLeftChild(x.right);
}
x = rotateWithRightChild(x);
}
else if (balanceFactor(x) > 1) {//左邊高
if (balanceFactor(x.left) < 0) {//左右
x.left = rotateWithRightChild(x.left);
}
x = rotateWithLeftChild(x);
}
return x;
}
private int balanceFactor(Node x) {
return height(x.left) - height(x.right);
}
堆
堆是一顆完全二叉樹，在這棵樹中，所有父節(jié)點(diǎn)都滿足大于等于其子節(jié)點(diǎn)的堆叫大根堆，所有父節(jié)點(diǎn)都滿足小于等于其子節(jié)點(diǎn)的堆叫小根堆。堆雖然是一顆樹，但是通常存放在一個數(shù)組中，父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的父子關(guān)系通過數(shù)組下標(biāo)來確定。如下圖的小根堆及存儲它的數(shù)組：
值： 7,8,9,12,13,11
數(shù)組索引： 0,1,2,3, 4, 5
通過一個節(jié)點(diǎn)在數(shù)組中的索引怎么計算出它的父節(jié)點(diǎn)及左右孩子節(jié)點(diǎn)的索引：
public int left(int i) {
return (i + 1) * 2 - 1;
}
public int right(int i) {
return (i + 1) * 2;
}
public int parent(int i) {
// i為根結(jié)點(diǎn)
if (i == 0) {
return -1;
}
return (i - 1) / 2;
}
維護(hù)大根堆的性質(zhì)：
public void heapify(T[] a, int i, int heapLength) {
int l = left(i);
int r = right(i);
int largest = -1;
//尋找根節(jié)點(diǎn)及其左右子節(jié)點(diǎn)，三個元素中的最大值
if (l < heapLength && a[i].compareTo(a[l]) < 0) {
largest = l;
} else {
largest = i;
}
if (r < heapLength && a[largest].compareTo(a[r]) < 0) {
largest = r;
}
// 如果i處元素不是最大的，就把i處的元素與最大處元素交換，使得i處元素變?yōu)樽畲蟮? if (i != largest) {
T temp = a[i];
a[i] = a[largest];
a[largest] = temp;
// 交換元素后，以a[i]為根的樹可能不在滿足大根堆性質(zhì)，于是遞歸調(diào)用該方法
heapify(a, largest, heapLength);
}
}
構(gòu)造堆：
public void buildHeap(T[] a, int heapLength) {
//從后往前看lengthParent處的元素是第一個有子節(jié)點(diǎn)的元素，所以從它開始，進(jìn)行堆得維護(hù)
int lengthParent = parent(heapLength - 1);
for(int i = lengthParent; i >= 0; i--){
heapify(a, i, heapLength);
}
}
堆的用途：堆排序，優(yōu)先級隊列。此外由于調(diào)整代價較小，也適合實(shí)時類型的排序與變更。
后記
寫著寫著就發(fā)現(xiàn)要想總結(jié)到位是一項(xiàng)非常龐大的工程，路漫漫其修遠(yuǎn)兮。吾將上下而求索啊。
歡迎訪問我的主頁 mageek
參考與感謝：
JDK1.8源碼
數(shù)據(jù)結(jié)構(gòu)與算法——Java語言實(shí)現(xiàn)
代碼主要來自-算法第四版
http://www.cnblogs.com/maybe2...
http://blog.csdn.net/hero_mys...
http://www.cppblog.com/cxiaoj...
http://blog.csdn.net/liyong19...
http://blog.csdn.net/l2942654...
