堆排序

数据结构

堆

堆的定义如下：

  1. 堆是一颗完全二叉树；
  2. 堆中的某个节点的值总是不大于或不小于其孩子节点的值；
  3. 堆中每个节点的子堆都是堆；

当父节点的键值总是大于或者等于任何一个子节点的键值时为最大堆。当父节点的键值总是小于或者等于任何一个子节点的键值时未最小堆。如下图所示，左边为最大堆，右边为最小堆。

heap.jpg

算法思想

首先把有n个元素的数组a初始化创建为最大堆，然后循环执行如下过程直到数组为空为止：

  1. 把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换；
  2. 最大堆元素个数减一；
  3. 由于第一步后根结点不再满足最大堆的定义，因此调整根结点使之满足最大堆的定义；
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
void CreateHeap(int a[], int n, int h) {
/* 当完全二叉树中某个非叶结点a[h]（h = (n - 2)/2）的左孩子结点a[2h + 1]和右孩子结点a[2h + 2]都已是最大堆后，调整一个非叶结点a[h]使之满足最大堆。 */
    int i, j, flag;
    int temp;
    /* i为要建堆的二叉树根结点下标 */
    i = h;
    /* j为i的左孩子结点的下标 */
    j = 2 * i + 1;
    temp = a[i];
    flag = 0;
    /* 沿左右孩子中值较大者重复向下筛选 */
    while (j < n && flag != 1) {
        /* 寻找左右孩子结点中较大者， */
        if (j < n - 1 && a[j] < a[j + 1])
            j++;
        if (temp > a[i]) {
            flag = 1;
        /* 否则把a[j]上移 */
        } else {
            a[i] = a[j];
            i = j;
            j = 2 * i + 1;
        }
    }
    a[i] = temp;
}
1
2
3
4
5
6
void InitCreateHeap(int a[], int n) {
    /* 把数组元素a[0]~a[n - 1]初始化创建为最大堆 */
    int i;
    for (i = (n - 2)/2; i >= 0; i--)
        CreateHeap(a, n, i);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void HeapSort(int a[], int n) {
    int i;
    int temp;
    /* 初始化创建最大堆 */
    InitCreateHeap(a, n);
    /* 当前最大堆个数每次递减一 */
    for (i = n - 1; i > 0; i--) {
        temp = a[0];
        a[0] = a[i];
        a[i] = temp;
        /* 调整根结点满足最大堆 */
        /* 子二叉树的根结点下标为零，结点个数为i */
        CreateHeap(a, i, 0);
    }
}
|