数据结构 小顶堆建堆过程 构建过程

2024-05-03 00:58

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

【一】简介

  • 最小堆是一棵完全二叉树,非叶子结点的值不大于左孩子和右孩子的值。本文以图解的方式,说明最小堆的构建、插入、删除的过程。搞懂最小堆的相应知识后,最大堆与此类似。
  • 最小堆示例:

 

【二】最小堆的操作

最小堆的构建:
      初始数组为:9,3,7,6,5,1,10,2

      按照完全二叉树,将数字依次填入。

      填入完成后,从最后一个非叶子结点(本示例为数字6的节点)开始调整。

根据性质,小的数字往上移动;至此,第1次调整完成。

      注意,被调整的节点,还有子节点的情况,需要递归进行调整。

      第二次调整,是数字6的节点数组下标小1的节点(比数字6的下标小1的节点是数字7的节点),

以下是本示例的图解:

注意:数字9的节点 将和 数字1的节点 发生对调,对调后,需要递归进行调整,请一定注意。

 

 

  • 最小堆的元素插入 【插入到该二叉树的最后一个节点,再调整】

以上个最小堆为例,插入数字0。

       数字0的节点首先加入到该二叉树最后的一个节点,依据最小堆的定义,自底向上,递归调整。

       以下是插入操作的图解:

 

 

  • 最小堆的节点删除【是把根节点删除,最后一个叶子节点放到根节点上,再调整】

对于最小堆和最大堆而言,删除是针对于根节点而言。

       对于删除操作,将二叉树的最后一个节点替换到根节点,然后自顶向下,递归调整。

       以下是图解:

 

【三】有一类常见的面试问题:

如何从一个存有10亿个数字的文档中获取到最大的10个数,计算机内存只有1M?

考虑10亿个数据很多,一次性无法装到我们的计算内存中,
采用常用的排序算法,可能也是不好进行操作,数据量很大,
这个地方可以想到可以才用小顶堆来解决这个问题。

1、让计算机去io读取文件
2、把读取出来的数据去构建一个包含10个元素的小顶堆
3、构建完成后,每次从文件中读取出来的一个数字和堆顶的元素进行比较,
如果比堆顶元素小,就直接丢弃或者跳过。如果读取出来的数据比堆顶元素大,
那么就可以用这个元素替代堆顶元素,进行调整小顶堆。这个算法的时间复杂度是O((100亿-1000)log(1000)),即O((N-M)logM),空间复杂度是M

转自:https://blog.csdn.net/wenge1477/article/details/101797674

这篇关于数据结构 小顶堆建堆过程 构建过程的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

使用Python构建一个Hexo博客发布工具

《使用Python构建一个Hexo博客发布工具》虽然Hexo的命令行工具非常强大,但对于日常的博客撰写和发布过程,我总觉得缺少一个直观的图形界面来简化操作,下面我们就来看看如何使用Python构建一个... 目录引言Hexo博客系统简介设计需求技术选择代码实现主框架界面设计核心功能实现1. 发布文章2. 加

PyInstaller打包selenium-wire过程中常见问题和解决指南

《PyInstaller打包selenium-wire过程中常见问题和解决指南》常用的打包工具PyInstaller能将Python项目打包成单个可执行文件,但也会因为兼容性问题和路径管理而出现各种运... 目录前言1. 背景2. 可能遇到的问题概述3. PyInstaller 打包步骤及参数配置4. 依赖

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

C# WinForms存储过程操作数据库的实例讲解

《C#WinForms存储过程操作数据库的实例讲解》:本文主要介绍C#WinForms存储过程操作数据库的实例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、存储过程基础二、C# 调用流程1. 数据库连接配置2. 执行存储过程(增删改)3. 查询数据三、事务处

JSON Web Token在登陆中的使用过程

《JSONWebToken在登陆中的使用过程》:本文主要介绍JSONWebToken在登陆中的使用过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录JWT 介绍微服务架构中的 JWT 使用结合微服务网关的 JWT 验证1. 用户登录,生成 JWT2. 自定义过滤

java中使用POI生成Excel并导出过程

《java中使用POI生成Excel并导出过程》:本文主要介绍java中使用POI生成Excel并导出过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录需求说明及实现方式需求完成通用代码版本1版本2结果展示type参数为atype参数为b总结注:本文章中代码均为

一文详解如何从零构建Spring Boot Starter并实现整合

《一文详解如何从零构建SpringBootStarter并实现整合》SpringBoot是一个开源的Java基础框架,用于创建独立、生产级的基于Spring框架的应用程序,:本文主要介绍如何从... 目录一、Spring Boot Starter的核心价值二、Starter项目创建全流程2.1 项目初始化(

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

SpringCloud之LoadBalancer负载均衡服务调用过程

《SpringCloud之LoadBalancer负载均衡服务调用过程》:本文主要介绍SpringCloud之LoadBalancer负载均衡服务调用过程,具有很好的参考价值,希望对大家有所帮助,... 目录前言一、LoadBalancer是什么?二、使用步骤1、启动consul2、客户端加入依赖3、以服务