目录

堆的介绍

堆的概念

堆的性质

堆的结构

堆的向下调整算法

基本思想（以建小堆为例）

 代码

堆的向上调整算法

基本思想（以建小堆为例）

代码

 堆功能的实现

堆的初始化 HeapInit

销毁堆 HeapDestroy

打印堆 HeapPrint

堆的插入 HeapPush

堆的删除 HeapPop

获取堆顶的数据 HeapTop

获取堆的数据个数 HeapSize

堆的判空 HeapEmpty

---

堆的介绍

堆的概念

        堆：如果有一个关键码的集合K={k0,k1,k2,…,kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足ki<=k2i+1且ki<=k2i+2（或满足ki>=k2i+1且ki>=k2i+2），其中i=0,1,2,…，则称该集合为堆。
        小堆：将根结点最小的堆叫做小堆，也叫最小堆或小根堆。
        大堆：将根结点最大的堆叫做大堆，也叫最大堆或大根堆。

堆的性质

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

堆的结构

堆的向下调整算法

        现在我们给出一个数组，逻辑上看作一棵完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。

但是，使用向下调整算法需要满足一个前提：
        若想将其调整为小堆，那么根结点的左右子树必须都为小堆。
        若想将其调整为大堆，那么根结点的左右子树必须都为大堆。 

基本思想（以建小堆为例）

        1.从根结点处开始，选出左右孩子中值较小的孩子。
        2.让小的孩子与其父亲进行比较。
        若小的孩子比父亲还小，则该孩子与其父亲的位置进行交换。并将原来小的孩子的位置当成父亲继续向下进行调整，直到调整到叶子结点为止。
        若小的孩子比父亲大，则不需处理了，调整完成，整个树已经是小堆了。

 代码

// 定义一个交换函数，用于交换两个整数变量的值
void Swap(int* x, int* y)
{
    // 创建一个临时变量存储x指向的值
    int tmp = *x;
    
    // 将y指向的值赋给x指向的位置
    *x = *y;
    
    // 将临时变量tmp的值（原x的值）赋给y指向的位置
    *y = tmp;
}

// 定义一个堆的向下调整函数（针对小顶堆）
void AdjustDown(int* a, int n, int parent)
{
    // 初始化child为当前节点的左孩子的下标，假设左孩子初始时值较小
    int child = 2 * parent + 1;

    // 当孩子节点下标小于数组长度时，循环执行以下操作
    while (child < n)
    {
        // 如果右孩子存在，并且右孩子的值小于左孩子的值
        if (child + 1 < n && a[child + 1] < a[child])
        {
            // 更新child为较小孩子的下标（即右孩子）
            child++;
        }
        
        // 如果孩子（左右中较小的一个）的值小于其父节点的值
        if (a[child] < a[parent])
        {
            // 使用交换函数交换父节点和较小的孩子节点的值
            Swap(&a[child], &a[parent]);

            // 更新parent为刚交换后较小孩子的下标，准备检查新的子树是否满足堆性质
            parent = child;

            // 重新计算下一个待检查的孩子节点的下标
            child = 2 * parent + 1;
        }
        else // 如果当前节点以及其子节点均满足堆性质，则结束调整
        {
            break;
        }
    }
}

        使用堆的向下调整算法，最坏的情况下（即一直需要交换结点），需要循环的次数为：h - 1次（h为树的高度）。而h = log2(N+1)（N为树的总结点数）。所以堆的向下调整算法的时间复杂度为：O(logN) 。 

        上面说到，使用堆的向下调整算法需要满足其根结点的左右子树均为大堆或是小堆才行，那么如何才能将一个任意树调整为堆呢？
        答案很简单，我们只需要从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

// 建堆过程
for (int i = (n - 1 - 1) / 2; i >= 0; i--) 
{
    // 从最后一个非叶子节点开始，依次对每个节点调用向下调整函数
    // 这样做可以确保整个堆结构满足小顶堆的性质
    AdjustDown(php->a, php->size, i);
}

 在这段代码中：

• `n` 表示堆中的元素个数。
• 通过 `(n - 1 - 1) / 2` 计算得到最后一个非叶子节点的索引。
• 遍历从最后一个非叶子节点到根节点（索引为0），依次对每个节点执行向下调整操作，使得每个节点及其子树构成一个小顶堆。
• `php->a` 是指向堆数组的指针，`php->size` 是堆的大小（元素个数）。
• 调用 `AdjustDown` 函数逐个对每个父节点进行调整，以保证堆的特性。当遍历完成后，整个数组便构成了一个小顶堆。

堆的向上调整算法

        当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，这时需要用到堆的向上调整算法。

基本思想（以建小堆为例）

        1.将目标结点与其父结点比较。

        2.若目标结点的值比其父结点的值小，则交换目标结点与其父结点的位置，并将原目标结点的父结点当作新的目标结点继续进行向上调整。若目标结点的值比其父结点的值大，则停止向上调整，此时该树已经是小堆了。

代码

// 定义一个交换函数，用于交换两个自定义类型 HPDataType 指针所指向的数据
void Swap(HPDataType* x, HPDataType* y)
{
    // 创建一个临时变量存储x指向的数据
    HPDataType tmp = *x;
    
    // 将y指向的数据赋给x指向的位置
    *x = *y;
    
    // 将临时变量tmp的数据（原x的数据）赋给y指向的位置
    *y = tmp;
}

// 定义一个堆的向上调整函数（针对小顶堆）
void AdjustUp(HPDataType* a, int child)
{
    // 根据孩子节点的下标计算其父节点的下标
    int parent = (child - 1) / 2;

    // 当孩子节点的下标大于0（即未到达根节点）时，循环执行以下操作
    while (child > 0)
    {
        // 如果孩子节点的值小于其父节点的值
        if (a[child] < a[parent])
        {
            // 使用交换函数交换孩子节点和父节点的数据
            Swap(&a[child], &a[parent]);

            // 更新孩子节点为刚刚交换后的父节点，以便继续向上调整
            child = parent;

            // 重新计算新的父节点下标
            parent = (child - 1) / 2;
        }
        else // 如果孩子节点与其父节点的值关系已经满足堆的性质，则停止调整
        {
            break;
        }
    }
}

在上述代码中：

• HPDataType 是用户自定义的数据类型，这里假设它支持 < 运算符用于比较大小。
• AdjustUp 函数主要用于将新插入或更新后的元素调整到正确位置，以保持小顶堆的性质。从下标为 child 的节点开始，如果其值小于父节点，则两者交换位置，直到无法继续交换（即已达到根节点或者不再违反堆的性质）。

 堆功能的实现

堆的初始化 HeapInit

        首先，必须创建一个堆类型，该类型中需包含堆的基本信息：存储数据的数组、堆中元素的个数以及当前堆的最大容量。

// 数据类型定义
typedef int HPDataType; // 定义堆中存储数据的类型为整型

// 结构体定义
typedef struct Heap
{
	// 堆中存储数据的数组，动态分配内存来存储堆中的元素
	HPDataType* a;

	// 记录堆中已有元素的个数
	int size;

	// 记录堆的最大容量，即数组a可容纳的元素数量
	int capacity;
} HP; 

        创建完堆类型后，我们还需要一个初始化函数，对刚创建的堆进行初始化，注意在初始化期间要将传入数据建堆。

// 定义一个初始化堆的函数
void HeapInit(HP* php, HPDataType* a, int n)
{
    // 断言检查传入的堆结构指针是否有效
    assert(php);

    // 动态申请一块足够容纳n个HPDataType类型数据的内存空间
    HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*n);
    
    // 检查内存申请是否成功
    if (tmp == NULL)
    {
        printf("动态内存分配失败！\n");
        exit(-1); // 若分配失败，程序终止运行
    }

    // 将新申请的内存空间赋值给堆结构的数组成员
    php->a = tmp;

    // 使用memcpy函数将输入数组a中的数据复制到堆结构的数组中
    memcpy(php->a, a, sizeof(HPDataType)*n);

    // 设置堆的已有元素个数为输入的n
    php->size = n;

    // 同时设置堆的容量也为n
    php->capacity = n;

    // 初始化堆：从最后一个非叶子节点开始，依次对每个节点进行向下调整操作
    int i = 0;
    for (i = (php->size - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDown(php->a, php->size, i);
    }
}

        此函数的作用是初始化一个堆结构，并根据传入的数据构建一个小顶堆。首先动态分配内存以存储堆中的数据，然后将输入数组a中的数据复制到堆结构的数组中。接着设置堆的大小和容量，并从最后一个非叶子节点开始，使用 AdjustDown 函数对每一个节点进行调整，最终使整个数据结构满足小顶堆的性质。 

销毁堆 HeapDestroy

        为了避免内存泄漏，使用完动态开辟的内存空间后都要及时释放该空间，所以，一个用于释放内存空间的函数是必不可少的。

// 定义一个销毁堆的函数
void HeapDestroy(HP* php)
{
    // 断言检查传入的堆结构指针是否有效
    assert(php);

    // 释放之前动态分配给堆结构数组的空间
    free(php->a);

    // 置堆结构的数组指针为空，防止野指针问题
    php->a = NULL;

    // 将堆中元素个数清零
    php->size = 0;

    // 将堆的容量也清零
    php->capacity = 0;
}

        此函数用于销毁堆结构，释放堆占用的内存资源并将相关状态信息重置为初始状态，以便后续可能的再次初始化或避免产生内存泄漏等问题。 

打印堆 HeapPrint

        打印堆中的数据，这里用了两种打印格式。第一种打印格式是按照堆的物理结构进行打印，即打印为一排连续的数字。第二种打印格式是按照堆的逻辑结构进行打印，即打印成树形结构。

// 计算具有n个节点的完全二叉树的深度
int depth(int n)
{
    assert(n >= 0);

    if (n > 0)
    {
        int m = 2;
        int height = 1;
        while (m < n + 1)
        {
            m *= 2;
            height++;
        }
        return height;
    }
    else
    {
        return 0;
    }
}

// 打印堆
void HeapPrint(HP* php)
{
    assert(php);

    // 按照数组形式打印堆内容
    int i = 0;
    for (i = 0; i < php->size; i++)
    {
        printf("%d ", php->a[i]);
    }
    printf("\n");

    // 按照树形结构打印堆内容
    int tree_depth = depth(php->size);
    int total_nodes = pow(2, tree_depth) - 1; // 获取对应深度的满二叉树的节点总数
    int current_spaces = total_nodes - 1; // 记录每一行前面的空格数
    int current_row = 1; // 当前行数
    int index = 0; // 待打印数据的下标

    while (true)
    {
        // 打印前面的空格
        for (int i = 0; i < current_spaces; i++)
        {
            printf(" ");
        }

        // 打印数据和间距
        int nodes_in_row = pow(2, current_row - 1); // 每一行的数字个数
        while (nodes_in_row--)
        {
            printf("%02d", php->a[index++]); // 打印数据

            if (index >= php->size) // 如果所有数据都已打印，则结束打印
            {
                printf("\n");
                return;
            }

            int spaces_between_numbers = (current_spaces + 1) * 2; // 两个数之间的空格数
            for (int j = 0; j < spaces_between_numbers; j++) // 打印两个数之间的空格
            {
                printf(" ");
            }
        }
        printf("\n"); // 换行

        current_row++; // 下一行
        current_spaces = current_spaces / 2 - 1; // 更新当前行的空格数
    }
}

这段代码实现了两个功能：

• depth 函数用于计算具有n个节点的完全二叉树的深度。

• HeapPrint 函数用于打印堆的内容。首先按数组顺序打印堆的所有元素，然后按照树形结构打印堆，使其看起来像一棵二叉树。通过计算堆对应的完全二叉树的深度，确定每一层节点的数量及相应空格数，从而实现树形结构的打印。

堆的插入 HeapPush

        数据插入时是插入到数组的末尾，即树形结构的最后一层的最后一个结点，所以插入数据后我们需要运用堆的向上调整算法对堆进行调整，使其在插入数据后仍然保持堆的结构。

// 插入元素到堆中
void HeapPush(HP* php, HPDataType x)
{
    // 断言检查堆结构指针有效性
    assert(php);

    // 判断堆是否已满，如果满了则尝试扩大容量
    if (php->size == php->capacity)
    {
        // 申请两倍于当前容量的新内存空间
        HPDataType* tmp = (HPDataType*)realloc(php->a, 2 * php->capacity * sizeof(HPDataType));

        // 检查内存分配是否成功
        if (tmp == NULL)
        {
            printf("动态内存扩充失败！\n");
            exit(-1); // 分配失败则退出程序
        }

        // 成功分配内存后，更新堆结构的数组指针和容量值
        php->a = tmp;
        php->capacity *= 2;
    }

    // 将新元素添加至堆数组末尾
    php->a[php->size] = x;

    // 堆大小加一
    php->size++;

    // 调整堆结构，确保新插入元素后的堆仍满足堆属性
    AdjustUp(php->a, php->size - 1); // 从新增节点开始向上调整
}

        在这个函数中，我们首先检查堆是否已满，若满则通过realloc函数扩大堆容量。接着将新元素添加至堆数组的末尾，并增加堆的大小计数。最后调用`AdjustUp`函数对新插入的元素进行上浮调整，确保堆仍然满足小顶堆的性质。

堆的删除 HeapPop

        堆的删除，删除的是堆顶的元素，但是这个删除过程可并不是直接删除堆顶的数据，而是先将堆顶的数据与最后一个结点的位置交换，然后再删除最后一个结点，再对堆进行一次向下调整。

        原因：我们若是直接删除堆顶的数据，那么原堆后面数据的父子关系就全部打乱了，需要全体重新建堆，时间复杂度为O(N)。

        若是用上述方法，那么只需要对堆进行一次向下调整即可，因为此时根结点的左右子树都是小堆，我们只需要在根结点处进行一次向下调整即可，时间复杂度为 O(log(N))。

// 删除堆顶元素
void HeapPop(HP* php)
{
    // 断言检查堆结构指针有效性
    assert(php);

    // 断言检查堆是否为空，如果不是空堆才能进行删除操作
    assert(!HeapEmpty(php));

    // 将堆顶元素（即数组的第一个元素）与堆的最后一个元素交换
    Swap(&php->a[0], &php->a[php->size - 1]);

    // 删除堆的最后一个元素，即将堆大小减一
    php->size--;

    // 由于堆顶元素可能不再满足堆的性质，因此需要对新的堆顶元素进行向下调整操作，以恢复堆的有序性
    AdjustDown(php->a, php->size, 0);
}

        此函数首先确认堆不为空，然后通过交换堆顶元素和堆尾元素的位置，实际上将堆尾元素移到了堆顶。接着减少堆的大小表示删除了堆顶元素，最后调用 `AdjustDown` 函数从新的堆顶元素开始向下调整堆，确保剩余元素重新形成符合堆性质的结构。

获取堆顶的数据 HeapTop

        获取堆顶的数据，即返回数组下标为0的数据。

// 获取堆顶元素的值
HPDataType HeapTop(HP* php)
{
    // 断言检查堆结构指针有效性
    assert(php);

    // 断言检查堆是否为空，非空堆才能获取堆顶数据
    assert(!HeapEmpty(php));

    // 返回堆顶元素的值，即堆数组的第一个元素
    return php->a[0];
}

        此函数用于安全地获取堆顶元素的值，在确保堆非空的情况下直接返回堆顶元素（小顶堆中最小的元素）。若堆为空，则会触发断言错误，提示堆为空无法获取堆顶元素。 

获取堆的数据个数 HeapSize

        获取堆的数据个数，即返回堆结构体中的size变量。

// 获取堆中元素个数
int HeapSize(HP* php)
{
    // 断言检查堆结构指针有效性
    assert(php);

    // 返回堆中当前存储的数据个数
    return php->size;
}

        此函数用于获取堆中实际包含的元素数量，只需直接返回堆结构体中的 `size` 成员变量即可。在调用此函数前，需确保堆结构指针有效。

堆的判空 HeapEmpty

        堆的判空，即判断堆结构体中的size变量是否为0。

// 判断堆是否为空
bool HeapEmpty(HP* php)
{
    // 断言检查堆结构指针有效性
    assert(php);

    // 如果堆中数据个数为0，则认为堆为空
    return php->size == 0;
}

        此函数用于检查堆中是否有数据，通过查看堆结构体中的 `size` 成员变量是否为0来判断。当堆中没有元素时，函数返回 true，表示堆为空；否则返回 false，表示堆中有至少一个元素。在调用此函数前，需确保堆结构指针有效。