堆是一种能方便解决 top 问题的树形数据结构，利用这个性质也可以用来解决排序问题。首先生成最大堆，然后逆序遍历该数组，过程中通过比较堆的最大值。如果小于，就放到数组的最后一个，并且调整堆。所以在堆排序中，如何构建堆和调整堆成为了问题的关键。
最简单，有效的做法就是用一个一位数组来表示堆。比如一颗二叉树可以用数组来表示：

1
2
3
4
5
6
[9, 4, 7, 3, 1, 2]
     9
    / \
   4   7
  / \  /  
 3   1 2

在一位数组表示法中，比如 root 节点 9 的下标是 0，它的两个子节点下标分别是 1，2 … 通过不断比较可以发现规律。下标为 n 的树的节点，两个子节点的下标分别是 2 * n + 1, 2 * n + 2; 同样的，如果一个节点下标是 m，对应的父节点的下标是 (m - 1) / 2。那么当给一个转换成二叉树的数组

1
2
3
4
5
6
[3, 1, 2, 5, 6]
     3
    / \
   1   2
  / \     
 5   6

需要通过一个方法让这个二叉树满足最大堆性质。

首先，在这个二叉树中每个节点对应的数在数组中都有对应的下标，按照上述的根节点，子节点的关系，在数组中间之后的数就不会有对应的子节点了假设数组长度是 m，那么（2 * m / 2 + 1) > m 这种情况显然不需要。也就是说目前只需要从下标为 5 / 2 = 2 的节点开始。（考虑到整数相除会有取整，因此这个地方从中间开始只是为了性能更好）。这个时候，

  • 从下标为 2 的节点 2 开始，发现没有子节点，下标减 1
  • 从下标为 1 的节点 1 开始，发现左节点更大，于是交换变成
    1
    2
    3
    4
    5
    6
    [3, 5, 2, 1, 6]
         3
        / \
       5   2
      / \     
     1   6

此时，节点 1 没有子节点，继续从下标 1 比较，发现右节点更大，于是交换变成

1
2
3
4
5
6
[3, 6, 2, 1, 5]
     3
    / \
   6   2
  / \     
 1   5

此时，节点 5 没有子节点，下标减 1

  • 从下标为 0 的节点 3 开始，发现左节点更大，于是交换变成
    1
    2
    3
    4
    5
    6
    [6, 3, 2, 1, 5]
         6 
        / \
       3   2
      / \     
     1   5

此时，节点 3 的右边节点更大，于是交换变成

1
2
3
4
5
6
[6, 5, 2, 1, 3]
     6 
    / \
   5   2
  / \     
 1   3

此时，节点 3 没有子节点，下标减 1

  • 下标目前已经小于 0 结束。

以上就是如何构建堆的过程，可以看到本质上就是利用数组中节点之前的关系，通过比较大小的方法来交换顺序。

当一个最大堆构建成功后，如何做排序呢？

在最大堆中，把 root 节点和数组中最后一个值交换。这个时候把数组分为两个区域，有序区和无序区。

1
2
3
4
5
6
[3, 5, 2, 1, 6]
     3
    / \
   5   2
  / \     
 1   6

此时认为 [6] 为有序区，[3, 5, 2, 1] 为无序区。此时可以认为堆是

1
2
3
4
5
    3
   / \
  5   2
 /      
1

这个时候继续调整成为最大堆即可。最终有序区会逐渐填满的同时，无序区会逐渐变小直到消失。这个过程可以表示为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private void buildMaxHeap(int[] arr, int end) {
  for (int i = end/2; i >= 0; --i) {
    siftDown(arr, i, end);
  }
}

private void siftDown(int[] arr, int i, int end) {
    int parent = i, child = 2 * parent + 1;
    while (child <= end) {
      if (child+1 <= end && arr[child+1] > arr[child]) ++child;
      if (arr[parent] >= arr[child]) break;
      swap(arr, parent, child);
      parent = child;
      child = 2 * parent + 1;
    }