博客

今天分享一个用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;

2. 退出循环方式：由于声明方式将不存在的子节点的位置赋值为父节点，从而产生子节点值==父节点值的效果。因此上述的一行退出循环语句就包含了两种可能：
   • 当节点下移至叶子节点时
   • 当节点下移至无法交换（但还未到叶子节点）时

if(smallHeap[left] >= smallHeap[parent] && smallHeap[right] >= smallHeap[parent]) break;