C语言数据结构之堆排序的优化算法

C语言数据结构之堆排序的优化算法攻略

堆排序简介

堆排序（HeapSort）是一种树形选择排序，在排序过程中始终保持一个最大堆，每次将堆顶元素与最后一个元素交换位置，并进行一次最大堆调整操作，直到整个序列有序为止。

堆排序的时间复杂度为O(nlogn)，具有不需额外存储空间的特点，因此广泛应用于内存受限的场景。

堆排序的优化算法

1. 建堆操作的优化

将序列中的元素插入到空堆中，时间复杂度为O(nlogn)，可以通过优化建堆操作，将其时间复杂度降至O(n)。

建堆操作的本质是将序列中的元素依次插入到堆中，因此可以考虑一次性将序列中的所有元素插入到堆中。具体方法如下：

void buildHeap(int a[], int n) {
    int i;
    for (i = n / 2; i >= 1; i--) {
        heapify(a, i, n);
    }
}

由于完全二叉树中叶子节点占据了一半的空间，因此从第n/2个节点开始（包括第n/2个节点）是堆中所有非叶子节点。从第n/2个节点开始，从后往前依次执行heapify操作，即每次将当前节点和其子节点进行比较并进行调整。由于叶子节点不需要调整，因此可以忽略叶子节点，将操作次数降至一半。

2. 堆调整操作的优化

堆调整操作的本质是将某个节点的值减小，从而可能影响到该节点的子节点，需要依次将该节点与其子节点进行比较，对不满足堆性质的节点进行调整。由于每次调整只是将节点移动到正确的位置，因此可以考虑将堆调整操作优化为插入操作。

具体方法如下：

void heapInsert(int a[], int n, int k) {
    int cur = n;
    a[cur] = k;
    while (cur > 1 && k > a[cur / 2]) {
        a[cur] = a[cur / 2];
        cur /= 2;
    }
    a[cur] = k;
}

每次将堆的最后一个元素插入到堆中，由于插入元素的大小可能会影响到堆的调整，因此需要按照子节点的大小依次将该元素与其父节点进行比较。如果插入元素比父节点大，则将父节点移动到当前位置，并将当前位置改为父节点，继续向上比较。最后将插入元素插入到正确的位置。

示例1

#include <stdio.h>

void heapify(int a[], int i, int n) {
    int max = i, l = 2 * i, r = l + 1;
    if (l <= n && a[l] > a[max]) {
        max = l;
    }
    if (r <= n && a[r] > a[max]) {
        max = r;
    }
    if (max != i) {
        int temp = a[i];
        a[i] = a[max];
        a[max] = temp;
        heapify(a, max, n);
    }
}

void heapSort(int a[], int n) {
    int i;
    for (i = n / 2; i >= 1; i--) {
        heapify(a, i, n);
    }
    for (i = n; i > 1; i--) {
        int temp = a[1];
        a[1] = a[i];
        a[i] = temp;
        heapify(a, 1, i - 1);
    }
}

int main() {
    int a[] = {0, 5, 2, 4, 1, 3};
    int n = sizeof(a) / sizeof(int) - 1;
    heapSort(a, n);
    int i;
    for (i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

1 2 3 4 5

示例2

#include <stdio.h>

void heapInsert(int a[], int n, int k) {
    int cur = n;
    a[cur] = k;
    while (cur > 1 && k > a[cur / 2]) {
        a[cur] = a[cur / 2];
        cur /= 2;
    }
    a[cur] = k;
}

int main() {
    int a[10] = {0};
    int n = 0;
    heapInsert(a, ++n, 5);
    heapInsert(a, ++n, 1);
    heapInsert(a, ++n, 4);
    heapInsert(a, ++n, 2);
    heapInsert(a, ++n, 3);
    int i;
    for (i = 1; i <= n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

5 3 4 1 2