【初阶数据结构】实现顺序结构二叉树-＞堆（附源码）

文章目录

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！

👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！
🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对数据结构感兴趣的朋友，让我们一起进步！

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。

1.堆的概念与结构

如果有⼀个关键码的集合 K = { k 0 , k 1 , k 2 , ... ， k n −1 } ，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜： K i <= K 2∗ i +1 （ K i >= K 2∗ i +1 且 K i <= K 2∗ i +2 ），i = 0、 1 、 2... ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆

叫做最⼩堆或⼩根堆。

1.1 堆的性质

• 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值；

• 堆总是⼀棵完全⼆叉树。

1.1.1 ⼆叉树性质

• 对于具有 n 个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有结点从

0 开始编号，则对于序号为 i 的结点有：

1. 若 i>0 ， i 位置结点的双亲序号： (i-1)/2 ； i=0 ， i 为根结点编号，⽆双亲结点（通常称为父节点）

2. 若 2i+1<n ，左孩⼦序号： 2i+1 ， 2i+1>=n 否则⽆左孩⼦

3. 若 2i+2<n ，右孩⼦序号： 2i+2 ， 2i+2>=n 否则⽆右孩⼦

2 堆的模拟实现

底层：使用数组，进行了特殊的处理成为堆。

下面将以建立小堆为示例：

heap.h头文件下的函数声明和其它头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义堆的结构---数组typedef int HPDataType;typedef struct Heap
{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);

测试文件：

#include"Heap.h"void test01()
{HP hp;HPInit(&hp);int arr[] = { 17,20,10,13,19,15 };for (int i = 0; i < 6; i++){HPPush(&hp, arr[i]);}//HPPop(&hp);while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}HPDestroy(&hp);
}int main()
{test01();return 0;
}

heap.c函数的实现方法（重点）

2.1 堆的初始化和销毁

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->size = php->capacity = 0;
}

2.2 入堆操作

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, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);++php->size;
}

2.2.1 向上调整算法

入堆之后，可能现在堆的数据不符合小堆或大堆的特性，需要从新调整堆的结构。

因此向上调整算法产生。

将新数据插⼊到数组的尾上，再进⾏向上调整算法，直到满⾜堆。

向上调整算法

• 先将元素插⼊到堆的末尾,即最后⼀个孩⼦之后

• 插⼊之后如果堆的性质遭到破坏，将新插⼊结点顺着其双双亲往上调整到合适位置即可

步骤（如下图）

代码如下:

void AdjustUp(HPDataType* arr,int child)
{int parent = (child - 1) / 2;while (child > 0)//不需要等于，child只要走到根节点的位置，根节点没有父节点不需要交换{if (arr[child] < arr[parent]){Swap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}	
}

2.3 堆的判空

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

2.4 出堆

将堆顶与最后一个数据交换，交换完成有效数据个数-1，在进行向下调整算法，因为可能删除后的数据结构不符合堆的特性。

出堆（删除数据）：只能删除堆顶数据。

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

2.4.1 向下调整算法

void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子//while (parent < n)while (child < n){//找左右孩子中找最小的if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

2.5 取堆顶数据

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

2.6 获取堆有效数据个数

//获取堆中有效数据个数
size_t HPsize(HP* php)
{return php->size;
}

（附源码）

#define _CRT_SECURE_NO_WARNINGS 1
#include"Heap.h"void HpInit(HP* php)
{assert(php);php->arr = NULL;php->capacity = php->size = 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;
}//时间复杂度logn
void AdjustUp(HpDataType* arr,int child)
{int parent = (child - 1) / 2;while (child>0){//if (arr[child] > arr[parent])//升序if (arr[child] < arr[parent])//降序{swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void AdjustDown(HpDataType* arr,int parent , int n)
{int child = 2 * parent + 1;//左孩子while (child < n){//if (child + 1 < n && arr[child] > arr[child + 1])//降序if (child + 1 < n && arr[child] < arr[child + 1])//升序->建大堆{child++;}if (arr[child] > arr[parent])//升序//if (arr[child] < arr[parent])//降序{swap(&arr[parent], &arr[child]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HpPop(HP* php)//出堆：出的是堆顶的数据
{assert(php && php->arr);swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;AdjustDown(php->arr, 0, php->size);
}bool HPEmpty(HP* php)
{assert(php);return php->size==0;
}HpDataType HoTop(HP* php)
{assert(php && php->size);return php->arr[0];
}void HpPush(HP* php, HpDataType x)
{assert(php);//扩容if (php->capacity == php->size){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HpDataType* tmp = (HpDataType*)realloc(php->arr, newCapacity * sizeof(HpDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//建小堆AdjustUp(php->arr, php->size);++php->size;
}//获取堆中有效数据个数
size_t HPsize(HP* php)
{return php->size;
}