开卷数据结构?--堆的实现超详解

2021年11月20日 阅读数:0
这篇文章主要向大家介绍开卷数据结构?--堆的实现超详解,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

目录数组

前言数据结构

堆的概念和结构函数

堆的实现测试

接口展现编码

堆结构建立spa

堆的初始化指针

堆的销毁code

入堆blog

数据向上调整接口

入堆测试

出堆

向下调整数据

出堆测试

堆顶数据获取

堆数据个数

判断空堆

堆数据打印

堆源码


前言


本章主要讲解:
数据结构中的堆的知识以及实现

堆的概念和结构


  • 概念:
  1. 将全部元素按彻底二叉树的顺序存储方式存储在一个一维数组中并以必定的数据要求存储
  2. 若是全部父节点的数据大于最大子节点的数据,称为大堆;若是全部父节点的数据小于最小子节点的数据,称为小堆
  3. 将根节点最大的堆叫作最大堆或大根堆,根节点最小的堆叫作最小堆或小根堆
  • 性质:
  1. 堆中某个节点的值老是不大于或不小于其父节点的值
  2. 堆老是一棵彻底二叉树
注:在上节基础知识讲解中咱们知道父节点和左右子节点的编码关系,以此能够对应到数组中的下标关系,这里咱们主要用数组来表示和实现堆
  • 图示:数组堆

 

堆的实现


注:这里咱们主要实现大堆,对于小堆的实现与大堆只有数据调整上的出入

接口展现

//堆初始化
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;
}

入堆

  • 注意:
  1. 入堆须要考虑堆是否满,满堆则须要调整空间大小
  2. 入堆的数据依旧要保持大堆数据存储的要求
  • 入堆方式:
  1. 这里采用的入堆方式是现将入堆数据先放在堆存储数据最尾部的后一个位置
  2. 再从这个位置进行向上调整,直到符合大堆的存储要求

 注:为了方便调用向上调整,咱们将之封装成一个函数

  • 参考代码:
//入堆
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);//传入数组地址和下标
}

数据向上调整

  • 注意:
  1. 依据父子节点位置,找到对应下标进行比较数据
  2. 若是数据不符合大堆则进行交换,直到交换成符合大堆
  3. 当入堆的数据到下标为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;
}
  • 效果示图:

出堆

  • 注意:
  1. 出堆操做是将堆顶的数据给删除
  2. 删除后数据依旧要保持大堆的特性
  3. 对于空堆没法出堆
  • 出堆方式:
  1. 首先咱们将堆顶数据也就是下标为0的数据与堆尾数据交换
  2. 交换后让记录存入数据的变量减减,实现删除堆顶数据
  3. 再让如今堆顶的数据向下调整
  • 参考代码:
//出堆(删除堆顶的数据)
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);
}

向下调整数据

  • 注意:
  1. 一样的依据父子节点位置,找到对应下标进行比较数据
  2. 由于堆是一个彻底二叉树,须要考虑存在只有左子节点没有右子节点的状况
  3. 若是左右子节点都存在,那么与左右子节点中数据大的节点进行比较
  4. 若是数据不符合大堆则进行交换,直到交换成符合大堆
  5. 当比较的子树下标超出存储数据个数时或者符合大堆时中止交换
  • 图示:

  •  参考代码:
//数据调整
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;
}
  •  效果示图:

堆顶数据获取

  • 注意:
  1. 空堆没有数据
  • 参考代码:
//堆顶数据
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];
}

有什么问题欢迎留言,能够的话别忘记留下你的点赞哦~