Summary of heap sorting related knowledge

Related connection ：

Heap sorting diagram

---

Reference code ：

public static void heapSort(int[] nums){
    
   int len = nums.length;
   //1. Building the largest pile ： From bottom to top , From left to right 
   for(int i = len / 2 - 1; i >= 0; i--){
    
       heapify(nums, i, len);
   }
   //2. Every adjustment 0 Elements and  “ The last element ”  The location of 
   for (int i = len - 1; i > 0; i--) {
    
       swap(nums, 0, i);// Will be the first 0 Elements and  “ The last element ”  Exchange the positions of 
       heapify(nums, 0, i);// After the exchange, start from 0 Elements begin to adjust the remaining elements to the maximum heap 
   }
}

public static void heapify(int[] nums, int i, int n){
    
   int l = i * 2 + 1;// Left child index 
   int r = i * 2 + 2;// Right child index 
   int maxIndex = i;
   if(l < n && nums[l] > nums[maxIndex])maxIndex = l;
   if(r < n && nums[r] > nums[maxIndex])maxIndex = r;
   if(maxIndex != i){
    // It indicates that the child node has a value larger than the root node , Want to swap 
       swap(nums, maxIndex, i);// In exchange for 
       heapify(nums, maxIndex, n);// After the exchange, the maxIndex The nodes with root nodes are adjusted to the maximum heap 
   }
}

public static void swap(int[] nums, int i, int j){
    
   int temp = nums[i];
   nums[i] = nums[j];
   nums[j] = temp;
}

---

Related instructions ：

1. A random array can actually be treated as a heap , So directly in the array ( Pile up ) Just operate on .

2. Ascending , Generally, the heap is converted to the maximum heap , Descending , Generally, the heap is converted to the smallest heap .

3. From bottom to top , From right to left , Find the first non leaf node and start the transformation .

4. When transforming , If the value of left and right children is not greater than the node , No adjustment , skip , Convert to the next node ; otherwise , Exchange the larger of the parent node value and the child node value , Then, the child nodes to be exchanged are converted back to the maximum heap , Note here ： The transformation is from top to bottom , Because at this time, only this child node may be smaller than its child node , And the child nodes of this child node must conform to the maximum heap , There is no need to adjust from bottom to top .

5. When making the maximum heap adjustment , From len / 2 - 1 Nodes are adjusted from back to front , Adjust until the 0 Nodes .

6. After transformation , Start sorting ：
The largest element of the root node and the len - 1 Exchange elements , After exchange, the root element does not conform to the maximum heap , And its sub elements conform to the maximum heap , So it is converted from top to bottom to the maximum heap . Pay attention to the rest len - 1 Elements to adjust ( Corresponding relation ).
From the largest element of the root node and the len - 2 Exchange elements , After exchange, the root element does not conform to the maximum heap , And its sub elements conform to the maximum heap , So it is converted from top to bottom to the maximum heap . Pay attention to the rest len - 2 Elements to adjust ( Corresponding relation ).
…
Finally, only one index is left 0 The elements of , Also the smallest element , No sorting , So the cycle len - 1 Time .

7. The index for i The elements of , The left child index is 2 * i + 1, The right child index is 2 * i + 2;

8. Complexity of time and space ： Building the heap O(N); Sort O(logN), Time complexity O(NlogN)