堆 (带图详解)

news/2024/4/29 4:47:15/文章来源:https://blog.csdn.net/qq_62939852/article/details/127932846

文章目录

  • 1.堆的基本概念
    • 1. 概念
    • 2.性质
      • 1.必须为完全二叉树
      • 2.满足大堆/小堆成立的条件
    • 3.存储方式
      • 1.逻辑结构
      • 2.物理结构
    • 4. 孩子与父亲之间下标的关系
  • 2.堆的基本实现
    • 1.push——插入
      • 1.代码
      • 2. 情况分析
        • 情况1
        • 情况2
      • 3. 向上调整算法
        • 1.过程分析
        • 2. 临界条件的判断
    • 2. pop—— 删除
      • 1.代码
      • 2. 向下调整算法
        • 1. 注意事项
        • 2. 临界条件
        • 3.TOPK问题
          • 1.过程分析
    • 3. create ——建堆
      • 1.向下调整算法的应用
    • 4. top—— 取堆顶元素
    • 5. size—— 数据个数
    • 6. empty ——判空
    • 7. TOPK问题的具体实现
  • 完整代码
      • 1.heap.h
      • 2.heap.c
      • 3.test.c

1.堆的基本概念

1. 概念

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且
<= ( >= 且 >= ) i = 0，1，
2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

2.性质

1.必须为完全二叉树

在这里插入图片描述

2.满足大堆/小堆成立的条件

在这里插入图片描述

  • 大堆：树中所有父亲节点都大于等于孩子节点

在这里插入图片描述

  • 小堆：树中所有父亲节点都小于等于孩子节点

3.存储方式

1.逻辑结构

在这里插入图片描述

  • 逻辑结构：我们想象出来的

2.物理结构

在这里插入图片描述

  • 物理结构：实实在在在内存是如何存储的

4. 孩子与父亲之间下标的关系

在这里插入图片描述

  • leftchild=parent*2+1

  • rightchild=parent*2+2

  • parent=(child-1)/2

这里child 可以是leftchild，也可以是rightchild，因为整数相除得到的结果也为整数

2.堆的基本实现

1.push——插入

1.代码

void adjustup(HPDatatype* a, int child)//向上调整算法
{int parent = (child - 1) / 2;while (child>0){if (a[parent] >a[child])//以小堆为例{swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}
void heappush(HP* php, HPDatatype x)//插入
{assert(php);if (php->capacity == php->size)//扩容{HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);if (ptr != NULL){php->a = ptr;php->capacity *= 2;}}php->a[php->size++] = x;//插入数据adjustup(php->a,php->size-1);  //向上调整}

2. 情况分析

在这里插入图片描述

由图可知目前是一个小堆

情况1

  • 在数组后插入 >=56 的数 例如 100
    在这里插入图片描述

此时依旧为一个小堆，不需要调整，直接插入在数组尾部就可以了

情况2

  • 在数组后插入<56的数 例如 22
    在这里插入图片描述
  • 在圈中22比56小，所以不构成小堆，需要进行向上调整

3. 向上调整算法

1.过程分析

  • 这里以小堆为例

在这里插入图片描述

  • 我们要创建小堆，parent(56)>child(22)，所以要将两者值进行交换

在这里插入图片描述

  • 假设我们并不知道上面的数 例如10 与 新交换后的parent 22 的关系 所以我们需要向上调整

在这里插入图片描述

  • 即将 parent的下标赋给 child ，即22成为新的child下标对应位置，10成为parent下标对应位置 ，此时因为10<22，所以走break不需要调整

2. 临界条件的判断

在这里插入图片描述

  • 当child下标处于0时，parent下标已经越界没有比较的必要了，所以child>0
    就为临界条件

2. pop—— 删除

1.代码

void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{int child = parent * 2 + 1;//假设为左孩子while (child<size){if (child+1<size&&a[child] < a[child + 1])//如果假设不成立，就为右孩子{child++;}if (a[parent] < a[child])//孩子大于父亲{swap(&a[parent], &a[child]);parent = child;child=parent * 2 + 1;}else{break;}}
}
void heappop(HP* php)//删除
{assert(php);assert(php->size > 0);swap(&php->a[0], &php->a[php->size - 1]);php->size--;adjustdown(php->a,0,php->size);//向下调整算法
}

2. 向下调整算法

1. 注意事项

在这里插入图片描述

在这里插入图片描述

若右孩子所对应没有结点，a[child+1]就会越界访问，
所以需要加上限制条件： child+1<size

2. 临界条件

在这里插入图片描述

  • child作为下标存在，n为数据个数，child最多等于n-1

3.TOPK问题

  • N个数，找最大/最小的前k个

这里我们以大堆来举例 寻找最大的前k个
在这里插入图片描述

1.过程分析

在这里插入图片描述

  • 刚开始时，我们需要将首尾互换，并将此时的尾数据删除

在这里插入图片描述

  • 交换parent下标与child下标所对应的值，如图1 2
  • 并将child的下标赋给parent 如 图 2 3

3. create ——建堆

void heapcreate(HP* php, HPDatatype* a, int n)//建堆
{assert(php);php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);if (php->a == NULL){perror("mealloc fail");exit(-1);}memcpy(php->a, a,  sizeof(HPDatatype) * n);int i = 0;for (i = (n - 1 - 1) / 2; i >= 0; i--){adjustdown(php->a, i, n);}}

1.向下调整算法的应用

在这里插入图片描述

我们想创建一个大堆，就必须使左子树是一个大堆及右子树是一个大堆
所以要从倒数第二层开始调整
在这里插入图片描述

4. top—— 取堆顶元素

HPDatatype heaptop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

5. size—— 数据个数

int heapsize(HP* php)//数据个数
{assert(php);assert(php->size > 0);return php->size;
}

6. empty ——判空

bool heapempty(HP* php)//判断是否为空
{assert(php);assert(php->size > 0);return php->size == 0;
}

7. TOPK问题的具体实现

#include "heap.h"
int main()
{HP php;heapinit(&php);int arr[] = {27,15,19,18,28,34,65,49,25,37};int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;for (i = 0; i < sz; i++){heappush(&php, arr[i]);}print(&php);int k = 5;//取前5个数while (k--){printf("%d ", heaptop(&php));heappop(&php);}heapdestroy(&php);return 0;
}

在这里插入图片描述

完整代码

1.heap.h

#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 heapcreate(HP* php, HPDatatype a, int size);
void heapinit(HP* php);//初始化
void heapdestroy(HP* php);//内存销毁
void heappush(HP* php,HPDatatype x);//插入
void heappop(HP* php);//删除
HPDatatype heaptop(HP* php);//堆顶数据
int heapsize(HP* php);//数据个数
bool heapempty(HP* php);//判断是否为空

2.heap.c

#include"heap.h"
//void heapcreate(HP* php, HPDatatype* a, int n)//建堆
//{
//	assert(php);
//	php->a = (HPDatatype*)malloc(sizeof(HPDatatype) * n);
//	if (php->a == NULL)
//	{
//		perror("mealloc fail");
//		exit(-1);
//	}
//	memcpy(php->a, a,  sizeof(HPDatatype) * n);
//	int i = 0;
//	for (i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		adjustdown(php->a, i, n);
//	}
//
//}
void  heapinit(HP* php)//初始化
{assert(php);php->a = (HP*)malloc(sizeof(php) *4);php->size = 0;php->capacity = 4;
}void heapdestroy(HP* php)//内存销毁
{assert(php);free(php->a);php->a = NULL;php->size = 0;php->capacity = 0;
}
void swap(HPDatatype* s1, HPDatatype* s2)
{int tmp = 0;tmp = *s1;*s1 = *s2;*s2 = tmp;
}
//void adjustup(HPDatatype* a, int child)//向上调整算法
//{
//	int parent = (child - 1) / 2;
//	while (child>0)
//	{
//		if (a[parent] >a[child])//以小堆为例
//		{
//			swap(&a[parent], &a[child]);
//			child = parent;
//			parent = (child - 1) / 2;
//	    }
//		else
//		{
//			break;
//		}
//	}
//}
void adjustup(HPDatatype* a, int child)//向上调整算法
{int parent = (child - 1) / 2;while (child > 0){if (a[parent] < a[child])//以大堆为例{swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void heappush(HP* php, HPDatatype x)//插入
{assert(php);if (php->capacity == php->size)//扩容{HPDatatype* ptr = (HPDatatype*)realloc(php->a, sizeof(HPDatatype)*php->capacity * 2);if (ptr != NULL){php->a = ptr;php->capacity *= 2;}}php->a[php->size++] = x;//插入数据adjustup(php->a,php->size-1);  //向上调整}
void adjustdown(HPDatatype* a, int parent,int size)//向下调整算法
{int child = parent * 2 + 1;//假设为左孩子while (child<size){if (child+1<size&&a[child] < a[child + 1])//如果假设不成立，就为右孩子{child++;}if (a[parent] < a[child])//孩子大于父亲{swap(&a[parent], &a[child]);parent = child;child=parent * 2 + 1;}else{break;}}
}
void heappop(HP* php)//删除
{assert(php);assert(php->size > 0);swap(&php->a[0], &php->a[php->size - 1]);php->size--;adjustdown(php->a,0,php->size);//向下调整算法
}
HPDatatype heaptop(HP* php)//取堆顶元素
{assert(php);assert(php->size > 0);return php->a[0];
}void print(HP* php)
{int i = 0;for (i = 0; i < php->size; i++){printf("%d ", php->a[i]);}printf("\n");
}
bool heapempty(HP* php)//判断是否为空
{assert(php);assert(php->size > 0);return php->size == 0;
}int heapsize(HP* php)//数据个数
{assert(php);assert(php->size > 0);return php->size;
}

#include "heap.h"
int main()
{HP php;heapinit(&php);int arr[] = {27,15,19,18,28,34,65,49,25,37};int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;for (i = 0; i < sz; i++){heappush(&php, arr[i]);}print(&php);int k = 5;while (k--){printf("%d ", heaptop(&php));heappop(&php);}heapdestroy(&php);return 0;
}

3.test.c

#include "heap.h"
int main()
{HP php;heapinit(&php);int arr[] = {27,15,19,18,28,34,65,49,25,37};int sz = sizeof(arr) / sizeof(arr[0]);int i = 0;for (i = 0; i < sz; i++){heappush(&php, arr[i]);}print(&php);int k = 5;while (k--){printf("%d ", heaptop(&php));heappop(&php);}heapdestroy(&php);return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.luyixian.cn/news_show_224157.aspx

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

redis哨兵系列1

redis哨兵系列1

需要配合源码一起康~ 9.1 哨兵基本概念 官网手册yyds&#xff1a;https://redis.io/docs/manual/sentinel/ redis主从模式&#xff0c;如果主挂了&#xff0c;需要人工将从节点提升为主节点&#xff0c;通知应用修改主节点的地址。不是很友好&#xff0c;so Redis 2.8之后开…
阅读更多...
C# async / await 用法

C# async / await 用法

目录 一、简介 二、异步等待返回结果 三、异步方法返回类型 四、await foreach 五、Task.Delay 结束 一、简介 await 运算符暂停对其所属的 async 方法的求值&#xff0c;直到其操作数表示的异步操作完成。 异步操作完成后&#xff0c;await 运算符将返回操作的结果&…
阅读更多...
使用STM32CubeMX实现按下按键，电平反转

使用STM32CubeMX实现按下按键，电平反转

需提前学习&#xff1a;使用STM32CubeMX实现LED闪烁 目录 原理图分析 按键部分原理图分析 LED部分原理图分析 STM32CubeMX配置 关于STM32CubeMXSYS的Debug忘记配置Serial Wire处理办法 GPIO配置 LED的GPIO配置 KEY1配置 关于PA0后面这个WKUP是什么&#xff1f; 那么啥…
阅读更多...
利用ogg微服务版将oracle同步到kafka

利用ogg微服务版将oracle同步到kafka

ogg微服务版可以再界面上配置抽取、复制进程&#xff0c;不必进入到shell中进行配置&#xff0c;并且图形化界面可以看到更多信息。 系统架构 源端安装ogg for oracle 19C , 目标端安装ogg for bigdata 21C kafka 2.2 数据库&#xff1a;19C 所有软件安装在同台服务器上&#…
阅读更多...
理解Linux32位机器下虚拟地址到物理地址的转化

理解Linux32位机器下虚拟地址到物理地址的转化

文章目录前言一、基本概念介绍二、虚拟地址到物理地址的转化过程总结前言 简要介绍LINUX32位系统下虚拟地址到物理地址的转化过程。 一、基本概念介绍 在32位机器下&#xff0c;IO的基本单位是块&#xff08;块&#xff1a;4kb),在程序编译成可执行程序时也划分好了以4kb为单…
阅读更多...
JVM【类加载与GC垃圾回收机制】

JVM【类加载与GC垃圾回收机制】

JVM【类加载与GC垃圾回收机制】&#x1f34e;一.JVM&#x1f352;1.1JVM简介&#x1f352;1.2JVM执行流程&#x1f34e;二.JVM运行时数据区&#x1f352;2.1 程序计数器(线程私有)&#x1f352;2.2 栈(线程私有)&#x1f352;2.3 堆(线程共享)&#x1f352;2.4 方法区(线程共享…
阅读更多...
OWASP API SECURITY TOP 10

OWASP API SECURITY TOP 10

目录 1. API 安全风险 2. 细说TOP10 1. Broken Object Level Authorization 2. Broken User Authentication 3 Excessive Data Exposure 4 Lack of Resources & Rate Limiting 5 Broken Function Level Authorization 6 Mass Assignment 7 security misconfigura…
阅读更多...
【原创】使用Golang的电商搜索技术架构实现

【原创】使用Golang的电商搜索技术架构实现

作者&#xff1a;黑夜路人 时间&#xff1a;2022年11月 一、背景&#xff1a; 现在搜索技术已经是非常主流的应用技术&#xff0c;各种优秀的索引开源软件已经很普遍了&#xff0c;比如 Lucene/Solr/Elasticsearch 等等主流搜索索引开源软件&#xff0c;让我们搭建一个优秀的…
阅读更多...
【FLASH存储器系列十】Nand Flash芯片使用指导之一

【FLASH存储器系列十】Nand Flash芯片使用指导之一

目录 1.1 芯片简介 1.2 功能框图 1.3 存储结构 1.4 信号定义 1.5 双平面&#xff08;plane&#xff09;操作 1.6 Die间交错操作 1.7 错误管理 今天以MT29F8G08AJADAWP芯片为例&#xff0c;说明nand flash的操作方法。 1.1 芯片简介 这是一款镁光的容量8Gb&#xff0c;总…
阅读更多...
liunx集成jmeter进行压测实践

liunx集成jmeter进行压测实践

首先liunx环境需要部署jdk 1,获取jmeter免安装包&#xff1a;点击我获取免安装包 2,获取jmeter-manger工具&#xff0c;用于生成报告&#xff0c;日志等 点击我获取工具 3,在服务器上新建一个文件夹存放jmeter&#xff0c;推荐在/usr/local/下面&#xff0c;我这里由于权限问…
阅读更多...
E 排队(排列组合)[牛客小*白月赛61]

E 排队(排列组合)[牛客小*白月赛61]

题面如下&#xff1a; 思路 or 题解&#xff1a; 对于一个长度为 nnn 的 排列组合 如果存在一对 逆序对 (x,y)(x, y)(x,y) xxx 在 yyy 的前面有 n∗(n−1)2\frac{n * (n - 1)}{2}2n∗(n−1)​ 种情况 剩下 n−2n - 2n−2 个位置可以随意填数进去&#xff0c;不会影响到逆序对 …
阅读更多...
狗屎一样的面试官，你遇到过几个？

狗屎一样的面试官，你遇到过几个？

做了几年软件开发&#xff0c;我们都或多或少面试过别人&#xff0c;或者被别人面试过。大家最常吐槽的就是面试造火箭&#xff0c;进厂拧螺丝。今天就来吐槽一下那些奇葩&#xff08;gou&#xff09;一样的面试官 A 那是在我刚工作1年的时候&#xff0c;出去面试前端开发。 那…
阅读更多...
Python编程 元组的创建

Python编程 元组的创建

作者简介&#xff1a;一名在校计算机学生、每天分享Python的学习经验、和学习笔记。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 目录 前言 一.元组知识点 二.元组(tuple) 1.元组介绍(掌握) 2.元组创建(掌握) 3.…
阅读更多...
鉴源论坛 · 观模丨浅谈随机测试

鉴源论坛 · 观模丨浅谈随机测试

作者 | 黄杉 华东师范大学软件工程学院博士 苏亭 华东师范大学软件工程学院教授 首发 | 鉴源论坛 观模 01 什么是随机测试 &#xff08;Random Testing&#xff09; 随机测试是一种使用随机、相互独立的程序输入来对计算机程序进行测试的黑盒软件测试&#xff08;在完全忽…
阅读更多...
Springboot常用参数注解

Springboot常用参数注解

访问路径为http://localhost:8080/ PathVariable GetMapping("/get/{id}/blank/{name}")public Map getValue(PathVariable("id") Integer id,PathVariable("name") String name,PathVariable Map<String,String> kv){Map map new Hash…
阅读更多...
大一新生HTML期末作业 学生个人网页设计作业 HTML5响应式个人简历网站模板 web前端网页制作课作业

大一新生HTML期末作业 学生个人网页设计作业 HTML5响应式个人简历网站模板 web前端网页制作课作业

&#x1f389;精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; ✍️ 作者简介: 一个热爱把逻辑思维转变为代码的技术博主 &#x1f482; 作者主页: 【主页——&#x1f680;获取更多优质源码】 &#x1f393; web前端期末大作业…
阅读更多...
CNN (吴恩达 2021

CNN (吴恩达 2021

week1-2 02_边缘检测例子_哔哩哔哩_bilibili ​ ​ 我们之前在说面部识别介绍过&#xff0c;要识别面部&#xff0c;都是从细微的边缘入手&#xff0c;一层一层聚类&#xff0c;最终实现人脸的识别。神经网络由浅层到深层&#xff0c;分别可以检测出图片的边缘特征 、局部特…
阅读更多...
web前端大一实训 HTML+CSS+JavaScript王者荣耀(60页) web课程设计网页规划与设计 HTML期末大作业 HTML网页设计结课作业

web前端大一实训 HTML+CSS+JavaScript王者荣耀(60页) web课程设计网页规划与设计 HTML期末大作业 HTML网页设计结课作业

&#x1f389;精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; ✍️ 作者简介: 一个热爱把逻辑思维转变为代码的技术博主 &#x1f482; 作者主页: 【主页——&#x1f680;获取更多优质源码】 &#x1f393; web前端期末大作业…
阅读更多...
【MySQL进阶】深入理解B+树索引底层原理

【MySQL进阶】深入理解B+树索引底层原理

【MySQL进阶】深入理解B树索引底层原理 文章目录【MySQL进阶】深入理解B树索引底层原理一、前言——没有索引的查找1、在一个页中的查找2、在很多页中查找3、总结二、索引1、一个简单的索引方案2、InnoDB中的索引方案3、B 树4、聚簇索引5、二级索引6、回表7、联合索引三、InnoD…
阅读更多...
【MySQL数据库笔记 - 进阶篇】（二）索引

【MySQL数据库笔记 - 进阶篇】（二）索引

✍个人博客&#xff1a;https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 &#x1f4da;专栏地址&#xff1a;暂定 &#x1f4dd;视频地址&#xff1a;黑马程序员 MySQL数据库入门到精通 &#x1f4e3;专栏定位&#xff1a;这个专栏我将会整理 B 站黑马程序员的 MySQL…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业