堆排序

一、什么是堆排序？

• 基于堆实现的排序算法
• 利用堆顶的有序性（最大值或最小值）来实现对数组的排序

二、为什么要用堆排序？

• 唯一能够同时最优地利用空间和时间的排序算法
• 缺点是很少和相邻元素比较，导致无法利用缓存

三、怎么实现堆排序？

堆排序可以分为 2 步：

• 构建堆：将数组构建成堆
• 堆排序：一直移除堆顶元素，直到堆为空为止

先将数据建成二叉树的形式，再进行排序。

3.1 构建堆

因为每次都是移除堆顶，而堆顶一直都是最大值/最小值，所以移除堆元素就是排序的过程。

比如说，数组 [2, 7, 1, 4, 3, 6, 5]，要从小到大排序。

第一步是构建堆，将数组构建出大顶堆的结构：

                            1=>6                       7                      2=>7=>4

      2                       2                        2                         7             
   /     \                 /     \                  /     \                   /     \      
  7       1               7       6                7       6                 4       6  
 / \     / \             / \     / \              / \     / \               / \     / \     
4   3   6   5           4   3   1   5            4   3   1   5             2   3   1   5 

构建完堆以后，数组变成了这样：

              7      
           /     \   
          4       6                         -- 逻辑结构（二叉树）
         / \     / \ 
        2   3   1   5

 ___ ___ ___ ___ ___ ___ ___
| 7 | 4 | 6 | 2 | 3 | 1 | 5 |               -- 物理结构（数组）

3.2 堆排序

接下来是排序，排序过程就是一直移除堆顶元素。

被移除的堆顶元素放到数组的末尾空位（相当于末尾已经不算在堆内了）：

              7                                            6                 
           /     \                                      /     \            
          4       6                     =>             4       5           
         / \     / \                                  / \     /          
        2   3   1   5                                2   3   1        
 ___ ___ ___ ___ ___ ___ ___                        ___ ___ ___ ___ ___ ___     ___ 
| 7 | 4 | 6 | 2 | 3 | 1 | 5 |                      | 6 | 4 | 5 | 2 | 3 | 1 |   | 7 |

注意，移除堆顶的同时会调整堆结构（这个是堆的性质）。

以此类推，一直移除堆顶元素，直到堆变成空为止。

移除堆顶 6：

        6                                                  5                    
     /     \                                            /     \                
    4       5                           =>             4       1              
   / \     /                                          / \                    
  2   3   1                                          2   3                    
 ___ ___ ___ ___ ___ ___     ___                    ___ ___ ___ ___ ___     ___ ___ 
| 6 | 4 | 5 | 2 | 3 | 1 |   | 7 |                  | 5 | 4 | 1 | 2 | 3 |   | 6 | 7 |

移除堆顶 5：

        5                                                  4                  
     /     \                                            /     \               
    4       1                           =>             3       1              
   / \                                                /                       
  2   3                                              2                        
 ___ ___ ___ ___ ___     ___ ___                    ___ ___ ___ ___     ___ ___ ___ 
| 5 | 4 | 1 | 2 | 3 |   | 6 | 7 |                  | 4 | 3 | 1 | 2 |   | 5 | 6 | 7 |

移除堆顶 4：

        4                                              3                  
     /     \                                          / \               
    3       1                           =>           2   1              
   /                                                                           
  2                                                                            
 ___ ___ ___ ___     ___ ___ ___                    ___ ___ ___     ___ ___ ___ ___ 
| 4 | 3 | 1 | 2 |   | 3 | 6 | 7 |                  | 3 | 2 | 1 |   | 4 | 5 | 6 | 7 |

移除堆顶 3：

    3                                                2                  
   / \                                  =>            \               
  2   1                                                1              
 ___ ___ ___     ___ ___ ___ ___                    ___ ___     ___ ___ ___ ___ ___ 
| 3 | 2 | 1 |   | 4 | 5 | 6 | 7 |                  | 2 | 1 |   | 3 | 4 | 5 | 6 | 7 |

移除堆顶 2：

  2                                     =>           1                  
   \                                                                 
    1                                                                
 ___ ___     ___ ___ ___ ___ ___                    ___     ___ ___ ___ ___ ___ ___ 
| 2 | 1 |   | 3 | 4 | 5 | 6 | 7 |                  | 1 |   | 2 | 3 | 4 | 5 | 6 | 7 |

至此，堆排序结束，数据已经排好序了。

四、算法分析

4.1 时间复杂度

• 最好时间复杂度：O(n)
• 最坏时间复杂度：O(nlogn)
• 平均时间复杂度：O(nlogn)

4.2 空间复杂度

• 空间复杂度：O(1)
• 原地算法

4.3 稳定性

• 不稳定排序算法

总结

• 基于堆实现的排序算法
• 利用堆顶的有序性（最大值或最小值）来实现对数组的排序
• 优缺点
  • 优点：唯一能够同时最优地利用空间和时间的排序算法
  • 缺点：很少和相邻元素比较，导致无法利用缓存
• 堆排序步骤
  • 构建堆：将数组构建成堆
  • 堆排序：一直移除堆顶元素，直到堆为空为止

参考

《算法（第4版）》

https://juejin.cn/post/7119807721766912030

附录

/**
 * 堆排序
 *
 * @author weijiaduo
 * @since 2023/2/26
 */
public class HeapSort implements Sort {

    @Override
    public void sort(int[] arr) {
        // 建堆
        int n = arr.length;
        for (int i = (n - 1) / 2; i >= 0; i--) {
            sink(arr, i, n);
        }

        // 排序
        for (int i = n; i > 0; i--) {
            swap(arr, 0, i - 1);
            sink(arr, 0, i - 1);
        }
    }

    /**
     * 下沉
     *
     * @param arr 数组
     * @param i   当前索引 i
     * @param n   数组长度
     */
    private void sink(int[] arr, int i, int n) {
        while (i < n - 1) {
            int m = i;
            // 左子节点
            int l = 2 * i + 1;
            if (l < n && arr[l] > arr[m]) {
                m = l;
            }
            // 右子节点
            int r = 2 * i + 2;
            if (r < n && arr[r] > arr[m]) {
                m = r;
            }
            if (m == i) {
                break;
            }
            swap(arr, i, m);
            i = m;
        }
    }

}