Chapter3: 更好的查找与排序算法

11. 堆的概念及堆排序

[1] 图解排序算法(三)之堆排序 讲得很好，这里相当于写个精简大纲版并将java代码转换为C++代码

堆的相关概念

堆排序概述

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆的概念

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

大顶堆和小顶堆图片示意

前面说了树是一种逻辑结构，可以用数组来存储，堆是一种特殊的树，自然也可以，如上面的大顶堆结点按照从上到下从左到右标号，然后存储到数组。

将这种逻辑结构映射到数组中就是下面这个样子：

image

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

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

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

堆排序的基本思想和步骤

堆排序的基本思想是：

1. 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

2. 将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

3. 重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

堆排序代码实现

代码思想

0. 初始化条件

一个数组，可以认为它的逻辑结构是堆，编号从上到下从左到右，从0开始

1. 构建大顶堆

调整堆使得对于整棵树及所有子树都是父元素最大，其实就是

• 从倒数第一个非叶子结点开始，从下到上，从右到左遍历调整结构 for(int i=arrLen/2-1;i>=0;i--)

  叶子结点没有左右子树，所以无论是大顶堆还是小顶堆都可以可以认为它们满足条件

  从下到上从右到左是堆的存储结构-数组的逆序

  关于最后一个非叶子结点的下标：

  完全二叉树中 n0=n2+1 (度为0的结点数=度为2的结点数+1)，如果完全二叉树中结点总数为奇数，则没有度为1的结点，如果结点总数为偶数，则有1个度为1的结点。而 n=n0+n1+n2 ，所以 n2=(n-n1-1)/2 , n2+n1=(n+n1-1)/2 ,如果结点总数是奇数，n1=0 ,非叶子结点数为 (n-1)/2, 考虑到计算机中的除法是向下取整的，所以对于奇数n而言，n/2==(n-1)/2，所以最后一个非叶子结点下标为 n/2-1 , 如果结点总数是偶数, n1=1 ,最后一个非叶子结点下标也是 n/2-1

  还有1个注意点就是：
  当数组下标从0开始时和从1开始时，树中父子结点的关系式是不一样的；n从0开始，左孩子结点和父结点的关系为 k=2*i+1 ,当n从1开始时，左孩子结点和父结点的关系为 k= i * 2;

• 对遍历到的每个元素调用调整堆结构的函数 adjustHeap(arr,i,arrLen);，即一次循环中调整以结点 i 作为根结点的子树(包括其所有子孙结点)使之满足堆的定义

2. 循环交换堆顶元素到数组末尾 & 调整堆结构

• 交换堆顶元素(最大值)与最后1个元素
• 调换元素后这棵树会不满足堆的定义，需要调整，此时调用堆调整函数 adjustHeap(arr,i,arrLen) 即可，i固定为0，arrLen每次调换后要-1。 即每次调换后都要对整棵树的进行堆结构调整(不包括已排序的元素)
• 循环进行上面两小步，将数组所有元素排好序 for(int j=arrLen-1;j>0;j--)

3.堆结构调整函数 adjustHeap(int* arr,int i,int arrLen)

• 函数参数分别为输入数组，要调整的结点，数组长度(用来确定边界)
• 函数功能为针对输入结点 i，调整以它作为根结点的子树使得满足堆的定义，如果 i=0 那就是对整棵树进行调整

代码

/*堆排序*/ 
void heapSort(int* arr,int arrLen){
    //构建大顶堆
    for(int i=arrLen/2-1;i>=0;i--){
        //从第一个非叶子结点开始，从下到上，从右到左调整结构
        //因为叶子结点没有子结点，可以认为每个叶子结点单独作为一棵子树已经是大顶堆/小顶堆 
        adjustHeap(arr,i,arrLen); 
    }
    //循环 交换堆顶元素到数组末尾 & 调整堆结构   
    for(int j=arrLen-1;j>0;j--){
        swap(arr,0,j);//将堆顶元素arr[0]与末尾元素arr[j]互换 
        adjustHeap(arr,0,j); //调整数组第一个元素到最后一个未排序元素(j的前一个元素)之间的堆 
    }
}

/*调整大顶堆(仅是调整过程，建立在大顶堆已构建的基础上)*/ 
void adjustHeap(int* arr,int i,int arrLen){
    int tmp=arr[i];//保存当前元素i
    for(int k=i*2+1;k<arrLen;k=k*2+1){//遍历左子树,下面第一个if判断会在合适的时候拐弯,注意当下标从1开始时，父子结点的关系式和下标从0开始时的关系式是不一样的 
        if(k+1<arrLen && arr[k]<arr[k+1]){//k的含义是上一个k的左结点，k>arrLen时,说明已经超越了树的范围，不存在这个结点；k+1=arrLen时,k为最左边的叶子结点，其右兄弟为已排序元素 & 左子结点小于右子结点 
            k++;//k指向右子结点 
        }
        if(arr[k]>tmp){//如果子结点大于父结点，注意这里是用arr[k]与tmp比较而不是arr[i]，这就是下面只需要将子结点的值赋值给父结点，而不需要将父结点的值赋值给左结点的原因，父结点的值一直保存在tmp中，直到遍历到底层后(不会也不需遍历所有元素，只走不满足条件需要调整的路线)才将tmp的值赋给合适的元素 
            arr[i]=arr[k];//将子节点值赋给父结点(不用交换,在循环结束后直接赋值)
            i=k; //将父元素指针移向它的左子树 
        }
        /*下面这个if判断可以取代上面的if判断，不需要tmp了*/ 
//      if(arr[k]>arr[i]){
//          swap(arr,i,k);
//          i=k;
//      }
//      else//不进行调换
//          break;   
    }
    arr[i]=tmp;//将tmp放到最终的位置    
}

/*交换元素*/ 
void swap(int* arr,int a,int b){
    int tmp=arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
}

时间复杂度分析

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为 O(n)，在交换并重建堆的过程中，需交换 n-1 次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1] 逐步递减，近似为 nlogn 。所以堆排序时间复杂度一般认为就是 O(nlogn) 级。

参考链接

[1] 图解排序算法(三)之堆排序