力扣labuladong——一刷day94
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
- 前言
- `二叉堆(Binary Heap)没什么神秘,性质比二叉搜索树 BST 还简单。其主要操作就两个,sink(下沉)和 swim(上浮),用以维护二叉堆的性质。其主要应用有两个,首先是一种排序方法「堆排序」,第二是一种很有用的数据结构「优先级队列」`
- 一、二叉堆
前言
二叉堆(Binary Heap)没什么神秘,性质比二叉搜索树 BST 还简单。其主要操作就两个,sink(下沉)和 swim(上浮),用以维护二叉堆的性质。其主要应用有两个,首先是一种排序方法「堆排序」,第二是一种很有用的数据结构「优先级队列」
一、二叉堆
public class MaxPQ<Key extends Comparable<Key>> {// 存储元素的数组private Key[] pq;// 当前 Priority Queue 中的元素个数private int size = 0;public MaxPQ(int cap) {// 索引 0 不用,所以多分配一个空间pq = (Key[]) new Comparable[cap + 1];}/* 返回当前队列中最大元素 */public Key max() {return pq[1];}/* 插入元素 e */public void insert(Key e) {...}/* 删除并返回当前队列中最大元素 */public Key delMax() {...}/* 上浮第 x 个元素,以维护最大堆性质 */private void swim(int x) {...}/* 下沉第 x 个元素,以维护最大堆性质 */private void sink(int x) {...}/* 交换数组的两个元素 */private void swap(int i, int j) {Key temp = pq[i];pq[i] = pq[j];pq[j] = temp;}/* pq[i] 是否比 pq[j] 小? */private boolean less(int i, int j) {return pq[i].compareTo(pq[j]) < 0;}/* 还有 left, right, parent 三个方法 */public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅,省略上文给出的代码部分...private void swim(int x) {// 如果浮到堆顶,就不能再上浮了while (x > 1 && less(parent(x), x)) {// 如果第 x 个元素比上层大// 将 x 换上去swap(parent(x), x);x = parent(x);}}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅,省略上文给出的代码部分...private void sink(int x) {// 如果沉到堆底,就沉不下去了while (left(x) <= size) {// 先假设左边节点较大int max = left(x);// 如果右边节点存在,比一下大小if (right(x) <= size && less(max, right(x)))max = right(x);// 结点 x 比俩孩子都大,就不必下沉了if (less(max, x)) break;// 否则,不符合最大堆的结构,下沉 x 结点swap(x, max);x = max;}}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅,省略上文给出的代码部分...public void insert(Key e) {size++;// 先把新元素加到最后pq[size] = e;// 然后让它上浮到正确的位置swim(size);}public class MaxPQ <Key extends Comparable<Key>> {// 为了节约篇幅,省略上文给出的代码部分...public Key delMax() {// 最大堆的堆顶就是最大元素Key max = pq[1];// 把这个最大元素换到最后,删除之swap(1, size);pq[size] = null;size--;// 让 pq[1] 下沉到正确位置sink(1);return max;}
}}}}}相关文章:
力扣labuladong——一刷day94
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言二叉堆(Binary Heap)没什么神秘,性质比二叉搜索树 BST 还简单。其主要操作就两个,sink(下沉…...
Vim 是一款强大的文本编辑器,广泛用于 Linux 和其他 Unix 系统。以下是 Vim 的一些基本用法
Vim 是一款强大的文本编辑器,广泛用于 Linux 和其他 Unix 系统。以下是 Vim 的一些基本用法: 打开文件: vim filename 基本移动: 使用箭头键或 h, j, k, l 分别向左、下、上、右移动。Ctrl f: 向前翻页。Ctrl b: 向后翻页。…...
软件工程:黑盒测试等价分类法相关知识和多实例分析
目录 一、黑盒测试和等价分类法 1. 黑盒测试 2. 等价分类法 二、黑盒测试等价分类法实例分析 1. 工厂招工年龄测试 2. 规定电话号码测试 3. 八位微机测试 4. 三角形判断测试 一、黑盒测试和等价分类法 1. 黑盒测试 黑盒测试就是根据被测试程序功能来进行测试…...
stable-diffusion 学习笔记
必看文档: 万字长篇!超全Stable Diffusion AI绘画参数及原理详解 - 知乎 (提示词)语法控制 常用语法: 加权:() 或 {} 降权:[](word)//将括号内的提示词权重提高 1.1 倍 ((word))//将括号内的提示…...
手写webpack核心原理,支持typescript的编译和循环依赖问题的解决
主要知识点 babel读取代码的import语句算法:bfs遍历依赖图为浏览器定义一个require函数的polyfill算法:用记忆化搜索解决require函数的循环依赖问题 Quick Start GitHub:https://github.com/Hans774882968/mini-webpack npm install npm…...
开箱即用之MyBatisPlus XML 自定义分页
调用方法 import com.baomidou.mybatisplus.extension.plugins.pagination.Page;public Page<User> queryListByPage(User user) { Page<User> page new Page<>(1, 12); return userMapper.queryListByPage(page, user); } mapper接口 import co…...
GPT应用开发:运行你的第一个聊天程序
本系列文章介绍基于OpenAI GPT API开发应用的方法,适合从零开始,也适合查缺补漏。 本文首先介绍基于聊天API编程的方法。 环境搭建 很多机器学习框架和类库都是使用Python编写的,OpenAI提供的很多例子也是Python编写的,所以为了…...
力扣刷MySQL-第一弹(详细解析)
🎉欢迎您来到我的MySQL基础复习专栏 ☆* o(≧▽≦)o *☆哈喽~我是小小恶斯法克🍹 ✨博客主页:小小恶斯法克的博客 🎈该系列文章专栏:力扣刷题讲解-MySQL 🍹文章作者技术和水平很有限,如果文中出…...
Xcode 15 for Mac:超越开发的全新起点
作为一名开发人员,你是否正在寻找一款强大而高效的开发工具,来帮助你在Mac上构建出卓越的应用程序?那么,Xcode 15就是你一直在寻找的答案。 Xcode 15是苹果公司最新推出的一款集成开发环境(IDE)࿰…...
2021腾讯、华为前端面试题集(基础篇)
Vue 面试题 生命周期函数面试题 1.什么是 vue 生命周期2.vue 生命周期的作用是什么 3.第一次页面加载会触发哪几个钩子 4.简述每个周期具体适合哪些场景 5.created 和 mounted 的区别 6.vue 获取数据在哪个周期函数 7.请详细说下你对 vue 生命周期的理解? **vue 路由…...
怎么修改或移除WordPress后台仪表盘概览底部的版权信息和主题信息?
前面跟大家分享『WordPress怎么把后台左上角的logo和评论图标移除?』和『WordPress后台底部版权信息“感谢使用 WordPress 进行创作”和版本号怎么修改或删除?』,其实在WordPress后台仪表盘的“概览”底部还有一个WordPress版权信息和所使用的…...
计算机三级(网络技术)——应用题
第一题 61.输出端口S0 (直接连接) RG的输出端口S0与RE的S1接口直接相连构成一个互联网段 对172.0.147.194和172.0.147.193 进行聚合 前三段相同,将第四段分别转换成二进制 11000001 11000010 前6位相同,加上前面三段 共30…...
Node.js基础知识点(四)
本节介绍一下最简单的http服务 一.http 可以使用Node 非常轻松的构建一个web服务器,在 Node 中专门提供了一个核心模块:http http 这个模块的就可以帮你创建编写服务器。 1. 加载 http 核心模块 var http require(http) 2. 使用 http.createServe…...
持久双向通信网络协议-WebSocket-入门案例实现demo
1 介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手,两者之间就可以创建持久性的连接, 并进行双向数据传输。 HTTP协议和WebSocket协议对比: HTTP是短连接࿰…...
LV.13 D10 Linux内核移植 学习笔记
具体实验步骤在lv13day10 实验十 一、Linux内核概述 1.1 内核与操作系统 内核 内核是一个操作系统的核心,提供了操作系统最基本的功能,是操作系统工作的基础,决定着整个系统的性能和稳定性 操作系统 操作系统是在内核的基础上添…...
STM32面试体验和题目
目录 一、说一下你之前的工作主要干了什么? 二、stm32有关的知识点 1.stm32的外设有哪一些 2.你的毕业论文的项目里面是怎么设计的 三,C语言的考察 1.写一个结构体(结构体的内容自由发挥) 2.写一个指针型的变量 3.结构体是…...
微软.NET、.NET Framework和.NET Core联系和区别
我是荔园微风,作为一名在IT界整整25年的老兵,看到不少初学者在学习编程语言的过程中如此的痛苦,我决定做点什么,我小时候喜欢看小人书(连环画),在那个没有电视、没有手机的年代,这是…...
Shell脚本同时调用#!/bin/bash和#!/usr/bin/expect
如果你想在一个脚本中同时使用bash和expect,你可以将expect部分嵌入到bash脚本中。以下是一个示例: #!/bin/bash# 设置MySQL服务器地址、端口、用户名和密码 MYSQL_HOST"localhost" MYSQL_PORT"3306" MYSQL_USER"your_usernam…...
C++ Webserver从零开始:基础知识(一)——Linux网络编程基础API
目录 前言 一.socket地址API 1.主机字节序和网络字节序 2.通用socket地址 3.专用socket地址 二.创建socket 三.绑定socket(命名socket) 四.监听socket 五.接受连接(服务端) 六.发起连接(客户端) 七.关闭连接…...
cookie和session的工作过程和作用:弥补http无状态的不足
cookie是客户端浏览器保存服务端数据的一种机制。当通过浏览器去访问服务端时,服务端可以把状态数据以key-value的形式写入到cookie中,存储到浏览器。浏览器下次去服务服务端时,就可以把这些状态数据携带给服务器端,服务器端可以根…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
聊聊 Pulsar:Producer 源码解析
一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台,以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中,Producer(生产者) 是连接客户端应用与消息队列的第一步。生产者…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
