数据结构基础：树的概念与堆的实现详解

1.4 树在实际中的应用

树结构在计算机中应用广泛，最典型的例子就是文件系统的目录树结构。根目录类似于树的根结点，子目录和文件则对应分支结点和叶结点。通过树形结构，我们可以高效地组织和管理文件。

二、二叉树概念及结构

2.1 二叉树的定义

二叉树（Binary Tree）是每个结点最多有两个子树的树结构，并且子树有左右之分，次序不能颠倒。二叉树的定义也是递归的：

• 要么为空树；
• 要么由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。

2.2 现实中的二叉树

2.3 特殊的二叉树

1. 满二叉树：如果一棵二叉树的每一层结点数都达到最大值，即深度为 k 的满二叉树有 2^k - 1 个结点，那么它就是满二叉树。满二叉树的特点是所有分支结点都有左右子树，且叶结点都在最底层。
2. 完全二叉树：对于深度为 k 的二叉树，如果其结点与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应（即从上到下、从左到右编号），则称为完全二叉树。完全二叉树的特点是：
   • 叶结点只可能出现在最后两层；
   • 最后一层的叶结点都靠左排列；
   • 若某个结点没有左孩子，则一定没有右孩子。
     满二叉树是特殊的完全二叉树。

2.4 二叉树的性质

二叉树具有以下重要性质（假设根结点层数为 1）：

1. 第 i 层最多结点数：在二叉树的第 i 层上，最多有 2^(i-1) 个结点（i ≥ 1）。
2. 深度为 h 的最大结点数：深度为 h 的二叉树最多有 2^h - 1 个结点。
3. 叶子结点数与度为 2 的结点数的关系：对任意非空二叉树，若叶子结点数为 n₀，度为 2 的结点数为 n₂，则 n₀ = n₂ + 1。这一性质可以通过总边数关系推导得出：
   • 总结点数 N = n₀ + n₁ + n₂
   • 总边数 = N - 1 = n₁ + 2n₂
   • 联立得 n₀ = n₂ + 1
4. 具有 n 个结点的完全二叉树深度：h = ⌊log₂(n)⌋ + 1（或 h = ⌈log₂(n+1)⌉）。
5. 完全二叉树结点编号特性：若对完全二叉树按从上到下、从左到右从 0 开始编号，则对于编号为 i 的结点：
   • 若 i > 0，其父结点编号为 (i-1)/2；
   • 若 2i+1 < n，其左孩子编号为 2i+1，否则无左孩子；
   • 若 2i+2 < n，其右孩子编号为 2i+2，否则无右孩子。

2.5 二叉树的存储结构

二叉树有两种常用的存储方式：顺序存储和链式存储。

1. 顺序存储

顺序存储使用数组来存放二叉树的结点。对于完全二叉树，这种存储方式非常高效，因为结点在数组中的位置可以直接反映其逻辑关系（利用上述编号特性）。但对于非完全二叉树，数组会浪费大量空间，因此通常只用于完全二叉树（如堆）。

2. 链式存储

链式存储使用结点结构体，每个结点包含数据域以及指向左孩子和右孩子的指针。这是最常用的二叉树存储方式，结构如下：

typedef int BTDataType;
typedef struct BinaryTreeNode {
    struct BinaryTreeNode* left; // 指向当前结点左孩子
    struct BinaryTreeNode* right; // 指向当前结点右孩子
    BTDataType data; // 当前结点值域
} BTNode;

三、堆的概念与结构

3.1 堆的定义

如果有一个关键码的集合 K = {k₀, k₁, k₂, ..., kₙ₋₁}，将其所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：

• 大堆（大根堆）：任意结点的值都大于或等于其左右孩子结点的值，即 Kᵢ ≥ K₂ᵢ₊₁ 且 Kᵢ ≥ K₂ᵢ₊₂。
• 小堆（小根堆）：任意结点的值都小于或等于其左右孩子结点的值，即 Kᵢ ≤ K₂ᵢ₊₁ 且 Kᵢ ≤ K₂ᵢ₊₂。

堆具有以下性质：

• 堆中某个结点的值总是不大于或不小于其父结点的值。
• 堆总是一棵完全二叉树。

3.2 堆的存储结构

堆通常使用顺序存储，即用一个一维数组来存储堆中的所有结点。由于堆是完全二叉树，数组下标可以自然映射结点位置：

• 若根结点下标为 0，则对于下标为 i 的结点：
  • 父结点下标：(i - 1) / 2
  • 左孩子下标：2 * i + 1
  • 右孩子下标：2 * i + 2

四、堆的基本功能实现

下面我们以小堆为例，实现一个动态增长的堆。我们将提供以下接口：

typedef int HeapdataType;
typedef struct Heap {
    HeapdataType* arr;
    int size;      // 这里的 size 指向最后一个元素的下一个位置，初始化时置为 0
    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);

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

堆的核心操作是插入和删除，它们依赖于两个关键调整算法：向上调整和向下调整。

4.1.1 向上调整（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;
        }
    }
}

4.1.2 向下调整（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;
        }
    }
}

4.2 接口实现

4.2.1 初始化与销毁

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;
}

4.2.2 插入元素

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);
}

4.2.3 删除堆顶元素

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);
}

4.2.4 其他简单接口

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;
}

4.2.5 建堆

给定一个数组，我们如何将它调整成一个堆？常用的方法是向下调整建堆：从最后一个非叶子结点开始，依次向前对每个结点执行向下调整。最后一个非叶子结点的下标为 (n-1-1)/2 = n/2 - 1。

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

五、堆排序

堆排序是利用堆这种数据结构进行排序的一种算法，其基本思想是：

1. 建堆：将待排序序列构建成一个堆（升序建大堆，降序建小堆）。
2. 排序：不断将堆顶元素与堆尾元素交换，交换后堆的大小减一，然后对新的堆顶执行向下调整，重复此过程直到堆为空。

以升序排序为例，我们需要建大堆（这样堆顶是最大值），然后每次将最大值交换到最后，并调整剩余元素为大堆，最终得到升序序列。

5.1 堆排序代码实现

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 需要根据堆的类型调整比较逻辑。若用于大堆，向下调整时应将父结点与较大的孩子交换。

5.2 堆排序的时间复杂度

• 建堆阶段：O(n)
• 排序阶段：每次交换后向下调整的时间复杂度为 O(log n)，共进行 n-1 次，因此排序阶段为 O(n log n)
• 总时间复杂度：O(n log n)
• 空间复杂度：O(1)（原地排序，不需要额外空间）

树作为重要的非线性结构，为我们提供了分层组织数据的能力。而堆作为完全二叉树的典型应用，不仅实现了优先队列，还衍生出高效的堆排序算法。通过本文的学习，我们掌握了堆的核心操作（向上调整、向下调整）及其在插入、删除、建堆、排序中的具体实现。希望读者能够动手编写代码，深入理解堆的精髓，并在实际问题中灵活运用。