堆排序算法：基于完全二叉树的高效排序

算法原理

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

基本思想

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

堆的性质

• 最大堆：父节点 ≥ 子节点
• 最小堆：父节点 ≤ 子节点
• 完全二叉树：除最后一层外，其他层节点全满

C语言实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SWAP(a, b) do { int temp = a; a = b; b = temp; } while(0)

/**
 * 调整堆结构（向下调整）
 * @param arr 数组
 * @param start 调整起始位置
 * @param end 调整结束位置
 */
void heapify(int arr[], int start, int end) {
    int parent = start;
    int child = 2 * parent + 1; // 左子节点
    
    while (child <= end) {
        // 选择较大的子节点
        if (child + 1 <= end && arr[child] < arr[child + 1]) {
            child++;
        }
        
        // 如果父节点已经大于子节点，调整完成
        if (arr[parent] >= arr[child]) {
            break;
        }
        
        // 交换父子节点
        SWAP(arr[parent], arr[child]);
        
        // 继续向下调整
        parent = child;
        child = 2 * parent + 1;
    }
}

/**
 * 堆排序主函数
 */
void heap_sort(int arr[], int n) {
    // 1. 构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, i, n - 1);
    }
    
    // 2. 排序过程
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素（最大值）交换到末尾
        SWAP(arr[0], arr[i]);
        
        // 重新调整堆结构
        heapify(arr, 0, i - 1);
    }
}

/**
 * 向上调整堆结构（用于插入操作）
 */
void heapify_up(int arr[], int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        
        if (arr[index] <= arr[parent]) {
            break;
        }
        
        SWAP(arr[index], arr[parent]);
        index = parent;
    }
}

/**
 * 堆的插入操作
 */
void heap_insert(int arr[], int* size, int value) {
    arr[*size] = value;
    heapify_up(arr, *size);
    (*size)++;
}

/**
 * 堆的删除操作（删除堆顶）
 */
int heap_extract_max(int arr[], int* size) {
    if (*size <= 0) return -1;
    
    int max_value = arr[0];
    arr[0] = arr[*size - 1];
    (*size)--;
    
    if (*size > 0) {
        heapify(arr, 0, *size - 1);
    }
    
    return max_value;
}

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