数据结构：树的概念与堆的实现

• 父结点：(i-1)/2
• 左孩子：2i+1
• 右孩子：2i+2

存储结构

顺序存储

使用数组存放结点。对完全二叉树非常高效，位置直接反映逻辑关系。非完全二叉树会浪费空间，通常用于堆。

链式存储

最常用方式，包含数据域及左右指针。

typedef int BTDataType;
typedef struct BinaryTreeNode {
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
    BTDataType data;
} BTNode;

堆的概念与结构

定义

将关键码集合 K 按完全二叉树顺序存储在一维数组中：

• 大堆：任意结点值 ≥ 左右孩子值。
• 小堆：任意结点值 ≤ 左右孩子值。

堆总是一棵完全二叉树，且满足父子序关系。

存储结构

通常使用顺序存储（一维数组）。下标映射关系：

• 父结点：(i - 1) / 2
• 左孩子：2 * i + 1
• 右孩子：2 * i + 2

堆的基本功能实现

我们以小堆为例，实现动态增长的堆。核心接口包括初始化、插入、删除、建堆等。

typedef int HeapdataType;
typedef struct Heap {
    HeapdataType* arr;
    int size;       // 当前元素个数
    int capacity;   // 容量
}Hp;

void HeapInit(Hp* hp);
void HeapDestroy(Hp* hp);
void Swap(HeapdataType* n1, HeapdataType* n2);
void AdjustUp(HeapdataType* arr, int child);
void HeapPush(Hp* hp, HeapdataType x);
void AdjustDown(HeapdataType* arr, int size, int parent);
void HeapPop(Hp* hp);
HeapdataType HeapTop(Hp* hp);
int HeapSize(Hp* hp);
bool HeapEmpty(Hp* hp);

辅助函数：向上调整和向下调整

向上调整（AdjustUp）

插入数据后若破坏堆结构，需向上调整。对于小堆，将较小的值向上冒泡直到满足堆序。

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

向下调整（AdjustDown）

删除堆顶时，将堆尾元素移至堆顶并删除原尾，然后向下调整。与小堆中较小的孩子交换，直到满足条件。

void AdjustDown(HeapdataType* arr, int size, int parent) {
    int child = 2 * parent + 1;
    while (child < size) {
        // 选出左右孩子中较小的一个
        if (child + 1 < size && arr[child + 1] < arr[child]) {
            child++;
        }
        if (arr[child] < arr[parent]) {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else {
            break;
        }
    }
}

接口实现

初始化与销毁

void HeapInit(Hp* hp) {
    assert(hp);
    hp->arr = NULL;
    hp->capacity = hp->size = 0;
}

void HeapDestroy(Hp* hp) {
    assert(hp);
    free(hp->arr);
    hp->arr = NULL;
    hp->size = hp->capacity = 0;
}

插入元素

插入前先检查容量，不足则扩容。新元素放在末尾，调用 AdjustUp 维护堆序。

void HeapPush(Hp* hp, HeapdataType x) {
    assert(hp);
    if (hp->size == hp->capacity) {
        int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
        HeapdataType* newarr = (HeapdataType*)realloc(hp->arr, sizeof(HeapdataType) * newcapacity);
        if (newarr == NULL) {
            perror("realloc failed");
            return;
        }
        hp->arr = newarr;
        hp->capacity = newcapacity;
    }
    hp->arr[hp->size++] = x;
    AdjustUp(hp->arr, hp->size - 1);
}

删除堆顶元素

将堆顶与堆尾交换，减小 size，再对新的堆顶执行 AdjustDown。

void HeapPop(Hp* hp) {
    assert(hp);
    assert(hp->size > 0);
    Swap(&hp->arr[0], &hp->arr[hp->size - 1]);
    hp->size--;
    AdjustDown(hp->arr, hp->size, 0);
}

其他简单接口

HeapdataType HeapTop(Hp* hp) {
    assert(hp);
    assert(hp->size > 0);
    return hp->arr[0];
}

int HeapSize(Hp* hp) {
    assert(hp);
    return hp->size;
}

bool HeapEmpty(Hp* hp) {
    assert(hp);
    return hp->size == 0;
}

建堆

给定数组，从最后一个非叶子结点 (n-1-1)/2 开始向前依次向下调整。

for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
    AdjustDown(hp->_a, n, i);
}

堆排序

堆排序利用堆结构进行排序。基本思想：

1. 建堆：构建大堆（升序）或小堆（降序）。
2. 排序：不断将堆顶与堆尾交换，减小堆大小并调整，重复至堆空。

代码实现

升序排序需建大堆，每次将最大值交换到最后。

void HeapSort(int* a, int n) {
    // 1. 建堆（升序建大堆）
    for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(a, n, i);
    }
    // 2. 排序
    int end = n - 1;
    while (end > 0) {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

注意：AdjustDown 的比较逻辑需根据堆类型（大/小）调整。

时间复杂度

• 建堆：O(n)
• 排序：O(n log n)
• 总复杂度：O(n log n)
• 空间复杂度：O(1)

总结

树提供了分层组织数据的能力，而堆作为完全二叉树的典型应用，实现了高效的优先队列和排序算法。掌握向上/向下调整的核心逻辑，就能灵活应对插入、删除、建堆及排序等场景。建议动手编写代码，深入理解其底层机制。