最小堆最大堆
文章目录
- 最小堆、最大堆
- 最小堆(Min-Heap)
- 最大堆(Max-Heap)
- 堆的主要操作及时间复杂度
- 堆的常见应用
- 堆的数组表示
- 大根堆--堆排序
最小堆、最大堆
最小堆(Min-Heap)和最大堆(Max-Heap) 是堆(Heap)数据结构的两种类型,它们都是完全二叉树,并且满足特定的堆性质。堆是一种优先级队列实现,通常用于高效地找出最值(最大或最小值)。堆的每个父节点都和其子节点满足一定的关系。
最小堆(又称:小根堆,小顶堆)
最大堆(又称:大根堆,大顶堆)
最小堆(Min-Heap)
最小堆1/ \2 3/ \ \5 6 4
- 定义:在最小堆中,父节点的值总是小于或等于其子节点的值。
- 性质:堆顶(根节点)的元素是整个堆中最小的元素。
- 结构:因为是完全二叉树,每次插入或删除时,堆结构会通过比较节点来维持堆性质。
插入和删除的规则:
- 插入:将新元素放在堆的末尾,然后通过“向上调整”(上浮)来恢复堆的性质,即与父节点比较,如果新元素小于父节点,就交换位置,直到符合堆的性质。
- 删除最小元素:将堆顶元素(最小值)移除,然后将最后一个元素移到堆顶,再通过“向下调整”(下沉)将其与子节点比较,直到恢复堆的性质。
最大堆(Max-Heap)
最大堆6/ \5 4/ \ \1 2 3
- 定义:在最大堆中,父节点的值总是大于或等于其子节点的值。
- 性质:堆顶(根节点)的元素是整个堆中最大的元素。
- 结构:同样是完全二叉树,插入和删除操作遵循与最小堆类似的方式,只是比较方向相反。
插入和删除的规则:
- 插入:将新元素放在堆的末尾,然后通过“向上调整”(上浮)来恢复堆的性质,即与父节点比较,如果新元素大于父节点,就交换位置,直到符合堆的性质。
- 删除最大元素:将堆顶元素(最大值)移除,然后将最后一个元素移到堆顶,再通过“向下调整”(下沉)将其与子节点比较,直到恢复堆的性质。
堆的主要操作及时间复杂度
- 插入元素:
O(log n),因为插入后可能需要调整堆的性质,最坏情况下需要从新元素的位置一直调整到根节点,最多经过堆的高度,即log n次比较和交换。 - 删除堆顶元素(最值):
O(log n),删除堆顶元素后需要调整堆的性质,类似插入操作,最多需要log n次比较和交换。 - 获取堆顶元素(最值):
O(1),堆顶元素始终是最小堆的最小值或最大堆的最大值,直接读取即可。
堆的常见应用
- 优先队列:堆用于实现优先级队列,使得能够高效地获取优先级最高或最低的元素。
- 排序算法:
- 堆排序(Heap Sort):通过构建最大堆或最小堆来实现排序,堆排序的时间复杂度为
O(n log n),并且可以原地排序。
- 堆排序(Heap Sort):通过构建最大堆或最小堆来实现排序,堆排序的时间复杂度为
- 寻找前 k 大或前 k 小元素:可以使用大小为
k的最小堆(用于前 k 大)或最大堆(用于前 k 小)来高效寻找前 k 个特定元素。 - 图算法:
- Dijkstra 算法:用于单源最短路径算法,堆能够高效地维护未访问节点的最短路径。
- Prim 算法:用于生成最小生成树,同样需要使用堆来维护当前可访问的最小边。
堆的数组表示
堆可以使用数组来实现,这是由于堆的完全二叉树结构具备的特性使得它可以映射到一个一维数组中。
节点索引规则
假设堆中某个节点位于数组的索引 i 处(i 是从 0 开始计数),那么:
- 父节点索引:节点
i的父节点位于索引(i - 1) / 2(向下取整)。 - 左子节点索引:节点
i的左子节点位于索引2 * i + 1。 - 右子节点索引:节点
i的右子节点位于索引2 * i + 2。
大根堆–堆排序
public static void heapSort(int[] arr) {if (arr == null || arr.length <= 1) return;// 构建大顶堆for (int i = (arr.length - 1) / 2; i >= 0; i--) {heapify(arr, i, arr.length);}// 堆排序int len = arr.length;while (len > 1) {// 理解成删除堆中一个元素 删堆顶元素 然后将最后一个元素放到堆顶 然后重新调整堆swap(arr, 0, len - 1); // 将堆顶元素与最后一个元素交换len--; // 因为数组后面的元素已经排序完成heapify(arr, 0, len); // 调整堆}
}// 调整堆
private static void heapify(int[] arr, int i, int len) {while (true) {int maxPos = i; // 假设当前节点是最大值int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;if (leftChild < len && arr[leftChild] > arr[maxPos]) {maxPos = leftChild; // 如果左子节点大于当前节点 更新最大值位置}if (rightChild < len && arr[rightChild] > arr[maxPos]) {maxPos = rightChild;}if (maxPos == i) break;swap(arr, i, maxPos);i = maxPos;}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}
为什么从 (arr.length - 1) / 2 开始向上遍历?
假设堆中有 n 个元素,这些元素在数组中的索引是从 0 到 n-1。完全二叉树的特性决定了:
- 叶子节点不需要进行任何调整,因为它们没有子节点,不需要堆化。
- 只有非叶子节点需要进行
heapify操作,即调整节点的位置,使其符合大顶堆的性质。
用数组表示的完全二叉树中:
- 叶子节点的索引:位于
n / 2到n-1之间。 - 非叶子节点的索引:位于
0到(n/2 - 1)之间。
为什么要进行 heapify?
heapify 是堆调整操作的核心,用来维护堆的性质。具体步骤如下:
- 假设节点
i的子树已经是堆,但节点i本身可能不满足堆的性质(例如,节点i比其子节点中的某一个值要小)。 - 通过
heapify,我们将节点i与其子节点中较大的那个进行交换,然后递归地对交换后的位置继续进行调整,直到该子树成为一个合法的堆。
❤觉得有用的可以留个关注~❤
相关文章:
最小堆最大堆
文章目录 最小堆、最大堆最小堆(Min-Heap)最大堆(Max-Heap)堆的主要操作及时间复杂度堆的常见应用堆的数组表示大根堆--堆排序 最小堆、最大堆 最小堆(Min-Heap)和最大堆(Max-Heap)…...
华为 HCIP-Datacom H12-821 题库 (10)
有需要题库的可以看主页置顶 V群进行学习交流 1.缺省情况下,BGP 对等体邻接关系的保持时间是多少秒? A、120 秒 B、60 秒 C、10 秒 D、180 秒 答案:D 解析: BGP 存活消息每隔 60 秒发一次,保持时间“180 秒” 2.缺省…...
如何利用命令模式实现一个手游后端架构?
命令模式的原理解读 命令模式的英文翻译是 Command Design Pattern。在 GoF 的《设计模式》一书中,它是这么定义的: The command pattern encapsulates a request as an object, thereby letting us parameterize other objects with different reques…...
ThreadLocal 释放的方式有哪些
ThreadLocal基础概念:IT-BLOG-CN ThreadLocal是Java中用于在同一个线程中存储和隔离变量的一种机制。通常情况下,我们使用ThreadLocal来存储线程独有的变量,并在任务完成后通过remove方法清理这些变量,以防止内存泄漏。然而&…...
监控-zabbix
1运维监控 是指对计算机系统、网络、服务器等关键IT基础设施进行实时监控,以确保系统的稳定运行和及时发现潜在问题 2老监控框架(不会用但需要知道) Cacti: Cacti是一款基于PHP、MySQL开发的网络流量监测图形分析工具。主要监…...
设计模式 解释器模式(Interpreter Pattern)
文章目录 解释器模式简绍解释器模式的结构优缺点UML图具体代码实现Context 数据实体类,可以包含一些方法Abstract Expression 创建接口方法Terminal Expression 对数据简单处理Non-Terminal Expression 同样实现抽象接口方法Client(客户端) 调…...
Linux echo命令讲解及与重定向符搭配使用方法,tail命令及日志监听方式详解
echo echo具有回声,回响的意思,在linux系统中echo一般可以输出指定字符或用于命令执行 echo命令的用法为 echo 输出字符串 或 echo 命令 若参数为字符串则进行字符串输出,注意若字符串中含空格最好将其用引号括起,防止echo命…...
Linux网络:总结协议拓展
1. TCP/IP四层模型总结 2. 网络协议拓展 DNS协议(地址解析协议) TCP/IP使用IP地址和端口号来确定网络中一台主机的一个程序。 但是这样标定不方便记忆,于是开始引出主机名(字符串),使用hosts文件来描述…...
去除恢复出厂设置中UI文字显示
文章目录 需求场景 一、代码跟踪与分析在线文字搜索RK平台本地源码搜索实际测试验证代码推理 二、实现方案三、延伸知识四、知识总结 需求 需求:去除恢复出厂设置中UI文字显示 场景 Android 相关产品各种方向旋转、强制横竖屏等需求,导致在恢复出厂设…...
《高校教育管理》
《高校教育管理》为中文社会科学引文索引(CSSCI)来源期刊、北大中文核心期刊、RCCSE中国核心学术期刊、人大“复印报刊资料”重要转载来源期刊,是江苏大学主办,中国高等教育管理研究会协办的全国性高等教育管理专业期刊。 ISSN 1…...
全国计算机二级考试C语言篇4——选择题
运算符与表达式 1.赋值的正确写法 赋值操作是一个很常见的操作,但是赋值操作也有一些需要注意的地方。赋值操作是将一个表达式的值赋给一个变量的过程。在C语言中,赋值操作符是""。结合性从右到左,不控制求值顺序。 下面是几种C语言…...
数据结构————哈希表
哈希表(Hash table),也被称为散列表,是一种根据关键值(Key value)而直接进行访问的数据结构。它通过把关键值映射到表中的一个位置来访问记录,从而加快查找的速度。这个映射函数被称为散列函数或…...
element select + tree
element select tree的使用 <template slot"action1" slot-scope"text, record, index"><el-select v-model"record.tagValue" multiple placeholder"请选择":filter-method"(e) > filterTree(e, index)" filt…...
LeetCode之矩阵
36. 有效的数独 class Solution {// 方法 isValidSudoku 接收一个字符二维数组 board,表示数独棋盘,返回是否有效public boolean isValidSudoku(char[][] board) {// 创建三个二维数组来记录每一行、列和子框中数字的出现次数int[][] rows new int[9][…...
Windows文件系统介绍与基本概念解析
1. 引言 1.1 什么是文件系统 文件系统是一种管理和组织计算机存储设备上文件和文件夹的方法。它提供了文件的创建、读取、写入、删除等操作,并负责文件在存储设备上的存储和访问。 在操作系统中,文件系统是一个重要的组成部分,它使得用户可以方便地使用计算机存储设备来存…...
使用 Apache POI 实现 Java Word 模板占位符替换功能
使用 Apache POI 实现 Java Word 模板占位符替换功能 在日常开发中,我们经常会遇到生成 Word 文档的需求,特别是在需要从模板导出 Word 文件时,比如生成合同、报告等。通过使用模板,开发者可以减少重复的工作,将预定义…...
第三届人工智能与智能信息处理国际学术会议(AIIIP 2024)
目录 大会介绍 基本信息 合作单位 主讲嘉宾 会议组委 征文主题 参会方式 会议日程 中国-天津 | 2024年10月25-27日 | 会议官网:www.iiip.net 大会介绍 第三届人工智能与智能信息处理国际学术会议(AIIIP 2024)将于202…...
【动手学深度学习】04 数据操作 + 数据预处理(个人向笔记)
数据操作 N维数组是机器学习和神经网络的主要数据结构其中 2-d 矩阵中每一行表示每一行表示一个样本 当维度来到三维的时候则可以表示成一张图片,再加一维就可以变成多张图片,再加一维则可以变成一个视频 访问元素 冒号表示从冒号左边的元素到冒号右…...
本地搭建 Whisper 语音识别模型
Whisper 是由 OpenAI 开发的一款强大的语音识别模型,具有出色的多语言处理能力。搭建和使用 Whisper 模型可以帮助您将音频内容转换为文本,这在语音转写、语音助手、字幕生成等应用中都具有广泛的用途。本指南将对如何在本地环境中搭建 Whisper 语音识别…...
数据集成-缝合一套数据仓库Infra的臆想
一、数据集成当前困境 目前数据集成基础设施建设仅一个单一数据库,无法很好支持上层应用的建设步骤,继续采用当前设施跟随产品的策略,数据产品开发受限巨大,从目前实施的几个产品看,存在以下主要问题: 功能…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信
文章目录 Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket(服务端和客户端都要)2. 绑定本地地址和端口&#x…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
