您现在的位置是：网站首页>技术百科技术百科

排序算法之堆排序（Heap Sort）

小大寒2024-01-01[技术百科]博学多闻

排序算法之堆排序（Heap Sort）堆排序（Heap Sort）是一种基于完全二叉堆的数据结构实现的比较排序算法。它利用堆的性质快速找出最大值（或最小值），通过不断调整堆来完成排序。堆排序具有原地排序的特性，时间复杂度为O(n log n)，适合对大数据进行排序。

排序算法之堆排序（Heap Sort）

1. 基础概念

1.1 堆排序的定义

堆排序是一种利用堆这种树形数据结构进行排序的算法。它将数组视为完全二叉树，并通过调整堆的性质来实现排序。堆分为最大堆和最小堆：
- 最大堆：每个节点的值都大于或等于其子节点的值。
- 最小堆：每个节点的值都小于或等于其子节点的值。
堆排序通常使用最大堆来实现升序排序，或最小堆来实现降序排序。

1.2 堆排序的特点

时间复杂度为O(n log n)，性能稳定。
原地排序，无需额外的存储空间（空间复杂度为O(1)）。
不稳定排序算法（交换过程可能改变元素的相对顺序）。

1.3 使用场景

堆排序适用于以下场景：
- 需要高效处理大规模数据的排序问题。
- 需要动态维护最大或最小值的应用，例如优先队列和Top-K问题。

2. 实现与操作

2.1 核心操作实现

以下是堆排序的完整C语言实现，包括构建堆、调整堆以及排序主逻辑。

#include <stdio.h>

// 交换两个元素的值
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆：保持最大堆的性质
void heapify(int arr[], int n, int i) {
    int largest = i;          // 当前节点为最大值
    int left = 2 * i + 1;     // 左子节点索引
    int right = 2 * i + 2;    // 右子节点索引

    // 如果左子节点大于当前最大值
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大值不是当前节点，交换并递归调整
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        heapify(arr, n, largest);
    }
}

// 堆排序主函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // 依次从堆顶取出最大值，调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);   // 将堆顶（最大值）移到数组末尾
        heapify(arr, i, 0);       // 调整剩余堆
    }
}

// 测试代码
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    heapSort(arr, n);

    printf("排序后的数组:\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
    </stdio.h>

2.2 代码详解

代码主要分为以下几个部分：

swap函数：用于交换两个元素的值。
heapify函数：调整堆的性质，确保以某个节点为根的子树满足最大堆要求。
heapSort函数：构建最大堆，并通过迭代将堆顶元素移到数组末尾完成排序。

3. 时间与空间复杂度分析

3.1 时间复杂度

构建堆：O(n)。
调整堆：每次调整为O(log n)，共进行n次调整，总复杂度为O(n log n)。
总时间复杂度：O(n log n)。

3.2 空间复杂度

堆排序在原数组上进行操作，不需要额外的存储空间，空间复杂度为O(1)。

4. 优缺点与局限性

4.1 优点

时间复杂度稳定为O(n log n)。
不需要额外存储空间，节省内存。
适合大规模数据的排序。

4.2 缺点与局限性

不稳定排序，可能改变相同元素的相对顺序。
对于小规模数据，性能可能不如插入排序。

5. 常见应用场景

5.1 实际应用示例

以下代码展示如何用堆排序解决Top-K问题（求数组中最大的K个数）。

#include <stdio.h>

void topK(int arr[], int n, int k) {
    // 构建前K个元素的最小堆
    for (int i = k / 2 - 1; i >= 0; i--) {
        heapify(arr, k, i);
    }

    // 遍历剩余元素，维护堆
    for (int i = k; i < n; i++) {
        if (arr[i] > arr[0]) { // 如果当前元素大于堆顶
            arr[0] = arr[i];   // 替换堆顶
            heapify(arr, k, 0); // 调整堆
        }
    }

    // 输出Top-K
    printf("Top-%d元素:\n", k);
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
    </stdio.h>