Ref: https://pdai.tech/md/algorithm/alg-sort-x-heap.html

概览

堆分为 “最大堆” 和 “最小堆”。最大堆通常被用来进行 “升序” 排序，而最小堆通常被用来进行 “降序” 排序。

最大堆进行升序排序的基本思想:
① 初始化堆：将数列 a [1…n] 构造成最大堆。
② 交换数据：将 a [1] 和 a [n] 交换，使 a [n] 是 a [1…n] 中的最大值；然后将 a [1…n-1] 重新调整为最大堆。 接着，将 a [1] 和 a [n-1] 交换，使 a [n-1] 是 a [1…n-1] 中的最大值；然后将 a [1…n-2] 重新调整为最大值。 依次类推，直到整个数列都是有序的。

下面，通过图文来解析堆排序的实现过程。注意实现中用到了 “数组实现的二叉堆的性质”。 在第一个元素的索引为 0 的情形中：

  • 性质一：索引为 i 的左孩子的索引是 (2*i+1);
  • 性质二：索引为 i 的右孩子的索引是 (2*i+2);
  • 性质三：索引为 i 的父结点的索引是 floor ((i-1)/2);

image.png
例如，对于最大堆 {110,100,90,40,80,20,60,10,30,50,70} 而言：索引为 0 的左孩子的索引是 1；索引为 0 的右孩子是 2；索引为 8 的父节点是 3。

堆排序实现

下面演示 heap_sort_asc (a, n) 对 a={20,30,90,40,70,110,60,10,100,50,80}, n=11 进行堆排序过程。下面是数组 a 对应的初始化结构:
image.png

初始化堆

在堆排序算法中，首先要将待排序的数组转化成二叉堆。 下面演示将数组 {20,30,90,40,70,110,60,10,100,50,80} 转换为最大堆 {110,100,90,40,80,20,60,10,30,50,70} 的步骤。

  • i=11/2-1，即 i=4

image.png
上面是 maxheap_down (a, 4, 9) 调整过程。maxheap_down (a, 4, 9) 的作用是将 a [4…9] 进行下调；a [4] 的左孩子是 a [9]，右孩子是 a [10]。调整时，选择左右孩子中较大的一个 (即 a [10]) 和 a [4] 交换。

  • i=3

image.png
上面是 maxheap_down (a, 3, 9) 调整过程。maxheap_down (a, 3, 9) 的作用是将 a [3…9] 进行下调；a [3] 的左孩子是 a [7]，右孩子是 a [8]。调整时，选择左右孩子中较大的一个 (即 a [8]) 和 a [4] 交换。

  • i=2

image.png
上面是 maxheap_down (a, 2, 9) 调整过程。maxheap_down (a, 2, 9) 的作用是将 a [2…9] 进行下调；a [2] 的左孩子是 a [5]，右孩子是 a [6]。调整时，选择左右孩子中较大的一个 (即 a [5]) 和 a [2] 交换。

  • i=1

image.png
上面是 maxheap_down (a, 1, 9) 调整过程。maxheap_down (a, 1, 9) 的作用是将 a [1…9] 进行下调；a [1] 的左孩子是 a [3]，右孩子是 a [4]。调整时，选择左右孩子中较大的一个 (即 a [3]) 和 a [1] 交换。交换之后，a [3] 为 30，它比它的右孩子 a [8] 要大，接着，再将它们交换。

  • i=0

image.png
上面是 maxheap_down (a, 0, 9) 调整过程。maxheap_down (a, 0, 9) 的作用是将 a [0…9] 进行下调；a [0] 的左孩子是 a [1]，右孩子是 a [2]。调整时，选择左右孩子中较大的一个 (即 a [2]) 和 a [0] 交换。交换之后，a [2] 为 20，它比它的左右孩子要大，选择较大的孩子 (即左孩子) 和 a [2] 交换。
调整完毕，就得到了最大堆。此时，数组 {20,30,90,40,70,110,60,10,100,50,80} 也就变成了 {110,100,90,40,80,20,60,10,30,50,70}。

交换数据

在将数组转换成最大堆之后，接着要进行交换数据，从而使数组成为一个真正的有序数组。 交换数据部分相对比较简单，下面仅仅给出将最大值放在数组末尾的示意图。
image.png
上面是当 n=10 时，交换数据的示意图。 当 n=10 时，首先交换 a [0] 和 a [10]，使得 a [10] 是 a [0…10] 之间的最大值；然后，调整 a [0…9] 使它称为最大堆。交换之后: a [10] 是有序的！ 当 n=9 时， 首先交换 a [0] 和 a [9]，使得 a [9] 是 a [0…9] 之间的最大值；然后，调整 a [0…8] 使它称为最大堆。交换之后: a [9…10] 是有序的！ … 依此类推，直到 a [0…10] 是有序的。

堆排序复杂度和稳定性

堆排序时间复杂度

堆排序的时间复杂度是 O (NlgN)。
假设被排序的数列中有 N 个数。遍历一趟的时间复杂度是 O (N)，需要遍历多少次呢？ 堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是 lg (N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过 lg (2N)。因此，遍历一趟的时间复杂度是 O (N)，而遍历次数介于 lg (N+1) 和 lg (2N) 之间；因此得出它的时间复杂度是 O (NlgN)。

堆排序稳定性

堆排序是不稳定的算法，它不满足稳定算法的定义。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。
算法稳定性 — 假设在数列中存在 a [i]=a [j]，若在排序之前，a [i] 在 a [j] 前面；并且排序之后，a [i] 仍然在 a [j] 前面。则这个排序算法是稳定的！

代码实现

  1. /**
  2.  * 堆排序: Java
  3.  *
  4.  * @author skywang
  5.  * @date 2014/03/11
  6.  */
  8. public class HeapSort {
  10.     /* 
  11.      * (最大)堆的向下调整算法
  12.      *
  13.      * 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
  14.      *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
  15.      *
  16.      * 参数说明: 
  17.      *     a -- 待排序的数组
  18.      *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
  19.      *     end   -- 截至范围(一般为数组中最后一个元素的索引)
  20.      */
  21.     public static void maxHeapDown(int[] a, int start, int end) {
  22.         int c = start;            // 当前(current)节点的位置
  23.         int l = 2*c + 1;        // 左(left)孩子的位置
  24.         int tmp = a[c];            // 当前(current)节点的大小
  26.         for (; l <= end; c=l,l=2*l+1) {
  27.             // "l"是左孩子，"l+1"是右孩子
  28.             if ( l < end && a[l] < a[l+1])
  29.                 l++;        // 左右两孩子中选择较大者，即m_heap[l+1]
  30.             if (tmp >= a[l])
  31.                 break;        // 调整结束
  32.             else {            // 交换值
  33.                 a[c] = a[l];
  34.                 a[l]= tmp;
  35.             }
  36.         }
  37.     }
  39.     /*
  40.      * 堆排序(从小到大)
  41.      *
  42.      * 参数说明: 
  43.      *     a -- 待排序的数组
  44.      *     n -- 数组的长度
  45.      */
  46.     public static void heapSortAsc(int[] a, int n) {
  47.         int i,tmp;
  49.         // 从(n/2-1) --> 0逐次遍历。遍历之后，得到的数组实际上是一个(最大)二叉堆。
  50.         for (i = n / 2 - 1; i >= 0; i--)
  51.             maxHeapDown(a, i, n-1);
  53.         // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
  54.         for (i = n - 1; i > 0; i--) {
  55.             // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最大的。
  56.             tmp = a[0];
  57.             a[0] = a[i];
  58.             a[i] = tmp;
  59.             // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最大堆。
  60.             // 即，保证a[i-1]是a[0...i-1]中的最大值。
  61.             maxHeapDown(a, 0, i-1);
  62.         }
  63.     }
  65.     /* 
  66.      * (最小)堆的向下调整算法
  67.      *
  68.      * 注: 数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
  69.      *     其中，N为数组下标索引值，如数组中第1个数对应的N为0。
  70.      *
  71.      * 参数说明: 
  72.      *     a -- 待排序的数组
  73.      *     start -- 被下调节点的起始位置(一般为0，表示从第1个开始)
  74.      *     end   -- 截至范围(一般为数组中最后一个元素的索引)
  75.      */
  76.     public static void minHeapDown(int[] a, int start, int end) {
  77.         int c = start;            // 当前(current)节点的位置
  78.         int l = 2*c + 1;        // 左(left)孩子的位置
  79.         int tmp = a[c];            // 当前(current)节点的大小
  81.         for (; l <= end; c=l,l=2*l+1) {
  82.             // "l"是左孩子，"l+1"是右孩子
  83.             if ( l < end && a[l] > a[l+1])
  84.                 l++;        // 左右两孩子中选择较小者
  85.             if (tmp <= a[l])
  86.                 break;        // 调整结束
  87.             else {            // 交换值
  88.                 a[c] = a[l];
  89.                 a[l]= tmp;
  90.             }
  91.         }
  92.     }
  94.     /*
  95.      * 堆排序(从大到小)
  96.      *
  97.      * 参数说明: 
  98.      *     a -- 待排序的数组
  99.      *     n -- 数组的长度
  100.      */
  101.     public static void heapSortDesc(int[] a, int n) {
  102.         int i,tmp;
  104.         // 从(n/2-1) --> 0逐次遍历每。遍历之后，得到的数组实际上是一个最小堆。
  105.         for (i = n / 2 - 1; i >= 0; i--)
  106.             minHeapDown(a, i, n-1);
  108.         // 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
  109.         for (i = n - 1; i > 0; i--) {
  110.             // 交换a[0]和a[i]。交换后，a[i]是a[0...i]中最小的。
  111.             tmp = a[0];
  112.             a[0] = a[i];
  113.             a[i] = tmp;
  114.             // 调整a[0...i-1]，使得a[0...i-1]仍然是一个最小堆。
  115.             // 即，保证a[i-1]是a[0...i-1]中的最小值。
  116.             minHeapDown(a, 0, i-1);
  117.         }
  118.     }
  120.     public static void main(String[] args) {
  121.         int i;
  122.         int a[] = {20,30,90,40,70,110,60,10,100,50,80};
  124.         System.out.printf("before sort:");
  125.         for (i=0; i<a.length; i++)
  126.             System.out.printf("%d ", a[i]);
  127.         System.out.printf("\n");
  129.         heapSortAsc(a, a.length);            // 升序排列
  130.         //heapSortDesc(a, a.length);        // 降序排列
  132.         System.out.printf("after  sort:");
  133.         for (i=0; i<a.length; i++)
  134.             System.out.printf("%d ", a[i]);
  135.         System.out.printf("\n");
  136.     }
  137. }