当前位置: 首页 > news >正文

数据结构——堆(C语言)

本篇会解决一下几个问题:
1.堆是什么?
2.如何形成一个堆?
3.堆的应用场景
 

堆是什么?

  • 堆总是一颗完全二叉树
  • 堆的某个节点总是不大于或不小于父亲节点

如图,在小堆中,父亲节点总是小于孩子节点的。

 

如图,在大堆中,父亲节点总是大于孩子节点的。

堆和二叉树还是有很大区别的,堆是用数组来实现的,尽管逻辑结构上是一颗二叉树,但在内存上要比二叉树好,普通的二叉树,你要用链表来存储他们的左右孩子,还要给他们分配空间,但堆只是用数组来表示。

如何形成一个堆?

堆的创建有向上调整和向下调整两种方式。

向上调整:从第一个非叶子节点开始向上调整,一直调整到根节点。

用int a[] ={1,5,3,8,7,6};来做例子,

如图所示,

向下调整:从根节点开始,和左右孩子中小或者大的节点比较,交换,直到小于数组元素。

堆的插入

堆的删除

删除堆是删除堆顶的元素,将堆顶的元素根据最后一个数据一换,然后删除数组中最后一个元素,再进行向下调整算法。

这里想一想为什么要这样???

1.因为堆是有数组来创建的,如果直接删除堆顶的数据,第一个缺点就是会造成移动,从后往前覆盖,这样就会造成一个问题。兄弟节点变成父子节点,而且这样也不能很好的利用数组的优点。

2.如果是交换第一个和最后一个元素,这样有2个优点:

  • 第一个是不会破坏除了堆顶的左右堆的结构。
  • 第二个就是会利用数组的优点,数组读取速度很快,这样每次最后或最小的元素就放在了后面。

堆的时间复杂度

向下调整时间复杂度:

 则要移动节点的总步数为:

向上调整时间复杂度:

则要调整的节点总数为:

堆的应用场景

  1. 堆排序,可以用堆的建立和堆的删除来实现排序,堆排序十分稳定(相同元素的相对位置不会发生交换),而且时间复杂度都是O(N*logN)
  2. TOP-K问题,我们想一想王者荣耀中前100的玩家是怎么实现的,或者专业前10名...问题

1).先回答一下TOP-K问题:即求数据结合中前K个最大的元素或最小的元素,一把情况下数据很大。

2).对于这种场景,首先想到的就是排序,但是:数据非常大,排序就不可取了,因为内存大小的原因,不会全部加载到内存,这时堆就发生了巨大的优势。

思路:利用K个元素建堆,如果是求最大的K个元素,就建立小堆,求最小的K歌元素,就建立大堆。然后用N-K个元素与堆顶元素比较,满足条件就交换。

下面是源码:

void HeapInit(Heap* php)
{assert(php);php->a = NULL;php->size = php->capacity =0;
}void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size =0;
}void Swap(HeapDateType* child, HeapDateType* parent){HeapDateType tmp = *child;*child=  *parent;*parent = tmp;
}void AdjustUp(HeapDateType* a,int child){int parent = (child-1)/2;while(child > 0){if(a[child] < a[parent]){Swap(&a[child],&a[parent]);child = parent;parent = (child-1)/2;}else{break;}
}}void HeapPush(Heap* php,HeapDateType x)
{assert(php);if(php->size == php->capacity){int newCapacity = php->capacity == 0?4:php->capacity*2;HeapDateType* tmp = (HeapDateType*)realloc(php->a,sizeof(HeapDateType)*newCapacity);if(tmp == NULL){perror("realloc fail\n");}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a,php->size-1);
}void HeapPrint(Heap* php)
{assert(php);for(size_t i =0; i<php->size; i++){std::cout << php->a[i] << " ";}std::cout << std::endl;
}void AdjustDown(HeapDateType* a,int n, int parent)
{int child = parent*2+1;while(child < n){if(child+1 < n && a[child+1] < a[child]){child++;}if(a[child] < a[parent]){Swap(&a[child],&a[parent]);parent = child;child = parent*2+1;}else{break;}}
}HeapDateType HeapTop(Heap* php)
{assert(php);assert(php->size > 0);return php->a[0];
}void HeapPop(Heap* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0],&php->a[php->size-1]);--php->size;AdjustDown(php->a,php->size,0);}bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}

 

void HeapSort(int* a, int n)
{//向上调整 O(n*logn)
//  for(size_t i =1; i<n; i++){
//    AdjustUp(a,i);
//  }
////向下调整 O(n)for(int i = (n-2)/2; i>=0; i--){AdjustDown(a,n,i);}//时间复杂度O(N*logN)int end = n-1;while(end > 0){Swap(&a[0],&a[end]);AdjustDown(a,end,0);--end;}
}void PrintTopK(const char* filename,int k)
{FILE* fout = fopen(filename,"r");if(fout == NULL){perror("fopen fail");exit(-1);}int* minHeap = (int*)malloc(sizeof(int)*k);if(minHeap == NULL){perror("malloc fail");exit(-1);}for(int i =0; i<k; i++){fscanf(fout,"%d",&minHeap[i]);}for(int i = (k-2)/2; i>=0; i++){AdjustDown(minHeap,k,0);}int x =0;while(fscanf(fout,"%d",&x)!= EOF){if(x > minHeap[0]){minHeap[0] = x;AdjustDown(minHeap,k,0);}}for(int i =0; i<k; i++){std::cout << minHeap[i] << " ";}std::cout << std::endl;
}

                        

 

相关文章:

数据结构——堆(C语言)

本篇会解决一下几个问题&#xff1a; 1.堆是什么&#xff1f; 2.如何形成一个堆&#xff1f; 3.堆的应用场景 堆是什么&#xff1f; 堆总是一颗完全二叉树堆的某个节点总是不大于或不小于父亲节点 如图&#xff0c;在小堆中&#xff0c;父亲节点总是小于孩子节点的。 如图&a…...

B058-SpringBoot

目录 springboot概念与作用入门案例springboot运行方式热部署配置文件Profile多环境支持整合测试-springboot-testSpringboot-web1.返回json数据2.返回页面&#xff08;模板技术&#xff09;thymeleaf1.导入thymeleaf依赖2.模板文件3.controller4.启动类 SSM整合1.导包2.项目目…...

龙迅LT9611UXC 2PORT MIPICSI/DSI转HDMI(2.0)转换器+音频,内置MCU

龙迅LT9611UXC 1.描述&#xff1a; LT9611UXC是一个高性能的MIPI DSI/CSI到HDMI2.0转换器。MIPI DSI/CSI输入具有可配置的单 端口或双端口&#xff0c;1高速时钟通道和1~4高速数据通道&#xff0c;最大2Gbps/通道&#xff0c;可支持高达16Gbps的总带 宽。LT9611UXC支持突发…...

STM32存储左右互搏 I2C总线读写FRAM MB85RC1M

STM32存储左右互搏 I2C总线读写FRAM MB85RC1M 在较低容量存储领域&#xff0c;除了EEPROM的使用&#xff0c;还有铁电存储器FRAM的使用&#xff0c;相对于EEPROM, 同样是非易失性存储单元&#xff0c;FRAM支持更高的访问速度&#xff0c; 其主要优点为没有EEPROM持续写操作跨页…...

1340. 跳跃游戏 V;2039. 网络空闲的时刻;2767. 将字符串分割为最少的美丽子字符串

1340. 跳跃游戏 V 核心思想&#xff1a;动态规划记忆化搜索。定义dfs(i)&#xff0c;表示从i开始最多可以访问多少个下标&#xff0c;然后统计往左跳和往右边跳的最大值&#xff0c;思路其实比较简单&#xff0c;但是代码我感觉还是不太好想。 2039. 网络空闲的时刻 核心思想…...

ElementUI之CUD+表单验证

目录 前言&#xff1a; 增删改查 表单验证 前言&#xff1a; 继上篇博客来写我们的增删改以及表单验证 增删改查 首先先定义接口 数据样式&#xff0c;我们可以去elementUI官网去copy我们喜欢的样式 <!-- 编辑窗体 --><el-dialog :title"title" :visib…...

Linux:nginx---web文件服务器

我这里使用的是centos7系统 nginx源码包安装 Linux&#xff1a;nginx基础搭建&#xff08;源码包&#xff09;_鲍海超-GNUBHCkalitarro的博客-CSDN博客https://blog.csdn.net/w14768855/article/details/131445878?ops_request_misc%257B%2522request%255Fid%2522%253A%25221…...

go 端口转发 代理V2 --chatGPT

问&#xff1a;broker(localPort, targetPort), 实现远程访问localPort的http代理转发到目标机器 gpt: 要实现一个简单的 HTTP 代理服务器&#xff0c;你可以使用 Go 的 net/http 包来处理 HTTP 请求和响应。以下是一个示例&#xff0c;演示如何创建一个 HTTP 代理服务器将本地…...

idea环境下如何打包可运行jar?

工作中有时候偶尔写一些工具类、小程序&#xff0c;可是java程序员制作一个可运行jar实在折腾&#xff0c;利用idea开发环境&#xff0c;可以快速打包自己的可运行jar。具体怎么操作呢&#xff1f; 创建一个空白的java项目并完成自己的程序开发 完成java代码&#xff1a; /**…...

基于FFmpeg的Android播放器

基于FFmpeg的Android播放器 文章目录 基于FFmpeg的Android播放器1. 前言2. 编译相关组件库3. 解码器4. 解码流程5. 音频输出6. 视频输出&#xff08;需要优化&#xff09; 1. 前言 FFmpeg是一个最有名的开源的编解码库&#xff0c;实现了通常的编解码逻辑。它还能够根据平台特…...

osgPBR(十五)镜面IBL--查看不同级别的HDR环境贴图

首先&#xff0c;设置可以使用Mipmap&#xff0c;启用三线性过滤&#xff0c;设置最大级别和最小级别 osg::ref_ptr<osg::TextureCubeMap> tcm new osg::TextureCubeMap; tcm->setTextureSize(128, 128);tcm->setFilter(osg::Texture::MIN_FILTER, osg::Texture:…...

Docker的学习记录

Docker是一个被广泛使用的开源容器引擎&#xff0c;基于Go语言&#xff0c;遵从Apache2.0协议开源。 docker的三个概念&#xff1a;容器、镜像和仓库。 镜像&#xff08;Image&#xff09;&#xff1a;镜像是Docker中的一个模板。通过 Docker镜像 来创建 Docker容器&#xff…...

Android Jetpack组件架构:ViewModel的原理

Android Jetpack组件架构&#xff1a;ViewModel的原理 导言 本篇文章是关于介绍ViewModel的&#xff0c;由于ViewModel的使用还是挺简单的&#xff0c;这里就不再介绍其的基本应用&#xff0c;我们主要来分析ViewModel的原理。 ViewModel的生命周期 众所周知&#xff0c;一般…...

数据分析(python)学习笔记1.0

《利用Python进行数据分析》(原书第2版) 《利用Python进行数据分析》(原书第2版) 《利用Python进行数据分析》(原书第2版) 社区和会议 除了网络搜索,科学、数据相关的Python邮件列表对于解决问题也非常有帮助。可以看看下列邮件列表: pydata:与数据分析和pandas相…...

SW免安装的toolbox只读问题

把SOLIDWORKSDATA 整体复制到另外的目录&#xff0c;然后这里设置目录位置。不然原始位置有只读属性...

nodejs在pdf中绘制表格

需求 之前我已经了解过如何在pdf模板中填写字段了 nodejs根据pdf模板填入中文数据并生成新的pdf文件https://blog.csdn.net/ArmadaDK/article/details/132456324 但是当我具体使用的时候&#xff0c;我发现我的模板里面有表格&#xff0c;表格的长度是不固定的&#xff0c;所…...

使用不同尺寸的传感器拍照时,怎么保证拍出同样视场范围的照片?

1、问题背景 使用竞品机做图像效果对比时&#xff0c;我们通常都会要求拍摄的照片要视场范围一致&#xff0c;这样才具有可比性。之前我会考虑用同样焦距、同样分辨率的设备去拍照对比就可以了&#xff0c;觉得相机的视场范围只由镜头焦距来决定。 但如果对于不同尺寸的传感器…...

01-工具篇-windows与linux文件共享

一般来说绝大部分PC上装的系统均是windows&#xff0c;为了开发linux程序&#xff0c;会在PC上安装一个Vmware的虚拟机&#xff0c;在虚拟机上安装ubuntu18.04&#xff0c;由于windows上的代码查看软件、浏览器&#xff0c;通信软件更全&#xff0c;我们想只用ubuntu进行编译&a…...

医疗实施-住院流程详解

住院就诊流程详解 1.病人入院登记2.病人进入病区3.医生操作病人4.医嘱录入与审核执行5. 医嘱收费前在对应业务系统的操作5.1.药物医嘱5.2.检查检验医嘱5.3.手术医嘱 6.住院医嘱费用的产生7. 医嘱收费后在对应业务系统的操作8. 病人出院 这篇文章是基于我的文章《医疗实施-住院就…...

本地连接服务器 jupyter notebook

本地连接服务器 jupyter notebook 一、前提工作二、服务器操作三、Windows 操作 一、前提工作 准备一台Linux云服务器新建一个用户&#xff0c;并切换到此用户安装 Anaconda 二、服务器操作 远程服务器上安装和配置 Jupyter Notebook&#xff1a; pip3 install jupyter接着…...

Android 使用Kotlin封装RecyclerView

文章目录 1.概述2.运行效果图3.代码实现3.1 扩展RecyclerView 3.2 扩展Adapter3.3 RecyclerView装饰绘制3.3.1 以图片实现分割线3.3.2 画网格线3.3.3空白的分割线3.3.4 不同方向上的分割线 3.4 使用方法 1.概述 在一个开源项目上看到了一个Android Kotlin版的RecyclerView封装…...

WPF 实现点击按钮跳转页面功能

方法1. 配置环境 首先添加prism依赖项&#xff0c;配置好所有文件。需要配置的有两个文件&#xff1a;App.xaml.cs和App.xaml App.xaml.cs using System.Data; using System.Linq; using System.Threading.Tasks; using System.Windows;namespace PrismDemo {/// <summa…...

关于http网络通信数据包封装的过程

当我们谈论网络通信时&#xff0c;数据在从源到目的地传输的过程中会通过多层网络协议。在每一层&#xff0c;都会添加一些头信息&#xff08;和有时尾信息&#xff09;来帮助处理和传输数据。这个过程被称为"封装"&#xff08;Encapsulation&#xff09;。简单来说&…...

关于RabbitMQ你了解多少?

关于RabbitMQ你了解多少&#xff1f; 文章目录 关于RabbitMQ你了解多少&#xff1f;基础篇同步和异步MQ技术选型介绍和安装数据隔离SpringAMQP快速入门Work queues交换机Fanout交换机Direct交换机Topic交换机 声明队列和交换机MQ消息转换器 高级篇消息可靠性问题发送者的可靠性…...

Vulkan-着色器及编译SPIR-V

1.着色器模块介绍 Vulkan着色器代码一定要用字节码格式&#xff0c;而不是人类可读的语法如GLSL和HLSL。这个字节码就是SPIR-V&#xff0c;设计用于Vulkan和OpenCL。这是一个可以用于编写图形和计算着色器的格式&#xff0c;但是我们主要关注的是Vulkan的图形管线。使用字节码格…...

从MVC到DDD,该如何下手重构?

作者&#xff1a;付政委 博客&#xff1a;bugstack.cn 沉淀、分享、成长&#xff0c;让自己和他人都能有所收获&#xff01;&#x1f604; 大家好&#xff0c;我是技术UP主小傅哥。多年的 DDD 应用&#xff0c;使我开了技术的眼界&#xff01; MVC 旧工程腐化严重&#xff0c;…...

论文阅读:基于隐马尔可夫模型的蛋白质多序列比对方法研究

本文来自chatpaper Basic Information: • Title: Research on Protein Multiple Sequence Alignment Method Based on Hidden Markov Model (基于隐马尔可夫模型的蛋白质多序列比对方法研究) • Authors: Zhan Qing • Affiliation: Harbin Institute of Technology (哈尔滨工…...

Vim同时打开多个文件

分屏模式 在 Vim 中&#xff0c;可以同时打开多个文件并使用分屏模式来查看它们。以下是一些常见的方法和命令&#xff1a; 在启动 Vim 时打开多个文件 使用 -o 选项打开文件并水平分屏&#xff1a; vim -o file1.txt file2.txt使用 -O 选项打开文件并垂直分屏&#xff1a; v…...

SpringCloudStreamkafka接收jsonarray字符串失败

文章目录 场景现象问题处理 场景现象 kafka作为消息队列&#xff0c;作为前端设备数据到后端消费的渠道&#xff0c;也被多个不同微服务消费一个服务与前端边缘计算设备建立socket消息&#xff0c;接收实时交通事件推送&#xff0c;再将事件发送到kafka里面。此处使用的是Spri…...

面向对象特性分析大全集

面向对象特性分析 先进行专栏介绍 面向对象总析前提小知识分类浅析封装浅析继承浅析多态面向对象编程优点abc 核心思想实际应用总结 封装概念详解关键主要目的核心思想优点12 缺点12 Java代码实现封装特性 继承概念详解语法示例关键主要目的核心思想优点12 缺点12 Java代码实现…...

一流的购物网站建设/国际最新新闻

文章目录1 introduction2 evaluation题目&#xff1a;TENET: A Framework for Modeling Tensor Dataflow Based on Relation-centric Notation时间&#xff1a;2021会议&#xff1a;ISCA研究机构&#xff1a;北大 1 introduction 如何描述数据流&#xff1f; 本文总结了三种形…...

WordPress来必力/天津seo培训

http://blog.sina.com.cn/s/blog_6714fba701018pip.html 1&#xff0c;/etc/hosts&#xff0c;主机名何ip配置文件。 hosts---The static table lookup for host name(主机名查询静态表) linux 的/etc/hosts是配置ip地址和其对应主机名的文件&#xff0c;这里可以记录本机的或…...

公司云网站建设/百度统计怎么使用

先看下源代码&#xff0c;预想从1至N总取出所有能被a或b整除的正整数之和&#xff0c;为了利用go语言的并行优势&#xff0c;特使用goroute特性来实现&#xff0c;同时使用普通顺序计算进行效率比较分析 package changoimport ( "fmt" "time")func get…...

公司网站能自己做二维码/b站免费建网站

题目大意&#xff1a;将一个1~n的环形排列变成升序的&#xff0c;最少需要几次操作&#xff1f;每次操作可以交换任意两个数字。 题目分析&#xff1a;枚举出1的位置。贪心策略&#xff1a;每次操作都保证至少一个数字交换到正确位置上。 # include<iostream> # include&…...

网站有二级域名做竞价/手游推广渠道和推广方式

MRT(MODIS Reprojection Tool)简介&#xff1a;MODIS的全称为中分辨率成像光谱仪(Moderate-Resolution Imaging Spectroradiometer)&#xff0c;是搭载在Terra和Aqua卫星上的一个重要的传感器。MRT是一种针对MODIS数据的处理工具。它可以帮助用户把MODIS影像重新投影到更为标准…...

公司自己做网站流程和备案/电子商务

从这篇文章起&#xff0c;我们看看Vue3.0的响应式部分源码。这部分reactive方法是核心&#xff0c;reactive方法如下&#xff1a; export function reactive<T extends object>(target: T): UnwrapNestedRefs<T> export function reactive(target: object) {// if…...