DS:堆的结构与实现

2024-06-10 00:28
文章标签 实现 结构 ds

本文主要是介绍DS:堆的结构与实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

欢迎来到Harper.Lee的学习世界!
博主主页传送门:Harper.Lee的博客主页
想要一起进步的uu可以来后台找我哦!

一、堆的概念与结构

1.1 堆的概念

堆(Heap)是完全二叉树中的一种,分为大根堆和小根堆。
特点:1.每个节点的值都大于或等于其左右孩子节点的值,称为大根堆;或是每个节点的值都小于或等于其左右孩子的值,称为小根堆。2.从堆的概念不难看出,大根堆堆顶为集合的最大值,小根堆堆顶为集合的最小值。(注意:父亲与孩子之间有大小关系,但是兄弟之间没有大小关系,因此堆并不是有序的!!!)

1.2 堆的结构

根据上一节(DS:树与二叉树的相关概念)可知,完全二叉树以数组的形式存储,因此堆采用数组的形式进行数据的存储。
父子的下标特点:(1)父亲找孩子:leftchild=parent2+1,rightchild=parent2+2;(2)孩子找父亲:parent=(child-1)/2。
image.png

二、堆的实现

2.0 分析过程

插入数据部分分析过程:
image.png

2.1 堆的相关结构体的创建

堆的底层是数组,因此结构体就以数组的形式创建。这一步和之前顺序表的创建基本一样。

//结构体的创建
typedef int HPDataType;
typedef struct Heap
{//以数组为背景HPDataType* a;int size;//表示存储的数据个数int capacity;//表示空间容量,因为我么虽然操作的是二叉树
}HP;

2.2 堆的初始化

//初始化
void HPInit(HP* php)
{//Q:这里需要断言吗???  A:php需要断言,避免传入空堆assert(php);php->a = NULL;php->capacity = php->size = 0;//可以给值,也可以不给值(前面有讲过)//如果capacity和size不给值的话,在插入数据的时候就需要动态申请开辟空间//如果capacity和size赋值的话,就是另外的一种操作。
}

2.3 堆的插入

push就有建立堆的功能。一边插入数据,一边调整出堆的结构。

//push堆的操作
void HPPush(HP* php,HPDataType x)//传入堆,插入一个数据x
{assert(php);//1. 先判断空间是否足够//1. 若空间不够(说明之前有空间的,即使没有空间,capacity也等于size),则进行增容操作if (php->capacity == php->size)//if (php->capacity == php->size == 0),而不是判断是否为空{int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");exit(1);//return;//直接返回也可}php->a = tmp;php->capacity = newcapacity;}//2. 开始插入数据php->a[php->size] = x;//php->size++;//3. 调用向上调整函数AdjustUp(php->a, php->size-1);//为什么第2个参数是size-1而不是size?----要弄清楚size的位置:最后一个数据位置的下标+1
}

2.4 向上调整算法

//向上调整函数的定义
void AdjustUp(HPDataType* a, int child)//从child的位置开始调整,现在child就是数组末尾了
{//虽然控制的十足,但是要把它想象成实在控制二叉树(堆)//1.第一次插入的数据在数组的末尾child位置int parent = (child - 1) / 2;//父节点的位置找到了//2.开始比较父节点和子节点--小根堆:谁小谁当爹//循环三要素:a.初始条件b.中间过程c.结束条件/*while (a[parent] >= 0)//为什么循环结构是>=0?因为实际上最初始的child从末尾开始就需要和她的所有祖先(一条线上的)全部进行比较,比较完循环才会结束)*///如果用parent>=0来判断,那么由于(0-1)/2是-1/2,取整后还是0,就会再次进入循环,一般情况来说这是错误的,但是这里出现了一个巧合:parent==child==0,break跳出循环了,程序歪打正着的正确了。while (a[child] > 0)//上面的循环条件写成下面这种会更好{  if (a[child] < a[parent]){//3.开始进行交换操作(Swap函数的调用)Swap(&a[child], &a[parent]);child = parent;//调整身份继续向上进行下一次(循环可能出现)可能出现的比较parent = (child - 1) / 2;//原来的父亲变成孩子(父亲赋值给孩子),然后原来的父亲变成了前一个祖先。}else{break;// 满足小根堆的结构}}
}

2.5 交换函数

//Swap函数的调用
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp;tmp = *a;*a = *b;*b = tmp;
}

2.6 堆的删除

删除堆的末尾数据是没意义的,因为这个操作很简单,封装成函数就是小题大做了。因此,我们一般删除的是堆顶数据即根位置的数据。但是,如果直接删除/挪动/覆盖了堆顶数据,可能父子关系、叔侄关系、兄弟关系会乱套,倒反天罡了。
所以我么选择一种新的解决办法:根节点的数据和尾节点的数据进行交换,然后再删除尾节点的数据,然后进行向下调整算法重新调整堆的结构,这样就实现了堆顶元素的删除。

分析过程如下:image.png
代码实现:

//Pop删除数据——要求删除堆顶即根位置的数据,删除末尾数据没有意义
void HPPop(HP* php)
{assert(php);//1.将堆顶元素和最后一个元素进行交换Swap(&php->a[php->size-1], &php->a[0]);//尾元素:a[size-1]//2.删除堆中的最后一个元素的数据---怎么删啊?---删除数组中最后一个元素的数据//free(php->a[php->size-1]);//不能使用free,因为内存申请的空间必须一块儿释放,而不是一部分一部分地释放的php->size--;//php->size -= 1;//3.向下调整算法的运用AdjustDown(php->a, php->size, 0);
}

Q1:删除堆顶数据有什么意义或者作用呢?

删除掉了目前堆里最小的元素,相当于取出来堆中的最小的元素。如果连续使用HPPop函数,那么就可以从小到大依次取出堆中的数据,这就是简单模式的TOP-K。

Q2:HPPop的时间复杂度是多少?

pop的时间复杂度为logN(最坏情况),O(1)(最好情况)。而满二叉树/完全二叉树的树高就是logN。

应用:可以一边HPTop获取堆中目前的最小的数据,然后HPPop删除掉这个数据,这样就可以进行排序打印了。

2.7 向下调整算法

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)//从parent根节点开始调整
{//1.先确定(假设法)用哪个孩子与父亲做比较//假设左孩子比右孩子小int child = parent * 2 + 1;//根据父节点找到子节点while (child < n)//child>=n时,说明该孩子已经不存在了 {//找出小的孩子//if (a[child + 1] < a[child])//此写法存在风险:左孩子<n没有风险,但是右孩子+1就可能存在风险if (child + 1 < n && a[child + 1] < a[child]){//如果右孩子比左孩子小:假设不成立,修改假设的内容:++child;//child右移变成右孩子}//2.小孩子与父亲做比较if (a[child] < a[parent]){Swap(&a[parent], &a[child]);//3.交换后进行父亲与孩子的调整parent = child;child = parent * 2 + 1;}else{break;}}
}

2.8 获取堆顶的数据

//获取堆顶的数据(返回堆顶元素)
HPDataType HPTop(HP* php)//top-k问题
{//断言:assert(php);assert(php->size > 0);return php->a[0];
}

2.9 判空

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

2.10 堆的销毁

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

2.11 前k个元素的打印

main函数中堆的建立过程以及打印实现过程:

//
int main()
{int a[] = { 4,2,8,1,5,6,9,7 };//这个数组现在还不是堆,需要将其变成一个堆(一个个地去插入)HP hp;//1.创建一个堆hp//2.初始化HPInit(&hp);//3.建堆(需要插入多个数据,因此,需要多次调用HPPush函数,使用循环结构)for (int i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);//建堆的同时 调整了堆的结构}//4.打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//5.如果是找堆里的最大的前k个数据int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");HPDestroy(&hp); return 0;
}

这里是实现了打印上的有序,但是数组本身并不有序。我们可以将每次HPTop操作获得的堆顶数据放在a数组中,就可以使得数组有序了。也就是上一段代码中注释掉的第 4. 点

	//4.打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//6. 数组a有序的改变int i = 0;while (!HPEmpty(&hp)){//printf("%d ", HPTop(&hp));//获取到堆顶的数据a[i++] = HPTop(&hp);HPPop(&hp);}

三、堆的实现-全部代码

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>//本次-----堆的实现过程 —— 框架//1. 结构体的创建
typedef int HPDataType;
typedef struct Heap
{//以数组为背景HPDataType* a;int size;//表示存储的数据个数int capacity;//表示空间容量,因为我么虽然操作的是二叉树
}HP;//2. 初始化和销毁
void HPInit(HP* php);//php是结构体指针变量
void HPDestroy(HP* php);
//3. 插入HPDataType类型数据x(节点),注意保持堆的完整结构
void HPPush(HP* php, HPDataType x);
//4. Pop删除数据——要求删除堆顶即根位置的数据
void HPPop(HP* php); 
//5. 向下调整法
void AdjustUp(HPDataType* a,int child);
//6. 向上调整法
void AdjustDown(HPDataType* a, int n, int parent);
//7. 判断堆结构是否为空
bool HPEmpty(HP* php);
//8. 交换函数
void Swap(HPDataType* a, HPDataType* b);
//9. 获取堆顶数据
HPDataType HPTop(HP* php);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"//(1) 初始化
void HPInit(HP* php)//传入堆(php是堆的名称)
{//Q:这里需要断言吗???  A:php需要断言,避免传入空堆assert(php);php->a = NULL;php->capacity = php->size = 0;//可以给值,也可以不给值(前面有讲过)//如果capacity和size不给值的话,在插入数据的时候就需要动态申请开辟空间//如果capacity和size赋值的话,就…………???两种玩法一样
}//(2) 销毁(free释放掉动态申请的空间)
void HPDestroy(HP* php)
{assert(php);free(php);//释放掉空间后记得善后php->capacity = php->size = 0;php->a = NULL;
}//(5)Swap函数的调用
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp;tmp = *a;*a = *b;*b = tmp;
}//(4) 向上调整函数的定义
void AdjustUp(HPDataType* a, int child)//从child的位置开始调整,现在child就是数组末尾了
{//虽然控制的十足,但是要把它想象成实在控制二叉树(堆)//1.第一次插入的数据在数组的末尾child位置int parent = (child - 1) / 2;//父节点的位置找到了//2.开始比较父节点和子节点--小根堆:谁小谁当爹//循环三要素:a.初始条件b.中间过程c.结束条件/*while (a[parent] >= 0)//为什么循环结构是>=0?因为实际上最初始的child从末尾开始就需要和她的所有祖先(一条线上的)全部进行比较,比较完循环才会结束)*///如果用parent>=0来判断,那么由于(0-1)/2是-1/2,取整后还是0,就会再次进入循环,一般情况来说这是错误的,但是这里出现了一个巧合:parent==child==0,break跳出循环了,程序歪打正着的正确了。while (a[child] > 0)//上面的循环条件写成下面这种会更好{  if (a[child] < a[parent]){//3.开始进行交换操作(Swap函数的调用)Swap(&a[child], &a[parent]);child = parent;//调整身份继续向上进行下一次(循环可能出现)可能出现的比较parent = (child - 1) / 2;//原来的父亲变成孩子(父亲赋值给孩子),然后原来的父亲变成了前一个祖先。}else{break;// 满足小根堆的结构}}
}//(3) push堆的操作
void HPPush(HP* php,HPDataType x)//传入堆,插入一个数据x
{assert(php);//1. 先判断空间是否足够//1. 若空间不够(说明之前有空间的,即使没有空间,capacity也等于size),则进行增容操作if (php->capacity == php->size)//if (php->capacity == php->size == 0),而不是判断是否为空{int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);if (tmp == NULL){perror("malloc fail");exit(1);//return;//直接返回也可}php->a = tmp;php->capacity = newcapacity;}//2. 开始插入数据php->a[php->size] = x;//php->size++;//3. 调用向上调整函数AdjustUp(php->a, php->size-1);//为什么第2个参数是size-1而不是size?----要弄清楚size的位置:最后一个数据位置的下标+1
}//(7)向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)//从parent根节点开始调整
{//1.先确定(假设法)用哪个孩子与父亲做比较//假设左孩子比右孩子小int child = parent * 2 + 1;//根据父节点找到子节点while (child < n)//child>=n时,说明该孩子已经不存在了 {//找出小的孩子//if (a[child + 1] < a[child])//此写法存在风险:左孩子<n没有风险,但是右孩子+1就可能存在风险if (child + 1 < n && a[child + 1] < a[child]){//如果右孩子比左孩子小:假设不成立,修改假设的内容:++child;//child右移变成右孩子}//2.小孩子与父亲做比较if (a[child] < a[parent]){Swap(&a[parent], &a[child]);//3.交换后进行父亲与孩子的调整parent = child;child = parent * 2 + 1;}else{break;}}
}//(6)Pop删除数据——要求删除堆顶即根位置的数据,删除末尾数据没有意义
void HPPop(HP* php)//logN
{assert(php);assert(php->size > 0);//1.将堆顶元素和最后一个元素进行交换Swap(&php->a[php->size-1], &php->a[0]);//尾元素:a[size-1]//2.删除堆中的最后一个元素的数据---怎么删啊?---删除数组中最后一个元素的数据//free(php->a[php->size-1]);//不能使用free,因为内存申请的空间必须一块儿释放,而不是一部分一部分地释放的php->size--;//php->size -= 1;//3.向下调整算法的运用AdjustDown(php->a, php->size, 0);
}//(7)获取堆顶的数据(返回堆顶元素)
HPDataType HPTop(HP* php)//top-k问题
{//断言:assert(php);assert(php->size > 0);//作用??return php->a[0];
}
//(8)判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"int main()
{ int a[] = { 4,2,8,1,5,6,9,7 };//这个数组现在还不是堆,需要将其变成一个堆(一个个地去插入)HP hp;//1.创建一个堆hp//2.初始化HPInit(&hp);//3.建堆(需要插入多个数据,因此,需要多次调用HPPush函数)for (int i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);//建堆的同时 调整了堆的结构}//1. 打印堆中的所有数据//while (!HPEmpty(&hp))//{//	printf("%d ", HPTop(&hp));//获取到堆顶的数据//	HPPop(&hp);//}//如果是找堆里的最大的前k个数据int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");return 0;
}

喜欢的uu记得三连支持哦!
在这里插入图片描述

这篇关于DS:堆的结构与实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1046727

相关文章

利用Python实现可回滚方案的示例代码

《利用Python实现可回滚方案的示例代码》很多项目翻车不是因为不会做,而是走错了方向却没法回头,技术选型失败的风险我们都清楚,但真正能提前规划“回滚方案”的人不多,本文从实际项目出发,教你如何用Py... 目录描述题解答案(核心思路)题解代码分析第一步:抽象缓存接口第二步:实现两个版本第三步:根据 Fea

Go语言使用slices包轻松实现排序功能

《Go语言使用slices包轻松实现排序功能》在Go语言开发中,对数据进行排序是常见的需求,Go1.18版本引入的slices包提供了简洁高效的排序解决方案,支持内置类型和用户自定义类型的排序操作,本... 目录一、内置类型排序:字符串与整数的应用1. 字符串切片排序2. 整数切片排序二、检查切片排序状态:

python利用backoff实现异常自动重试详解

《python利用backoff实现异常自动重试详解》backoff是一个用于实现重试机制的Python库,通过指数退避或其他策略自动重试失败的操作,下面小编就来和大家详细讲讲如何利用backoff实... 目录1. backoff 库简介2. on_exception 装饰器的原理2.1 核心逻辑2.2

Java实现视频格式转换的完整指南

《Java实现视频格式转换的完整指南》在Java中实现视频格式的转换,通常需要借助第三方工具或库,因为视频的编解码操作复杂且性能需求较高,以下是实现视频格式转换的常用方法和步骤,需要的朋友可以参考下... 目录核心思路方法一:通过调用 FFmpeg 命令步骤示例代码说明优点方法二:使用 Jaffree(FF

基于C#实现MQTT通信实战

《基于C#实现MQTT通信实战》MQTT消息队列遥测传输,在物联网领域应用的很广泛,它是基于Publish/Subscribe模式,具有简单易用,支持QoS,传输效率高的特点,下面我们就来看看C#实现... 目录1、连接主机2、订阅消息3、发布消息MQTT(Message Queueing Telemetr

Java实现图片淡入淡出效果

《Java实现图片淡入淡出效果》在现代图形用户界面和游戏开发中,**图片淡入淡出(FadeIn/Out)**是一种常见且实用的视觉过渡效果,它可以用于启动画面、场景切换、轮播图、提示框弹出等场景,通过... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细

Python实现获取带合并单元格的表格数据

《Python实现获取带合并单元格的表格数据》由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,所以本文我们就来聊聊如何使用Python实现获取带合并单元格的表格数据吧... 由于在日常运维中经常出现一些合并单元格的表格,如果要获取数据比较麻烦,现将将封装成类,并通过调用list_exc

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs

Java进行日期解析与格式化的实现代码

《Java进行日期解析与格式化的实现代码》使用Java搭配ApacheCommonsLang3和Natty库,可以实现灵活高效的日期解析与格式化,本文将通过相关示例为大家讲讲具体的实践操作,需要的可以... 目录一、背景二、依赖介绍1. Apache Commons Lang32. Natty三、核心实现代

SpringBoot实现接口数据加解密的三种实战方案

《SpringBoot实现接口数据加解密的三种实战方案》在金融支付、用户隐私信息传输等场景中,接口数据若以明文传输,极易被中间人攻击窃取,SpringBoot提供了多种优雅的加解密实现方案,本文将从原... 目录一、为什么需要接口数据加解密?二、核心加解密算法选择1. 对称加密(AES)2. 非对称加密(R