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

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

相关文章

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、以服务

使用Python和python-pptx构建Markdown到PowerPoint转换器

《使用Python和python-pptx构建Markdown到PowerPoint转换器》在这篇博客中,我们将深入分析一个使用Python开发的应用程序,该程序可以将Markdown文件转换为Pow... 目录引言应用概述代码结构与分析1. 类定义与初始化2. 事件处理3. Markdown 处理4. 转

Oracle存储过程里操作BLOB的字节数据的办法

《Oracle存储过程里操作BLOB的字节数据的办法》该篇文章介绍了如何在Oracle存储过程中操作BLOB的字节数据,作者研究了如何获取BLOB的字节长度、如何使用DBMS_LOB包进行BLOB操作... 目录一、缘由二、办法2.1 基本操作2.2 DBMS_LOB包2.3 字节级操作与RAW数据类型2.

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3