感谢参考文章博主：https://blog.csdn.net/qq_36186690/article/details/82505569
对算法复杂度数量级的详细说明：https://blog.csdn.net/qq_25800311/article/details/82345252

一、排序算法复杂度

各种排序算法的时间复杂度统计（图片来自网络）：

• 如果题目明确要求时间复杂度优于nlogn，常用方法中我们可以堆排序或归并排序。
• 如果题目中由要求出topk，可以选择堆排序，保证时间复杂度nlogn同时节省内存空间。

堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

以大顶堆为例，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

此处我们再来回忆一下用数组结构存储树结构（从下标0开始存储）

• 父节点i的左子节点在位置(2i);
• 父节点i的右子节点在位置(2i+1);
• 第一个叶子节点(n/2)

  二、一般堆排序算法框架

• 堆排序的基本思想*是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
  【将最大（小）值与末尾元素交换，故一般升序采用大顶堆，降序采用小顶堆】

  Step 1: 构建初始堆

  据升序降序需求选择大顶堆或小顶堆。从最后一个非叶子结点开始，从左至右，从下至上进行调整。

     //建立初始大顶堆
    for(i = n/2-1; i>=0; i--){ //从第一个非叶子节点从下往上开始调整
         adjustHeap(arr, i, n);
     }

  Step 2: 堆顶元素换至末尾，然后继续调整堆。

  for(i = n-1; i>0; i--){
     swap(arr, 0, i);
     adjustHeap(arr, 0, i);
    }

  堆的调整过程

  给定初始无序序列自然形成的“堆”结构如下图所示：
  

从最后一个非叶子结点（6）开始向下调整

代码1：堆排序模板

class Solution {
    //因为有k的限制，这两道题的堆处理都可以优化
    public int[] smallestK(int[] arr, int k) {
        int i, j, n = arr.length;
        //建立初始大顶堆
        for(i = n/2-1; i>=0; i--){ //从第一个非叶子节点从下往上开始调整
            adjustHeap(arr, i, n);
        }
        for(i = n-1; i>0; i--){
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
        }
        return arr;
    }
    public void adjustHeap(int[] arr, int i, int n){
        int temp = arr[i];
        for(int k = i*2+1; k<n; k=k*2+1){
            if(k+1<n && arr[k]<arr[k+1]){
                k++; //k指向右子节点
            }
            if(arr[k]>temp){
                arr[i] = arr[k];
                i = k;
            } else{
                break;
            }
        }
        arr[i] = temp;
    }
    public static void swap(int []arr, int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

三、用优先队列实现堆