前言
本章主要讲解：
数据结构中的堆的知识以及实现
堆的概念和结构
- 概念：
- 将所有元素按完全二叉树的顺序存储方式存储在一个一维数组中并以一定的数据要求存储
- 如果所有父节点的数据大于最大子节点的数据,称为大堆；如果所有父节点的数据小于最小子节点的数据,称为小堆
- 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆
- 性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值
- 堆总是一棵完全二叉树
注：在上节基础知识讲解中我们知道父节点和左右子节点的编码关系，以此可以对应到数组中的下标关系，这里我们主要用数组来表示和实现堆
图示：数组堆
堆的实现
注：这里我们主要实现大堆，对于小堆的实现与大堆只有数据调整上的出入
接口展示
//堆初始化 void HeapInit(HP* hp); //堆销毁 void HeapDestroy(HP* hp); //入堆 void HeapPush(HP* hp, HPDataType x); //出堆 void HeapPop(HP* hp); //堆数据打印 void HeapPrint(HP* hp); //堆顶数据 HPDataType HeapTop(HP* hp); //堆存入数据个数 int HeapSize(HP* hp); // 堆的判空 bool HeapEmpty(HP* hp); //交换函数 void Swap(HPDataType* a, HPDataType* b); //数据向上调整 void AdjustUp(HPDataType* a, int child); //数据向下调整 void AdjustDown(HPDataType* a, int size, int parent);
堆结构创建
这里我们实现的堆的逻辑结构是完全二叉树，存储结构为数组
注：为了方便以及空间的使用，我们采用动态开辟数组空间
- 参考代码：
//默认堆中的数据类型 typedef int HPDataType; //堆结构体类型 typedef struct Heap { HPDataType* a;//数组指针（指向动态开辟的空间） int size;//堆中存放的数据个数 int capacity;//堆的容量（数组长度） }HP;
堆的初始化
注：比较简单
- 参考代码：
//堆初始化 void HeapInit(HP* hp) { assert(hp);//避免传入参数错误 //初始化 hp->a = NULL; hp->size = hp->capacity = 0; }
堆的销毁
注：动态开辟的空间在不使用后需要销毁，避免内存泄漏
- 参考代码：
//堆销毁 void HeapDestroy(HP* hp) { assert(hp);//避免传入参数错误 //释放 free(hp->a); hp->a=NULL;//置空 hp->capacity=hp->size=0; }
入堆
- 注意：
- 入堆需要考虑堆是否满，满堆则需要调整空间大小
- 入堆的数据依旧要保持大堆数据存储的要求
- 入堆方式：
- 这里采用的入堆方式是现将入堆数据先放在堆存储数据最尾部的后一个位置
- 再从这个位置进行向上调整，直到符合大堆的存储要求
注：为了方便调用向上调整，我们将之封装成一个函数
- 参考代码：
//入堆 void HeapPush(HP* hp, HPDataType x) { assert(hp);//避免传入参数错误 //满堆的情况 if (hp->size == hp->capacity) { //如果容量为0则开辟4个空间，否则扩展成原来的两倍 int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HP* tmp = (HP*)realloc(hp->a, sizeof(HP) * newcapacity); if (tmp == NULL)//开辟失败则打印错误并结束进程 { perror("realloc fail:"); exit(-1); } hp->capacity = newcapacity;//更新数据 hp->a = tmp; } //入堆操作 hp->a[hp->size] = x;//先放入尾端，再调整 hp->size++; //数据调整 AdjustUp(hp->a, hp->size - 1);//传入数组地址和下标 }
数据向上调整
- 注意：
- 依据父子节点位置，找到对应下标进行比较数据
- 如果数据不符合大堆则进行交换，直到交换成符合大堆
- 当入堆的数据到下标为0时或者符合大堆时停止交换
- 图示：
注：交换有很多地方需要，依旧封装成函数
- 参考代码：
//交换函数 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } //数据调整 void AdjustUp(HPDataType* a, int child)// { int parent = (child - 1) / 2; while (child) { if (a[parent] < a[child])//不符合情况交换 Swap(&a[parent], &a[child]); else break; //调整下标 child = parent; parent = (child - 1) / 2; } }
入堆测试
- 测试代码：
int main() { int a[] = { 70, 56, 30, 25, 15, 10, 75 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { HeapPush(&hp, a[i]); } HeapPrint(&hp); HeapPush(&hp, 99); HeapPrint(&hp); return 0; }
效果示图
出堆
- 注意：
- 出堆操作是将堆顶的数据给删除
- 删除后数据依旧要保持大堆的特性
- 对于空堆无法出堆
- 出堆方式：
- 首先我们将堆顶数据也就是下标为0的数据与堆尾数据交换
- 交换后让记录存入数据的变量减减，实现删除堆顶数据
- 再让现在堆顶的数据向下调整
- 参考代码：
//出堆（删除堆顶的数据） void HeapPop(HP* hp) { assert(hp);//避免传入参数错误 assert(hp->size);//空堆的情况 Swap(&hp->a[0], &hp->a[hp->size - 1]);//先将堆顶数据与堆尾交换 hp->size--;//再将记录数据个数变量减减实现删除的效果 //对现在堆顶的数据进行下调 AdjustDown(hp->a, hp->size, 0); }
向下调整数据
注意：
同样的依据父子节点位置，找到对应下标进行比较数据
因为堆是一个完全二叉树，需要考虑存在只有左子节点没有右子节点的情况
如果左右子节点都存在，那么与左右子节点中数据大的节点进行比较
如果数据不符合大堆则进行交换，直到交换成符合大堆
当比较的子树下标超出存储数据个数时或者符合大堆时停止交换
图示：
参考代码：
//数据调整 void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child<size) { //找到数据大的儿子 if (child + 1 < size && a[child + 1] > a[child]) { child++; } //将父节点与大子节点交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]);//交换数据 parent = child;//调整下标位置 child = parent * 2 + 1; } else { break;//结束调整 } } }
出堆测试
- 测试代码：
int main() { int a[] = { 70, 56, 30, 25, 15, 10, 75 }; HP hp; HeapInit(&hp); for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i) { HeapPush(&hp, a[i]); } HeapPrint(&hp); HeapPop(&hp); HeapPrint(&hp); HeapPop(&hp); HeapPrint(&hp); return 0; }
效果示图：
堆顶数据获取
- 注意：
- 空堆没有数据
- 参考代码：
//堆顶数据 HPDataType HeapTop(HP* hp) { assert(hp);//避免传入参数错误 assert(!HeapEmpty(hp));//空堆没有数据 return hp->a[0]; }
堆数据个数
- 参考代码：
//堆存入数据个数 int HeapSize(HP* hp) { assert(hp);//避免传入参数错误 return hp->size; }
判断空堆
注：C语言要使用布尔类型需要包含头文件<stdbool.h>
- 参考代码：
// 堆的判空 bool HeapEmpty(HP* hp) { assert(hp);//避免传入参数错误 return hp->size==0; }
堆数据打印
- 参考代码：
//堆数据打印 void HeapPrint(HP* hp) { assert(hp);//避免传入参数错误 for (int i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); }printf("\n"); }
堆源码
- Heap.h:
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> //默认堆中的数据类型 typedef int HPDataType; //堆结构体类型 typedef struct Heap { HPDataType* a;//数组指针（指向动态开辟的空间） int size;//堆中存放的数据个数 int capacity;//堆的容量（数组长度） }HP; //堆初始化 void HeapInit(HP* hp); //堆销毁 void HeapDestroy(HP* hp); //入堆 void HeapPush(HP* hp, HPDataType x); //出堆 void HeapPop(HP* hp); //堆数据打印 void HeapPrint(HP* hp); //堆顶数据 HPDataType HeapTop(HP* hp); //堆存入数据个数 int HeapSize(HP* hp); // 堆的判空 bool HeapEmpty(HP* hp); //交换函数 void Swap(HPDataType* a, HPDataType* b); //数据调整(实现大堆) void AdjustUp(HPDataType* a, int child); //数据调整 void AdjustDown(HPDataType* a, int size, int parent);
- Heap.c
#include"Heap.h" //堆初始化 void HeapInit(HP* hp) { assert(hp);//避免传入参数错误 //初始化 hp->a = NULL; hp->size = hp->capacity = 0; } //堆销毁 void HeapDestroy(HP* hp) { assert(hp);//避免传入参数错误 //释放 free(hp->a); hp->capacity=hp->size=0; } //数据调整 void AdjustUp(HPDataType* a, int child)// { int parent = (child - 1) / 2; while (child) { if (a[parent] < a[child])//不符合情况交换 Swap(&a[parent], &a[child]); else break; //调整下标 child = parent; parent = (child - 1) / 2; } } //数据调整 void AdjustDown(HPDataType* a, int size, int parent) { int child = parent * 2 + 1; while (child<size) { //找到数据大的儿子 if (child + 1 < size && a[child + 1] > a[child]) { child++; } //将父节点与大子节点交换 if (a[child] > a[parent]) { Swap(&a[child], &a[parent]);//交换数据 parent = child;//调整下标位置 child = parent * 2 + 1; } else { break;//结束调整 } } } //入堆 void HeapPush(HP* hp, HPDataType x) { assert(hp);//避免传入参数错误 //满堆的情况 if (hp->size == hp->capacity) { //如果容量为0则开辟4个空间，否则扩展成原来的两倍 int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HP* tmp = (HP*)realloc(hp->a, sizeof(HP) * newcapacity); if (tmp == NULL)//开辟失败则打印错误并结束进程 { perror("realloc fail:"); exit(-1); } hp->capacity = newcapacity; hp->a = tmp; } //入堆操作 hp->a[hp->size] = x;//入尾端，再调整 hp->size++; //数据调整 AdjustUp(hp->a, hp->size - 1);//传入数组地址和下标 } //出堆（删除堆顶的数据） void HeapPop(HP* hp) { assert(hp);//避免传入参数错误 assert(hp->size);//空堆的情况 Swap(&hp->a[0], &hp->a[hp->size - 1]);//先将堆顶数据与堆尾交换 hp->size--;//再将记录数据个数变量减减实现删除的效果 //对现在堆顶的数据进行下调 AdjustDown(hp->a, hp->size, 0); } //堆数据打印 void HeapPrint(HP* hp) { assert(hp);//避免传入参数错误 for (int i = 0; i < hp->size; i++) { printf("%d ", hp->a[i]); }printf("\n"); } //堆存入数据个数 int HeapSize(HP* hp) { assert(hp);//避免传入参数错误 return hp->size; } // 堆的判空 bool HeapEmpty(HP* hp) { assert(hp);//避免传入参数错误 return hp->size==0; } //交换函数 void Swap(HPDataType* a, HPDataType* b) { HPDataType tmp = *a; *a = *b; *b = tmp; } //堆顶数据 HPDataType HeapTop(HP* hp) { assert(hp);//避免传入参数错误 assert(!HeapEmpty(hp));//空堆没有数据 return hp->a[0]; }
有什么问题欢迎留言，可以的话别忘记留下你的点赞哦~
