E extractMax() - 提取堆中最大的元素
堆中最大的元素：
堆中最大的元素就是堆頂?shù)脑兀?/li>
從二叉樹的角度看玛瘸，堆中最大的元素就是二叉樹的根節(jié)點(diǎn)捧搞；
從數(shù)組的角度看雷恃，堆中最大的元素就是數(shù)組中索引為0的元素驾茴；
提取堆中最大的元素：
找到堆中最大的元素并返回很簡(jiǎn)單，但提取涉及到要把最大的元素從堆中刪除（即邏輯上刪除二叉樹的根事格，物理上刪除數(shù)組索引為0的元素）惕艳，就要重組剩余元素的結(jié)構(gòu)，使之仍然能夠滿足堆的定義驹愚；
具體刪除最大堆中的堆頂元素的做法如下：
讓堆頂元素和堆中最后一個(gè)元素互換位置远搪；
刪除堆中最后一個(gè)元素，即剛換過(guò)來(lái)的原堆頂元素逢捺；
下沉新堆頂元素谁鳍，使整個(gè)二叉樹重新滿足堆的定義；
// 看堆中的最大元素
public E findMax(){
if(data.getSize() == 0)
throw new IllegalArgumentException("Can not findMax when heap is empty.");
return data.get(0);
}
// 取出堆中最大元素
public E extractMax(){
E ret = findMax();
data.swap(0, data.getSize() - 1);
data.removeLast();
siftDown(0);
return ret;
}
void siftDown(int k) - 下沉新的堆頂元素
下沉的終止條件劫瞳，即k指向的元素已經(jīng)沒(méi)有可下沉的空間了倘潜，這個(gè)狀態(tài)為：k的左孩子的索引已經(jīng)大于等于size，size從索引的角度看志于，指向下一個(gè)碼元素的位置涮因；當(dāng)堆中只有一個(gè)元素，size==1伺绽，size指向堆頂元素的左孩子养泡，堆頂元素左孩子的索引也是1，下一個(gè)堆中元素的碼放位置是堆頂元素左孩子的位置憔恳，說(shuō)明堆頂元素沒(méi)有左孩子瓤荔，更沒(méi)有右孩子，這就是k沒(méi)有下沉空間的狀態(tài)了钥组，k但凡還有個(gè)左孩子（就是有孩子输硝，k還沒(méi)到最底層），它就還有下沉的空間 程梦；
用一個(gè)指針j指向k的左孩子点把；
看 k 是否還有右孩子，并且 k 的右孩子比 k 的左孩子大屿附，那么讓 j 指向 k 的右孩子郎逃，否則 j 還指向 k 的左孩子，此時(shí) j 指向 k 的疑似下沉位置 挺份；
k 和其疑似下沉位置 做比較褒翰，如果 k 不比其疑似下沉位置 的元素小，則不需要下沉，跳出循環(huán)优训，下沉動(dòng)作結(jié)束朵你；
如果 k 比其疑似下沉位置 的元素小，開始下沉動(dòng)作揣非，交換 k 和其疑似下沉位置 的元素抡医；
下沉完成以后，讓 k 重新追上待下沉元素早敬；
private void siftDown(int k){
while(leftChild(k) < data.getSize()){
int j = leftChild(k);
// 如果k有右孩子忌傻，并且右孩子比左孩子大
if( j + 1 < data.getSize() &&
data.get(j + 1).compareTo(data.get(j)) > 0 )
j ++; // j 指向 leftChild 和 rightChild 中更大的那一個(gè)
// 如果不需要下沉，跳出循環(huán)搞监，下沉動(dòng)作結(jié)束
if(data.get(k).compareTo(data.get(j)) >= 0 )
break;
// k 和 j 交換位置水孩，待下沉元素和左右孩子中更大的那個(gè)交換位置
data.swap(k, j);
// k 重新追上待下沉的元素
k = j;
}
}
最后編輯于 ：2019.03.13 23:40:17
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
