数据结构：顺序结构二叉树与堆详解

如果每一个层的结点数都达到最大值或满足结点总数是 2^k-1 则这个二叉树就是满二叉树。 2^k-1 的公式推导：

总的结点数：2^0 + 2^1 + 2^2+……+2^(k-1) = 1 * (1 - 2^k) / (1 - 2) = 2^k-1

2.1.2 完全二叉树

规定根结点的层数为 1:

1. 一棵非空二叉树的第 i 层上最多有 2^(i−1) 个结点
2. 深度为 h 的二叉树的最大结点数是 2^h − 1
3. 具有 n 个结点的满二叉树的深度 h = log2(n + 1) (log 以 2 为底，n+1 为对数) -->满二叉树是特殊的完全二叉树。

3 顺序结构二叉树

顺序结构存储是使用数组来存储，在实现完全二叉树能减少空间浪费。

3.1 堆的引入

3.1.1 概念与结构

1. 对于序号 i 对应的结点，若 i>0，则(i-1)/2 为父结点；若 i=0，则无父结点；
2. 若 2*i+1<n，则对应其左孩子；
3. 若 2*i+2<n，则对应其右孩子。

3.2 功能实现

3.2.1 堆的结构

由于堆底层是用数组实现的，因此相似于顺序表，其结构定义如下：

typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
    HPDataType* arr;
    int size; // 有效数据个数
    int capacity; // 容量
} HP;

3.2.2 初始化、销毁

这些代码实现已经在顺序表中介绍到。

// 堆的初始化
void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

// 堆的销毁
void HPDestroy(HP* php) {
    assert(php);
    if (php->arr) free(php->arr);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

3.3 堆的插入数据

熟悉了堆的概念与结构后，我们清楚堆要不就是大根堆，要不就是小根堆。问题在于插入数据后，我们如何通过代码实现化成大根堆或者小根堆的形式？由此我们提出了向上 (下) 调整算法，也会带大家分析这两种算法哪种更好。

3.3.1 向上调整算法

3.4 堆是否为空

bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

3.5 删除堆顶数据

1. 在删除堆顶数据时，先要判断堆是否为空，因此采用 assert。

删除堆顶数据后，如何让其再次成为大 (小) 根堆。

由此我们引入了向下调整算法。

3.5.1 向下调整算法

前提：左右⼦树必须是⼀个堆，才能调整。

3.5.2 获取堆顶数据

HPDataType HPTop(HP* php) {
    assert(!HPEmpty(php));
    return php->arr[0];
}

3.5.2.1 求有效数据个数

int HPSize(HP* php) {
    assert(php);
    return php->size;
}

3.6 向上 (下) 调整算法的复杂度比较

3.6.1 向上调整算法时间复杂度

根据大 O 表示法，则 O(n*log2n) -->详见算法复杂度篇章

3.6.2 向下调整算法时间复杂度

根据大 O 表示法可见时间复杂度为 O(n)

因此向下调整算法的时间复杂度更优。

4 代码实现

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include <time.h>

typedef int HPDataType;
// 定义堆的结构
typedef struct HeapNode {
    HPDataType* arr;
    int size; // 有效数据个数
    int capacity; // 容量
} HP;

// 堆的初始化
void HPInit(HP* php);
// 堆的销毁
void HPDestroy(HP* php);
// 堆的插入数据
void HPPush(HP* php, HPDataType x);
// 删除堆顶数据
void HPPop(HP* php);
// 获取堆顶数据
HPDataType HPTop(HP* php);
// 判空
bool HPEmpty(HP* php);
// 求 size
int HPSize(HP* php);
// 向上调整
void AdjustUp(HPDataType* arr, int child);
// 向下调整
void AdjustDown(HPDataType* arr, int parent, int n);
// 交换
void Swap(int* x, int* y);

Heap.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

// 堆的初始化
void HPInit(HP* php) {
    assert(php);
    php->arr = NULL;
    php->size = php->capacity = 0;
}

// 堆的销毁
void HPDestroy(HP* php) {
    assert(php);
    if (php->arr) free(php->arr);
    php->arr = NULL;
    php->capacity = php->size = 0;
}

// 交换
void Swap(int* x, int* y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

// 向上调整
void AdjustUp(HPDataType* arr, int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        // >: 大堆
        // <: 小堆
        if (arr[child] > arr[parent]) {
            // 交换
            Swap(&arr[child], &arr[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

// 堆的插入数据
void HPPush(HP* php, HPDataType x) {
    assert(php);
    // 判断空间是否不足
    if (php->size == php->capacity) {
        int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
        // 空间不足需要增容
        HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * newCapacity);
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        // realloc 成功
        php->arr = tmp;
        php->capacity = newCapacity;
    }
    php->arr[php->size] = x;
    // 向上调整
    AdjustUp(php->arr, php->size - 1);
    php->size++;
}

// 向下调整
void AdjustDown(HPDataType* arr, int parent, int n) {
    int child = parent * 2 + 1;
    while (child < n) {
        if (child + 1 < n && arr[child] < arr[child + 1]) {
            child++;
        }
        // > 建小堆
        // < 建大堆
        if (arr[parent] < arr[child]) {
            Swap(&arr[parent], &arr[child]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

// 删除堆顶数据
void HPPop(HP* php) {
    assert(!HPEmpty(php));
    Swap(&php->arr[0], &php->arr[php->size - 1]);
    php->size--;
    // 向下调整
    AdjustDown(php->arr, 0, php->size);
}

// 获取堆顶数据
HPDataType HPTop(HP* php) {
    assert(!HPEmpty(php));
    return php->arr[0];
}

// 判空
bool HPEmpty(HP* php) {
    assert(php);
    return php->size == 0;
}

// 求 size
int HPSize(HP* php) {
    assert(php);
    return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"

void test() {
    HP hp;
    HPInit(&hp);
    HPPush(&hp, 1);
    HPPush(&hp, 3);
    HPPush(&hp, 2);
    HPPush(&hp, 4);
    /*HPPop(&hp); HPPop(&hp); HPPop(&hp); HPPop(&hp);*/
    while (!HPEmpty(&hp)) {
        printf("%d ", HPTop(&hp));
        HPPop(&hp);
    }
    HPDestroy(&hp);
}

void test01() {
    int arr[] = { 14, 51, 31, 21, 23, 32 };
    int n = sizeof(arr) / sizeof(arr[0]);
    HP hp;
    HPInit(&hp);
    // 调用 push 将数组中的数据建堆
    for (int i = 0; i < n; i++) {
        HPPush(&hp, arr[i]);
    }
    int i = 0;
    while (!HPEmpty(&hp)) {
        arr[i++] = HPTop(&hp);
        HPPop(&hp);
    }
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    HPDestroy(&hp);
}

int main() {
    // test();
    // test01();
    return 0;
}