【数据结构】二叉树顺序结构之堆的实现

堆的物理本质是一个数组，就可以像动态顺序表一样进行结构定义。

typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size; // 有效元素个数int capacity; // 数组长度
}HP;

3.3 堆的初始化

初始化有两种方式：
① 初始化时我们可以为数组开辟一定大小空间。

② 我们也可以直接将数组指针先置为空指针，插入数据过程中在进一步处理。

代码如下：我们采用的是第二种实现方式

void HeapInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}

3.4 堆的销毁

顺序表空间连续，所以只要free（首地址）就可以。

注意：不能忘记 hp->capacity = hp->size = 0;

代码如下：

void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}

 3.5 堆的插入

① 在插入数据前，我们首先要判断是否要扩容的问题。由于前面初始化时我们直接置空，所以我们先判断容量是否为空。如果为空开4个空间，否则空间扩大到原来的2倍。（为空时，第一次具体开辟多少空间读者可自行选择，我们默认开辟4个字节）
② 接下来就是插入数据了！但有一个问题，直接插入数据可能会破坏堆的结构，所以我们采用了向上调整算法。

实现代码如下： 

void HPPush(HP* php, HPDataType x)
{assert(php);// 判断扩容if (php->size == php->capacity){// 扩容size_t newcapacity = ph->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){// 扩容失败printf("realloc fail\n");exit(-1);}php->capacity = newcapacity;php->a = tmp;}// 数组尾插数据php->a[php->size++] = x;// 向上调整// 参数： 堆数组，插入位置下标AdjustUp(php->a, php->size - 1);
}

3.5.1 向上调整算法

当我们在一个堆的末尾插入一个数据后，需要对堆进行调整，使其仍然是一个堆，

这时需要用到堆的向上调整算法。

向上调整算法的基本思想（以建小堆为例）：

1. 插入数据
2. 与自己的父亲比较
3. 交换/不交换
4. 交换：孩子来到父亲位置，父亲来到自己父亲的位置
5. 结束循环两个点：

• 不交换（跳出循环）
• 一直交换直到来到根节点>0

🌟Tips: 同学们需要记住父节点和孩子节点之间的数量关系

leftchild = parent *2 + 1  左孩子节点下标 = 父亲节点下标*2 + 1
rightchild = parent * 2 + 2  右孩子节点下标 = 父亲节点下标*2 + 2
parent = (child - 1) / 2   父亲节点下标 = （孩子节点下标 - 1）/ 2

如：

​

举个例子：

现在我们给出一个数组[70, 30, 56, 25, 15, 10]，逻辑上就要把他看作一颗完全二叉树。

int array[] = {70, 30, 56, 25, 15, 10};

​

如果我们插入的是8，8是最小值，他就保证小堆结构不发生变化

​

如果我们插入的比堆顶元素小，比如插入60， 我们发现60比它的根节点56大，

这时我们就要使用向上调整算法，调到合适位置即可

​

父亲比孩子小，交换元素。 

 ​

如果插入元素比根节点大，比如插入80

  使用向上调整算法

继续调整

代码如下： 

// 向上调整算法  此处以大堆为例
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;// 结束条件如果是parent>=0，会进入到下一个循环通过break跳出while (child > 0) {if (a[parent] < a[child]){// 父亲结点值小于孩子结点Swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

 3.5.2 向上调整法时间复杂度计算

可得高度与向上调整的关系 

时间复杂度

3.6 删除堆顶元素

     把堆尾元素放到堆顶元素，然后去除堆尾元素（这里直接size--），再向下调整即可。因为原本就是一个堆，现在堆顶元素变了，所以直接向下调整。

代码如下：

void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size-1]);php->size--;AdjustDown(php->a, php->size, 0);
}

3.6.1 向下调整算法

当从堆中移除元素（通常是堆顶元素）后，为了维护堆的性质，需要对剩余的元素进行重新调整。向下调整法就是从父节点开始，通过与其子节点的比较和交换，确保父节点的值不大于（对于大根堆）或不小于（对于小根堆）其子节点的值。

步骤：

1. 删除堆顶元素
2. 堆顶元素与最后一个元素交换
3. 删除最后一个元素
4. 堆顶元素与左右两个孩子（最小/最大的孩子比较）
5. 判断交换/不交换
6. 交换：父亲来到孩子位置，孩子来到自己孩子的位置

判断条件：child + 1 < n && a[child + 1] < a[child]

结束循环条件：child < n（确保左孩子存在）

时间复杂度：O(logN)，其中N是堆中元素的数量。

因为每次调整都涉及沿着树的一条路径向下移动，而树的深度为logN。

那么如何删除堆顶数据后插入数据呢？🤔🤔

如果直接挪动覆盖：操作的时间复杂度太大，而且父子关系就全乱了，不如重新建堆

在这里，以调整为小堆为例，给大家讲解向下调整算法的过程

 代码如下：

// 向下调整算法，这里默认是调整成小堆
void AdjustDown(int* a, int n, int parent)
{assert(a);int child = parent * 2 + 1; // 默认是左孩子while (child < n){// 找出小孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}// 如果小孩子比父亲小，则交换，继续调整if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

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

可得高度与向下调整次数的关系 

可得时间复杂度：

3.7 取堆顶元素

HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

3.8 堆是否为空

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

4. 参考代码 (如果发现上面代码有误，以这里为准)

Heap.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);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);

Heap.c

#include"Heap.h"void HPInit(HP* php)
{assert(php);php->a = NULL;php->size = php->capacity = 0;
}void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->size = php->capacity = 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustUp(HPDataType* a, int child)
{// 初始条件// 中间过程// 结束条件int parent = (child - 1) / 2;//while (parent >= 0)while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[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 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}void AdjustDown(HPDataType* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // child >= n说明孩子不存在，调整到叶子了{// 找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){++child;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// logN
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size-1]);php->size--;AdjustDown(php->a, php->size, 0);
}HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

Test.c

#include"Heap.h"void TestHeap1()
{int a[] = { 4,2,8,1,5,6,9,7,3,2,23,55,232,66,222,33,7,1,66,3333,999 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a)/sizeof(int); i++){HPPush(&hp, a[i]);}int i = 0;while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));//a[i++] = HPTop(&hp);HPPop(&hp);}printf("\n");// 找出最大的前k个/*int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");*/HPDestroy(&hp);
}int main()
{TestHeap1();return 0;
}

以上就是这期博客的全部内容，

有同学们会有疑问：堆在实际问题的求解中有什么样的应用呢？

预知后事如何，请听下回分解，我们下期博客再来探讨~

希望这篇文章能给予你学习中一些帮助，如果有疑问的，欢迎在评论区与我讨论交流哦~