一文带你读懂排序算法（三）：堆排序算法

堆是一种特殊的树形数据结构，其每一个结点都有一个值，通常提到的堆都是指一棵完全二叉树，根结点的值小于（或大于）两个子结点的值，同时，根结点的两个子树也分别是一个堆。

堆排序是什么

堆排序是一个树形选择排序，在排序过程中，将 R[1···n]看作一棵完全二叉树的顺序存储结构，利用完全二叉树中父节点和子结点之间的内在关系来选择最小的元素。

堆一般分为大顶堆和小顶堆两种不同的类型。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。对于给定n个记录的序列（r(1),r(2),···r(n)），当且仅当满足条件。

二叉树是什么

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。

性质

1、具有n个结点的完全二叉树的深度

（注：[ ]表示向下取整）

2、如果对一棵有n个结点的完全二叉树的结点按层序编号, 则对任一结点i (1≤i≤n) 有：

• 如果i=1, 则结点i是二叉树的根, 无双亲
• 如果i>1, 则其双亲parent (i) 是结点[i/2]
• 如果2i>n, 则结点i无左孩子, 否则其左孩子lchild (i) 是结点2i
• 如果2i+1>n, 则结点i无右孩子, 否则其右孩子rchild (i) 是结点2i+1

特点

完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。

满二叉树

一棵深度为k且有

个结点的二叉树称为满二叉树。

根据二叉树的性质2, 满二叉树每一层的结点个数都达到了最大值, 即满二叉树的第i层上有 个结点 (i≥1)。

如果对满二叉树的结点进行编号, 约定编号从根结点起, 自上而下, 自左而右。则深度为k的, 有n个结点的二叉树, 当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时, 称之为完全二叉树。

从满二叉树和完全二叉树的定义可以看出, 满二叉树是完全二叉树的特殊形态, 即如果一棵二叉树是满二叉树, 则它必定是完全二叉树。

完全二叉树判定

算法思路：判断一棵树是否是完全二叉树的思路

• 如果树为空，则直接返回错
• 如果树不为空：层序遍历二叉树
• 如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；
• 如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树
• 如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点

堆算法图解

堆排序的过程包括两个：

• 一是构建堆。建堆的核心内容是调整堆，使二叉树满足堆的定义（每个节点的值都不大于其父节点的值）
• 二是交换对顶元素与最后一个元素位置（调堆的过程应该从最后一个非叶子节点开始）

下面举个例子，我们拥有一个完全二叉树：[4,6,8,5,9]，我们将如何通过堆排序完成对这个二叉树的排序呢？

• 给定无序序列结构如下

• 步骤一：构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。从最后一个非叶子结点开始，从左至右，从下至上进行调整。
• 第一自然是[6,5,9]这个子树了，我们的目标是，将其满足大顶堆的条件：根结点比子结点要大，操作对象自然是把元素9 跟元素6 交换位置。

• 找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换

• 交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6，此时，我们就将一个无需序列构造成了一个大顶堆。

• 步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
• a.交换：将堆顶元素9和末尾元素4进行交换

• b.调整：重新调整结构，使其继续满足堆定义

如何调整呢？我们步骤一进行的操作就是，针对非叶子结点，从左往右，从下到上，开始进行调整。
- 因为[6,5,9]，元素9 是经过排序的叶子结点，按照规则忽略掉，因此[6,5]是满足了大顶堆的条件了。
- [4,6,8]，元素8 子结点比元素4要大，因此需要交换彼此的位置。

• c.交换：将堆顶元素8与当前末尾元素5进行交换，得到第二大元素8成为了倒数第二个元素。

• d.调整：第二次的堆顶元素与末尾元素交换，导致了堆结构的混乱，因此要进行调整。

[5,6,4] 的元素5 与元素6 进行交换

• e.交换：根结点与最后叶子结点进行交换，将对顶元素6，沉入到最末队列元素4 的位置。

• f.调整堆结构，满足对顶元素比左右子结点都要大（大顶堆）

[4,5] 调整为 [5,4]

• g.交换：根结点与最后叶子结点进行交换，将对顶元素5，沉入到最末队列元素4 的位置。最终使得整个序列有序。

• 至此，我们得到最终的按照大顶堆排序算法的执行结果：[4,5,6,8,9]

堆算法实现

下面是代码例子：

public class HeapSort {
  public static void main(String[] args) {
    int i = 0;
    int a[] = {5,4,9,8,7,6,0,1,3,2};
    int len = a.length;
    myMinHeapSort(a);
    System.out.println(Arrays.toString(a));

  }

  private static void myMinHeapSort(int[] array){
    int i;
    int len = array.length;
    for (i = len/2-1; i>=0; i--){
      adjustMinHeap(array, i, len-1);
    }
    for (i = len -1; i>=0; i--){
      int tmp = array[0];
      array[0] = array[i];
      array[i] = tmp;
      adjustMinHeap(array, 0, i-1);
    }
  }

  private static void adjustMinHeap(int[] array, int pos, int len) {
    int temp = 0;
    int child = 0;
    for (temp = array[pos]; 2 * pos + 1 <= len; pos = child){
      child = 2 * pos + 1;
      if (child < len && array[child] <= array[child+1]){
        child++;
      }
      if (array[child] < temp){
        array[pos] = array[child];
      } else {
        break;
      }
    }
    array[pos] = temp;
  }
}

输出结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

复杂度分析

总结

堆排序方法对记录较少的文件效果一般，但对于记录较多的文件还是很有效的，其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏情况下，其时间复杂度也有Ο(nlog(n))。

—END—