堆排序算法详解：利用堆数据结构的高效排序

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一种近似完全二叉树的结构，同时满足堆的性质：父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

1. 算法原理

1.1 基本思想

堆排序的核心思想：

1. 构建最大堆：将待排序数组构造成最大堆
2. 提取最大值：将堆顶（最大值）与堆尾交换
3. 重新调整：调整剩余元素重新构成最大堆
4. 重复过程：重复步骤2-3，直到排序完成

1.2 堆的基本概念

最大堆示例：
       50
      /  \
     30   40
    / \   / \
   10 20 35 25

特点：父节点 ≥ 子节点

数组表示：[50, 30, 40, 10, 20, 35, 25]
索引关系：
- 父节点: (i-1)/2
- 左子节点: 2*i+1  
- 右子节点: 2*i+2

2. C语言实现

2.1 基础版本

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.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;        // 初始化largest为根节点
    int left = 2 * i + 1;   // 左子节点
    int right = 2 * i + 2;  // 右子节点
    
    printf("  调整节点 %d (值=%d)\n", i, arr[i]);
    
    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 如果最大值不是根节点
    if (largest != i) {
        printf("  交换 %d 和 %d (值: %d <-> %d)\n", 
               i, largest, arr[i], arr[largest]);
        swap(&arr[i], &arr[largest]);
        
        // 递归调整被影响的子树
        heapify(arr, n, largest);
    }
}

// 构建最大堆
void build_max_heap(int arr[], int n) {
    printf("构建最大堆:\n");
    
    // 从最后一个非叶子节点开始向上调整
    for (int i = n / 2 - 1; i >= 0; i--) {
        printf("调整子树，根节点索引: %d\n", i);
        heapify(arr, n, i);
        
        printf("当前堆状态: ");
        for (int j = 0; j < n; j++) {
            printf("%d ", arr[j]);
        }
        printf("\n\n");
    }
}

// 堆排序主函数
void heap_sort_basic(int arr[], int n) {
    printf("开始堆排序...\n\n");
    
    // 步骤1: 构建最大堆
    build_max_heap(arr, n);
    
    printf("最大堆构建完成: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    // 步骤2: 逐个提取最大元素
    for (int i = n - 1; i > 0; i--) {
        printf("第 %d 轮排序:\n", n - i);
        
        // 将当前最大元素（堆顶）移到数组末尾
        printf("  将最大值 %d 移到位置 %d\n", arr[0], i);
        swap(&arr[0], &arr[i]);
        
        // 重新调整堆（堆大小减1）
        printf("  重新调整堆 (大小=%d)\n", i);
        heapify(arr, i, 0);
        
        printf("  当前状态: ");
        for (int j = 0; j < n; j++) {
            if (j >= i) {
                printf("[%d] ", arr[j]);  // 已排序部分
            } else {
                printf("%d ", arr[j]);    // 堆部分
            }
        }
        printf("\n\n");
    }
}

// 测试基础堆排序
void test_basic_heap_sort() {
    printf("=== 基础堆排序测试 ===\n");
    
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
    
    heap_sort_basic(arr, n);
    
    printf("最终结果: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n\n");
}

2.2 优化版本

// 优化的堆调整（减少递归）
void heapify_iterative(int arr[], int n, int i) {
    while (true) {
        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) {
            break;  // 堆性质已满足
        }
        
        swap(&arr[i], &arr[largest]);
        i = largest;  // 继续向下调整
    }
}

// 自底向上构建堆（Floyd算法）
void build_heap_floyd(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify_iterative(arr, n, i);
    }
}

// 优化的堆排序
void heap_sort_optimized(int arr[], int n) {
    build_heap_floyd(arr, n);
    
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        heapify_iterative(arr, i, 0);
    }
}

// 堆的插入操作
void heap_insert(int heap[], int* size, int value) {
    // 在堆末尾插入新元素
    heap[*size] = value;
    int i = *size;
    (*size)++;
    
    // 向上调整
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[parent] >= heap[i]) {
            break;
        }
        swap(&heap[parent], &heap[i]);
        i = parent;
    }
}

// 堆的删除操作（删除最大值）
int heap_extract_max(int heap[], int* size) {
    if (*size <= 0) return -1;
    
    int max_value = heap[0];
    heap[0] = heap[*size - 1];
    (*size)--;
    
    if (*size > 0) {
        heapify_iterative(heap, *size, 0);
    }
    
    return max_value;
}

// 测试堆操作
void test_heap_operations() {
    printf("=== 堆操作测试 ===\n");
    
    int heap[20];
    int size = 0;
    
    int values[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int n = sizeof(values) / sizeof(values[0]);
    
    printf("逐步插入元素构建堆:\n");
    for (int i = 0; i < n; i++) {
        heap_insert(heap, &size, values[i]);
        printf("插入 %d 后: ", values[i]);
        for (int j = 0; j < size; j++) {
            printf("%d ", heap[j]);
        }
        printf("\n");
    }
    
    printf("\n逐步提取最大元素:\n");
    while (size > 0) {
        int max_val = heap_extract_max(heap, &size);
        printf("提取最大值 %d，剩余堆: ", max_val);
        for (int i = 0; i < size; i++) {
            printf("%d ", heap[i]);
        }
        printf("\n");
    }
    printf("\n");
}

2.3 堆排序变种

// 最小堆实现（用于升序排序的另一种方法）
void min_heapify(int arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left] < arr[smallest]) {
        smallest = left;
    }
    
    if (right < n && arr[right] < arr[smallest]) {
        smallest = right;
    }
    
    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        min_heapify(arr, n, smallest);
    }
}

// 使用最小堆进行排序（结果为降序）
void heap_sort_min_heap(int arr[], int n) {
    // 构建最小堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        min_heapify(arr, n, i);
    }
    
    // 提取最小元素到末尾（得到降序序列）
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        min_heapify(arr, i, 0);
    }
}

// K路归并排序中的堆应用
typedef struct {
    int value;
    int array_index;
    int element_index;
} HeapNode;

void heapify_nodes(HeapNode arr[], int n, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n && arr[left].value < arr[smallest].value) {
        smallest = left;
    }
    
    if (right < n && arr[right].value < arr[smallest].value) {
        smallest = right;
    }
    
    if (smallest != i) {
        HeapNode temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
        heapify_nodes(arr, n, smallest);
    }
}

// 测试不同变种
void test_heap_sort_variants() {
    printf("=== 堆排序变种测试 ===\n");
    
    int arr1[] = {64, 34, 25, 12, 22, 11, 90};
    int arr2[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr1) / sizeof(arr1[0]);
    
    printf("原始数组: ");
    for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
    printf("\n");
    
    printf("\n最大堆排序（升序）:\n");
    heap_sort_optimized(arr1, n);
    printf("结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr1[i]);
    printf("\n");
    
    printf("\n最小堆排序（降序）:\n");
    heap_sort_min_heap(arr2, n);
    printf("结果: ");
    for (int i = 0; i < n; i++) printf("%d ", arr2[i]);
    printf("\n\n");
}

3. 算法分析

3.1 时间复杂度分析

typedef struct {
    int comparisons;
    int swaps;
    double time_taken;
} HeapSortStats;

HeapSortStats stats;

void heapify_with_stats(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    
    if (left < n) {
        stats.comparisons++;
        if (arr[left] > arr[largest]) {
            largest = left;
        }
    }
    
    if (right < n) {
        stats.comparisons++;
        if (arr[right] > arr[largest]) {
            largest = right;
        }
    }
    
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        stats.swaps++;
        heapify_with_stats(arr, n, largest);
    }
}

void heap_sort_with_stats(int arr[], int n) {
    // 构建堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify_with_stats(arr, n, i);
    }
    
    // 排序
    for (int i = n - 1; i > 0; i--) {
        swap(&arr[0], &arr[i]);
        stats.swaps++;
        heapify_with_stats(arr, i, 0);
    }
}

void analyze_time_complexity() {
    printf("=== 时间复杂度分析 ===\n");
    
    printf("堆排序的时间复杂度:\n");
    printf("- 构建堆: O(n)\n");
    printf("- n-1次调整: O(n log n)\n");
    printf("- 总时间复杂度: O(n log n)\n");
    printf("- 所有情况都是O(n log n)，性能稳定\n\n");
    
    int sizes[] = {100, 500, 1000};
    printf("实际测试验证:\n");
    printf("%-10s %-15s %-15s %-15s\n", "数组大小", "比较次数", "交换次数", "理论复杂度");
    printf("-------------------------------------------------------\n");
    
    for (int s = 0; s < 3; s++) {
        int size = sizes[s];
        int* arr = (int*)malloc(size * sizeof(int));
        
        // 生成随机数据
        srand(42);
        for (int i = 0; i < size; i++) {
            arr[i] = rand() % 1000;
        }
        
        memset(&stats, 0, sizeof(stats));
        heap_sort_with_stats(arr, size);
        
        double theoretical = size * log2(size);
        
        printf("%-10d %-15d %-15d %-15.0f\n", 
               size, stats.comparisons, stats.swaps, theoretical);
        
        free(arr);
    }
    printf("\n");
}

3.2 空间复杂度分析

void analyze_space_complexity() {
    printf("=== 空间复杂度分析 ===\n");
    
    printf("堆排序的空间复杂度:\n");
    printf("- 原地排序: O(1)额外空间\n");
    printf("- 递归版本: O(log n)调用栈\n");
    printf("- 迭代版本: O(1)额外空间\n");
    printf("- 不需要额外的数组空间\n\n");
    
    printf("空间使用详情:\n");
    printf("- 几个局部变量用于索引和临时存储\n");
    printf("- 递归调用栈深度最多O(log n)\n");
    printf("- 可以用迭代版本实现真正的O(1)空间\n\n");
}

4. 优缺点与应用

4.1 优点

void heap_sort_advantages() {
    printf("=== 堆排序的优点 ===\n");
    
    printf("1. 时间复杂度稳定\n");
    printf("   - 始终为O(n log n)\n");
    printf("   - 不受数据分布影响\n\n");
    
    printf("2. 空间效率高\n");
    printf("   - 原地排序，O(1)空间\n");
    printf("   - 适合内存受限环境\n\n");
    
    printf("3. 性能可预测\n");
    printf("   - 最坏情况性能有保证\n");
    printf("   - 适合实时系统\n\n");
    
    printf("4. 堆结构有用\n");
    printf("   - 可用于优先队列\n");
    printf("   - 支持动态维护最值\n\n");
}

4.2 缺点

void heap_sort_disadvantages() {
    printf("=== 堆排序的缺点 ===\n");
    
    printf("1. 不稳定排序\n");
    printf("   - 可能改变相等元素顺序\n");
    printf("   - 不适合需要稳定性的场景\n\n");
    
    printf("2. 缓存性能差\n");
    printf("   - 跳跃式访问模式\n");
    printf("   - 对CPU缓存不友好\n\n");
    
    printf("3. 常数因子大\n");
    printf("   - 虽然是O(n log n)但常数较大\n");
    printf("   - 实际性能可能不如快排\n\n");
    
    printf("4. 不适应已排序数据\n");
    printf("   - 无法利用数据的有序性\n");
    printf("   - 性能不会因预排序而提升\n\n");
}

4.3 应用场景

void heap_sort_applications() {
    printf("=== 应用场景 ===\n");
    
    printf("1. 内存受限环境\n");
    printf("   - 嵌入式系统\n");
    printf("   - 大数据集排序\n\n");
    
    printf("2. 实时系统\n");
    printf("   - 性能可预测\n");
    printf("   - 最坏情况有保证\n\n");
    
    printf("3. 优先队列实现\n");
    printf("   - 任务调度\n");
    printf("   - 事件处理\n\n");
    
    printf("4. 选择算法\n");
    printf("   - 找第K大元素\n");
    printf("   - Top-K问题\n\n");
    
    printf("5. 外部排序\n");
    printf("   - 大文件排序\n");
    printf("   - 多路归并\n\n");
}

5. 主函数

int main() {
    printf("========================================\n");
    printf("       堆排序算法完整演示\n");
    printf("========================================\n\n");
    
    test_basic_heap_sort();
    test_heap_operations();
    test_heap_sort_variants();
    analyze_time_complexity();
    analyze_space_complexity();
    heap_sort_advantages();
    heap_sort_disadvantages();
    heap_sort_applications();
    
    printf("========================================\n");
    printf("            测试完成\n");
    printf("========================================\n");
    
    return 0;
}

6. 总结

堆排序是一种重要的比较排序算法，具有以下特点：

核心优势

• 稳定性能: 时间复杂度始终为O(n log n)
• 空间高效: 原地排序，空间复杂度O(1)
• 可预测性: 最坏情况性能有保证
• 实用性强: 在优先队列等数据结构中广泛应用

技术价值

堆排序不仅是一种排序算法，更重要的是体现了堆数据结构的价值。理解堆排序有助于掌握：

• 完全二叉树的数组表示
• 堆的基本操作和维护
• 优先队列的实现原理

实际应用

虽然在一般情况下性能不如快速排序，但堆排序在需要稳定性能保证的场合仍有重要价值，特别是在实时系统和内存受限的环境中。

版权所有，如有侵权请联系我