堆排序

发表于 | 分类于 |

1. 算法原理

1.1 什么是堆？

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

如下图，是一个堆和数组的相互关系

heap-and-array.png

  • 对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标：
    • Parent(i) = floor(i/2)，i 的父节点下标
    • Left(i) = 2i，i 的左子节点下标
    • Right(i) = 2i + 1，i 的右子节点下标
  • 二叉堆一般分为两种：最大堆和最小堆。
  1. 最大堆：
  • 最大堆中的最大元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都大于等于其孩子结点（如果存在）
  1. 最小堆：
  • 最小堆中的最小元素值出现在根结点（堆顶）
  • 堆中每个父节点的元素值都小于等于其孩子结点（如果存在）

1.2 堆排序原理

堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：

  • 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆
  • 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变

zero-based.png

相应的，几个计算公式也要作出相应调整：

  • Parent(i) = floor((i-1)/2)，i 的父节点下标
  • Left(i) = 2i + 1，i 的左子节点下标
  • Right(i) = 2(i + 1)，i 的右子节点下标

1.2.1 最大堆调整（Max-Heapify）

最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：

max-heapify.png

由于一次调整后，堆仍然违反堆性质，所以需要递归的测试，使得整个堆都满足堆性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 从 index 开始检查并保持最大堆性质
 * @param array
 * @param index
 * @param heapSize
 */
public static void maxHeapify(int[] array, int index, int heapSize) {
  int iMax = index,
    iLeft = 2 * index + 1,
    iRight = 2 * (index + 1);
  // 找出父节点和左右子节点中的最大值的下标
  if (iLeft < heapSize && array[index] < array[iLeft]) {
    iMax = iLeft;
  }
  if (iRight < heapSize && array[iMax] < array[iRight]) {
    iMax = iRight;
  }
  // 当父节点不是最大值时交换父节点和该子节点
  if (iMax != index) {
    swap(array, iMax, index);
    maxHeapify(array, iMax, heapSize); // 递归调整（交换父子节点后，可能会导致以子节点为根的子堆不是最大堆）
  }
}
public static void swap(int[] array, int i, int j) {
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

1.2.2 创建最大堆（Build-Max-Heap）

创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下：

build-max-heap.png

1.2.3 堆排序（Heap-Sort）

堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：

heap-sort.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 堆排序（Heap-Sort）是堆排序的接口算法，
 * Heap-Sort先调用Build-Max-Heap将数组改造为最大堆
 * 然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。
 * @param array
 * @param heapSize
 */
public static void heapSort(int[] array, int heapSize) {
  buildMaxHeap(array, heapSize);
  for (int i = heapSize - 1; i > 0; i--) {
    swap(array, 0, i);
    maxHeapify(array, 0, i);
  }
}

2. 算法实现

合并以上三个步骤后最终的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
 * Created by cjz on 2017/6/3.
 */
public class HeapSort {
    /**
     * 从 index 开始检查并保持最大堆性质
     * @param array
     * @param index
     * @param heapSize
     */
    public static void maxHeapify(int[] array, int index, int heapSize) {
        int iMax = index,
            iLeft = 2 * index + 1,
            iRight = 2 * (index + 1);
        // 找出父节点和左右子节点中的最大值的下标
        if (iLeft < heapSize && array[index] < array[iLeft]) {
            iMax = iLeft;
        }
        if (iRight < heapSize && array[iMax] < array[iRight]) {
            iMax = iRight;
        }
        // 当父节点不是最大值时交换父节点和该子节点
        if (iMax != index) {
            swap(array, iMax, index);
            maxHeapify(array, iMax, heapSize); // 递归调整（交换父子节点后，可能会导致以子节点为根的子堆不是最大堆）
        }
    }
    /**
     * 从原始的数组中创建最大堆
     * @param array
     * @param heapSize
     */
    public static void buildMaxHeap(int[] array, int heapSize) {
        int iParent = (heapSize - 1) / 2; // 第一个需要进行最大堆调整的节点
        for (int i = iParent; i >= 0; i--) {
            maxHeapify(array, i, heapSize);
        }
    }
    /**
     * 堆排序（Heap-Sort）是堆排序的接口算法，
     * Heap-Sort先调用Build-Max-Heap将数组改造为最大堆
     * 然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。
     * @param array
     * @param heapSize
     */
    public static void heapSort(int[] array, int heapSize) {
        buildMaxHeap(array, heapSize);
        for (int i = heapSize - 1; i > 0; i--) {
            swap(array, 0, i);
            maxHeapify(array, 0, i);
        }
    }
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static void main(String[] args) {
        int array[] = {15,6,6,10,6,5,6,3,1,6,7,6,2,8,6};
        System.out.println("排序之前：");
        for(int element : array){
            System.out.print(element+" ");
        }
        heapSort(array,array.length);
        System.out.println("\n排序之后：");
        for(int element : array){
            System.out.print(element+" ");
        }
    }
}