C语言数据结构之堆、堆排序的分析及实现

什么是堆

堆（Heap）是一种特殊的树形数据结构，它满足两个条件：

1. 堆是一棵完全二叉树；
2. 堆中任意节点的值总是不大于/不小于其子节点的值。

如果父节点的值不大于所有子节点的值，此堆称为小根堆，又称为最小堆。如果父节点的值不小于所有子节点的值，此堆称为大根堆，又称为最大堆。

堆通常可以使用数组来实现，具体实现方法是将堆的元素依次存入数组中，对于任意下标为i的节点，它的左儿子的下标为2i+1，右儿子的下标为2i+2，它的父节点的下标为(i-1)/2。

堆排序的基本思想

堆排序是一种利用堆的数据结构对数组中的元素进行排序的算法。它的基本思路如下：

1. 先把要排序的数组构建成一个大根堆（或小根堆）；
2. 取出堆顶的元素，将其和末尾元素交换；
3. 缩小范围：把数组范围缩小至之前的数组长度-1，并且刚才被调换到了最后面的那个元素不再参与调整堆的过程；
4. 重新调整堆（依次下沉）；
5. 循环执行第2到第4步，直到整个数组排好序为止。

堆排序的实现步骤

1. 构建堆

构建堆的过程是将一个数组调整为一个大根堆或小根堆的过程。我们以构建大根堆为例，构建小根堆只需要把「a[i] < a[lchild(i)]」改为「a[i] > a[lchild(i)]」即可。

void heapify(int a[], int n, int i) {
    int largest = i; // 初始化最大元素为当前节点
    int l = 2 * i + 1; // 左子节点
    int r = 2 * i + 2; // 右子节点

    // 如果左子节点比当前节点大，则更新最大元素
    if (l < n && a[l] > a[largest]) {
        largest = l;
    }

    // 如果右子节点比当前节点大，则更新最大元素
    if (r < n && a[r] > a[largest]) {
        largest = r;
    }

    // 如果最大元素不是当前节点，则交换之后再递归调整堆
    if (largest != i) {
        swap(&a[i], &a[largest]);
        heapify(a, n, largest);
    }
}

2. 堆排序

在构建好一个大根堆或小根堆之后，我们就可以把堆首（最大或最小元素）和堆尾调换。然后重新调整堆，再次得到一个大根堆或小根堆，然后再把堆首和堆尾交换，这样循环下去就可以得到一个有序的序列了。

void heapSort(int a[], int n) {
    // 构建大根堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(a, n, i);
    }

    // 交换堆顶元素和堆尾元素，然后重新调整堆
    for (int i = n - 1; i >= 0; i--) {
        swap(&a[0], &a[i]);
        heapify(a, i, 0);
    }
}

示例说明

示例1：从小到大排序

我们来看一下一个从小到大排序的示例：

int a[] = {5,2,9,4,7,6,1,3,8};
int n = sizeof(a)/sizeof(a[0]);

heapSort(a, n); // 排序

for (int i = 0; i < n; i++) {
    printf("%d ", a[i]); // 输出结果：1 2 3 4 5 6 7 8 9
}

示例2：从大到小排序

如果要从大到小排序，只需要将堆的排序顺序改为小根堆即可：

void heapify(int a[], int n, int i) {
    int smallest = i; // 初始化最小元素为当前节点
    int l = 2 * i + 1; // 左子节点
    int r = 2 * i + 2; // 右子节点

    // 如果左子节点比当前节点小，则更新最小元素
    if (l < n && a[l] < a[smallest]) {
        smallest = l;
    }

    // 如果右子节点比当前节点小，则更新最小元素
    if (r < n && a[r] < a[smallest]) {
        smallest = r;
    }

    // 如果最小元素不是当前节点，则交换之后再递归调整堆
    if (smallest != i) {
        swap(&a[i], &a[smallest]);
        heapify(a, n, smallest);
    }
}

void heapSort(int a[], int n) {
    // 构建小根堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(a, n, i);
    }

    // 交换堆顶元素和堆尾元素，然后重新调整堆
    for (int i = n - 1; i >= 0; i--) {
        swap(&a[0], &a[i]);
        heapify(a, i, 0);
    }
}

int a[] = {5,2,9,4,7,6,1,3,8};
int n = sizeof(a)/sizeof(a[0]);

heapSort(a, n); // 排序

for (int i = 0; i < n; i++) {
    printf("%d ", a[i]); // 输出结果：9 8 7 6 5 4 3 2 1
}

以上就是关于堆（Heap）和堆排序（Heap Sort）的具体分析及实现步骤，以及两个排序示例讲解。