上移與下移堆節點的最優寫法

今天分享一個用Java編寫的小根堆的節點上移與下移的最佳實踐，上移對應着堆節點的插入，下移對應着堆頂節點的删除

//将整數數組nums變更為小根堆
int[] smallHeap = new int[nums.length]; //聲明小根堆
smallHeap[0] = nums[0];
//構造小根堆
for(int i = 1; i < nums.length; i++){
	smallHeap[i] = nums[i];
	shiftUp(i, smallHeap);   
} 
public void shiftUp(index, smallHeap){
    while(index > 0){
        int parent = (index - 1) / 2;
        if(smallHeap[parent] <= smallHeap[index]) break;
        int tmp = smallHeap[parent];
        smallHeap[parent] = smallHeap[index];
        smallHeap[index] = tmp;
        index = parent;
    }
}
public void shiftDown(parent, smallHeap){
	int len = smallHeap.length;
	while(parent < len){
	   int left = 2 * parent + 1 > len - 1 ? parent : 2 * parent + 1;
       int right = 2 * parent + 2 > len - 1 ? parent : 2 * parent + 2;
       if(smallHeap[left] >= smallHeap[parent] && smallHeap[right] >= smallHeap[parent]) break;
       int index = smallHeap[right] < smallHeap[left] ? right : left;
       int tmp = smallHeap[parent];
       smallHeap[parent] = smallHeap[index];
       smallHeap[index] = tmp;
       parent = index;
   }
}
           

該最佳實踐的巧妙之處在于shiftDown部分對left和right的處理手段：

1. 聲明方式：采用條件語句，充分利用等于時不發生交換的情形，進而避開了在後續繼續編寫對子節點是否存在進行判斷的邏輯

int left = 2 * parent + 1 > len - 1 ? parent : 2 * parent + 1;
int right = 2 * parent + 2 > len - 1 ? parent : 2 * parent + 2;
           

1. 退出循環方式：由于聲明方式将不存在的子節點的位置指派為父節點，進而産生子節點值==父節點值的效果。是以上述的一行退出循環語句就包含了兩種可能：
   • 當節點下移至葉子節點時
   • 當節點下移至無法交換（但還未到葉子節點）時