本小節将介紹如何從一個最大堆中取出一個元素，稱為 shift down，隻能取出最大優先級的元素，也就是根節點，把原來的 62 取出後，下面介紹如何填補這個最大堆。
第一步，我們将數組最後一位數組放到根節點，此時不滿足最大堆的定義。
調整的過程是将這個根節點 16 一步一步向下挪，16 比子節點都小，先比較子節點 52 和 30 哪個大，和大的交換位置。
繼續比較 16 的子節點 28 和 41，41 大，是以 16 和 41 交換位置。
繼續 16 和孩子節點 15 進行比較，16 大，是以現在不需要進行交換，最後我們的 shift down 操作完成，維持了一個最大堆的性質。
源碼包下載下傳：Download
package runoob.heap;
/**
* 往最大堆中取出一個元素
*/
public class HeapShiftDown<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// 構造函數, 構造一個空堆, 可容納capacity個元素
public HeapShiftDown(int capacity){
//這裡加1是指原來能裝的元素個數，那去掉0位，隻能裝capacity個元素
data = (T[])new Comparable[capacity+1];
count = 0;
this.capacity = capacity;
}
// 傳回堆中的元素個數
public int size(){
return count;
// 傳回一個布爾值, 表示堆中是否為空
public boolean isEmpty(){
return count == 0;
// 像最大堆中插入一個新的元素 item
public void insert(T item){
assert count + 1 <= capacity;
data[count+1] = item;
count ++;
shiftUp(count);
// 從最大堆中取出堆頂元素, 即堆中所存儲的最大資料
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
// 擷取最大堆中的堆頂元素
public T getMax(){
assert( count > 0 );
return data[1];
// 交換堆中索引為i和j的兩個元素
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
//********************
//* 最大堆核心輔助函數
private void shiftUp(int k){
while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
swap(k, k/2);
k /= 2;
}
//shiftDown操作
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // 在此輪循環中,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 ) break;
swap(k, j);
k = j;
System.out.println("shiftDown結束");
// 測試 HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// 堆中元素個數
int N = 100;
// 堆中元素取值範圍[0, M)
int M = 100;
for( int i = 0 ; i < N ; i ++ )
heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// 将最大堆中的資料逐漸使用extractMax取出來
// 取出來的順序應該是按照從大到小的順序取出來的
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
System.out.print(arr[i] + " ");
// 確定arr數組是從大到小排列的
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}