4.堆

标签： index arr int heapSize largest left

从0开始：

左孩子  2*i+1

右孩子  2*i+2

父       （i-1）/2

---

从1开始：

左孩子  2*i                     (i<<1)

右孩子  2*i+1                 (i<<1 | 1)

父          i/2                     (i>>1)            从1开始的比较容易，因为位运算更快

---

---

public static void heapSort(int[]arr){
     if(arr==null || arr.length<2)
         return;
     for(int i=arr.length-1;i>=0;i--)
         heapify(arr,i,arr.length);
     int heapSize=arr.length;
     swap(arr,0,--heapSize);
     while(heapSize>0){
         heapify(arr,0,heapSize);
         swap(arr,0,--heapSize);
     }
}

private void swap(int[]arr,int i,int j){
      int tmp=arr[i];
      arr[i]=arr[j];
      arr[j]=tmp;
}

//从index位置，往下看，不断地下沉
//停：1)我的孩子都不再比我大 2）已经没孩子了

private void heapify(int[]arr,int index,int heapSize){
      int left=index*2+1;
      while(left<heapSize){
           int largest=left+1<heapSize&&arr[left+1]>arr[left]?left:left+1;
           largest=arr[largest]>arr[index]?largest:index;
           if(largest==index)
               break;
           swap(arr,largest,index);
           index=largest;
           left=index*2+1;
      }
}

 

标签：,index,arr,int,heapSize,largest,left
From： https://www.cnblogs.com/ztzzh-1/p/17542605.html