C语言数据结构：当树结构钻进数组?———堆的终极指南

堆（Heap）是一种非常重要的数据结构，它在优先队列、堆排序等场景中有广泛应用。本文将详细介绍堆的实现原理和堆排序算法。

一、堆的基本概念

堆是一种特殊的完全二叉树，它满足以下性质：

• 大根堆：每个节点的值都大于或等于其子节点的值
• 小根堆：每个节点的值都小于或等于其子节点的值

下面以大根堆为例

二、堆的结构实现

typedef int HeapDataType;
typedef struct {
    HeapDataType* a;  // 动态数组存储堆元素
    int size;         // 当前堆的大小
    int capacity;     // 堆的容量
} Heap;

三、核心操作实现

1. 初始化堆

void HeapInit(Heap* h) {
    h->a = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);
    h->size = 0;
    h->capacity = 4;
}

2. 交换元素

void Swap(HeapDataType* a, HeapDataType* b) {
    HeapDataType tmp = *a;
    *a = *b;
    *b = tmp;
}

3. 向上调整（AdjustUp）

void AdjustUp(HeapDataType* a, int child) {
    assert(a);
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

当向堆中插入新元素时，将其放在数组末尾，然后通过向上调整保持堆的性质。

4. 向下调整（AdjustDown）

void AdjustDown(HeapDataType* a, int size, int parent) {
    int child = parent * 2 + 1;
    while (child < size) {
        if (child + 1 < size && a[child] < a[child + 1]) {
            child++;
        }
        if (a[parent] < a[child]) {
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

当删除堆顶元素时，将最后一个元素移到堆顶，然后通过向下调整保持堆的性质。

四、堆的基本操作

1. 插入元素（HeapPush）

void HeapPush(Heap* h, HeapDataType val) {
    assert(h && h->a);
    // 检查并扩容
    if (h->size == h->capacity) {
        h->a = (HeapDataType*)realloc(h->a, sizeof(HeapDataType) * h->capacity * 2);
        h->capacity *= 2;
    }
    // 插入到末尾并向上调整
    h->a[h->size++] = val;
    AdjustUp(h->a, h->size - 1);
}

将新元素插入末尾并向上调整。

2. 删除堆顶（HeapPop）

void HeapPop(Heap* h) {
    assert(h && h->a);
    if (h->size == 0) {
        printf("error:堆中元素个数为0\n");
        return;
    }
    // 交换堆顶和末尾元素，然后向下调整
    Swap(&h->a[0], &h->a[h->size - 1]);
    h->size--;
    AdjustDown(h->a, h->size, 0);
}

删除堆顶元素时，先将其与最后一个元素交换，然后缩小堆大小并向下调整。

3. 获取堆顶元素

HeapDataType HeapTop(HeapDataType* a) {
    return a[0];
}

直接返回数组第一个元素，即堆顶元素。

五、堆排序算法

void HeapSort(HeapDataType* a, int n) {
    // 建堆：从最后一个非叶子节点开始向下调整
    // ps:建堆时向下调整效率高于向上调整
    for (int i = (n - 2) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    
    // 排序：每次将堆顶元素(最大)放到末尾，然后调整堆
    int end = n - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

堆排序分为两个阶段：

1. 建堆阶段：从最后一个非叶子节点开始，向前逐个进行向下调整
2. 排序阶段：每次将堆顶元素（当前最大值）与末尾元素交换，然后对剩余元素进行向下调整

堆排序的时间复杂度为O(n log n)，是一种非常高效的排序算法。

六、堆的应用

• Top K问题：快速找出前K个最大/最小元素

七、总结

堆是一种高效的数据结构。堆的核心在于维护堆性质的调整操作（AdjustUp和AdjustDown），理解这些操作是掌握堆的关键。

堆排序虽然不如快速排序在大多数情况下快，但它有稳定的O(n log n)时间复杂度，并且是原地排序，不需要额外空间。

感谢您的阅读和关注！ (˶╹ꇴ╹˶)