目录
本章主要讲解:
数据结构中的堆的知识以及实现
注:在上节基础知识讲解中我们知道父节点和左右子节点的编码关系,以此可以对应到数组中的下标关系,这里我们主要用数组来表示和实现堆
注:这里我们主要实现大堆,对于小堆的实现与大堆只有数据调整上的出入
//堆初始化
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);//传入数组地址和下标
}
注:交换有很多地方需要,依旧封装成函数
//交换函数
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;
}
//出堆(删除堆顶的数据)
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");
}
#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);
#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];
}
有什么问题欢迎留言,可以的话别忘记留下你的点赞哦~