#### golang中【堆】的使用及底层 ####
声明,本文部分内容摘自:
Go: 深入理解堆实现及应用-腾讯云开发者社区-腾讯云
数组实现堆 | WXue
堆(Heap)是实现优先队列的数据结构,Go提供了接口和方法来操作堆。
应用
package mainimport ("container/heap""sort"
)/*
题目:给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字,滑动窗口每次只向右移动一位,返回滑动窗口中的最大值。示例:输入:nums = [1,3,-1,-3,5,3,6,7], k = 3输出:[3,3,5,5,6,7]解释:滑动窗口的位置 最大值---------------------------------[1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
题解:大根堆可以帮助我们实时维护一系列元素中的最大值。初始时,我们将数组 nums 的前 k 个元素放入优先队列中。每当我们向右移动窗口时,我们就可以把一个新的元素放入优先队列中,此时堆顶的元素就是堆中所有元素的最大值。然而这个最大值可能并不在滑动窗口中,在这种情况下,这个值在数组 nums 中的位置出现在滑动窗口左边界的左侧。因此,当我们后续继续向右移动窗口时,这个值就永远不可能出现在滑动窗口中了,我们可以将其永久地从优先队列中移除。我们不断地移除堆顶的元素,直到其确实出现在滑动窗口中。此时,堆顶元素就是滑动窗口中的最大值。为了方便判断堆顶元素与滑动窗口的位置关系,我们可以在优先队列中存储二元组 (num,index),表示元素 num 在数组中的下标为 index。
*/var a []int// heap 实现了标准库的heap.Interface接口
type hp struct {sort.IntSlice // type IntSlice []int
}func (h hp) Less(i, j int) bool {return a[h.IntSlice[i]] > a[h.IntSlice[j]]
}
func (h *hp) Push(v interface{}) {h.IntSlice = append(h.IntSlice, v.(int))
}
func (h *hp) Pop() interface{} {a := h.IntSlicev := a[len(a)-1]h.IntSlice = a[:len(a)-1]return v
}func maxSlidingWindow(nums []int, k int) (ans []int) {ans = make([]int, 1, len(nums)-k+1)a = nums// 初始化堆(优先队列)queue := &hp{make([]int, k)} // 优先队列for i := 0; i < k; i++ {queue.IntSlice[i] = i // 注意堆里存的是数组下标而非数组值,对应Less函数里的比较时需要a[h.IntSlice[i]]来比较值}heap.Init(queue) // 初始化+向下调整// 赋值ans[0],因为不需要判断IntSlice[0]的元素是不是在边界外的左侧ans[0] = nums[queue.IntSlice[0]] // IntSlice[0] 下标为0=数组IntSlice的头部=堆顶元素// 窗口滑动for i := k; i < len(nums); i++ {heap.Push(queue, i) // 入堆+向上调整for queue.IntSlice[0] <= i-k { // 判断IntSlice[0]的元素是不是在边界外的左侧heap.Pop(queue) // 出堆+向下调整}ans = append(ans, nums[queue.IntSlice[0]]) // IntSlice[0] 下标为0=数组头部=堆顶元素}return ans
}func main() {res := maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3)println(res)
}
底层
包:container/heap
接口:heap.Interface
源码:
type Interface interface {sort.InterfacePush(x interface{}) // 添加元素Pop() interface{} // 弹出元素
}
其中,注意,实现heap.Interface接口需要嵌入sort.Interface,后者包含Len()、Less(i, j int) bool和Swap(i, j int)方法,用于确定元素间的排序。
全部源码:
type Interface interface {sort.InterfacePush(x any) // add x as element Len()Pop() any // remove and return element Len() - 1.
}func Init(h Interface) {// heapifyn := h.Len()for i := n/2 - 1; i >= 0; i-- {down(h, i, n)}
}// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h Interface, x any) {h.Push(x)up(h, h.Len()-1)
}func Pop(h Interface) any {n := h.Len() - 1h.Swap(0, n)down(h, 0, n)return h.Pop()
}func Remove(h Interface, i int) any {n := h.Len() - 1if n != i {h.Swap(i, n)if !down(h, i, n) {up(h, i)}}return h.Pop()
}func Fix(h Interface, i int) {if !down(h, i, h.Len()) {up(h, i)}
}func up(h Interface, j int) {for {i := (j - 1) / 2 // parentif i == j || !h.Less(j, i) {break}h.Swap(i, j)j = i}
}func down(h Interface, i0, n int) bool {i := i0for {j1 := 2*i + 1if j1 >= n || j1 < 0 { // j1 < 0 after int overflowbreak}j := j1 // left childif j2 := j1 + 1; j2 < n && h.Less(j2, j1) {j = j2 // = 2*i + 2 // right child}if !h.Less(j, i) {break}h.Swap(i, j)i = j}return i > i0
}
其中:
① 初始化(Init): 对一个未排序的切片构建堆。这是通过down方法实现的,down方法确保元素下沉到正确的位置,维持堆的性质。
② 添加元素(Push): 元素被添加到切片的末尾,然后通过up方法上浮到正确的位置。
注意:标准库中的push函数中,第一行调用的【h.Push(x)】是上层业务代码中自行实现的heap.Interface的堆实例的push方法。
func Push(h Interface, x any) {
h.Push(x)
up(h, h.Len()-1)
}
③ 删除元素(Pop): 堆顶元素(切片的第一个元素)被移动到切片末尾并返回,然后新的堆顶元素通过down方法恢复堆的性质。
④ 删除任意元素(Remove): 类似Pop,但可以移除指定位置的元素。此操作需要综合up和down方法来调整堆。
⑤ 修改元素并调整堆(Fix): 如果堆中某个元素被外部修改了(比如优先级改变),Fix方法会根据这个修改后的新值重新调整堆。
堆是一颗完全二叉树,可由数组表示
完全二叉树,逐层而下,从左到右,结点的位置完全由其序号觉得,因此可以用数组来实现。
计算各结点下标的公式,其中 𝑟𝑟 表示结点的下标,范围在 0 ~ n-1 之间,n 是二叉树结点的总数。
𝑃𝑎𝑟𝑒𝑛𝑡(𝑟)=⌊(𝑟−1)/2⌋𝑃𝑎𝑟𝑒𝑛𝑡(𝑟)=⌊(𝑟−1)/2⌋ 向下取整,当 𝑟≠0𝑟≠0 时
𝐿𝑒𝑓𝑡𝑐ℎ𝑖𝑙𝑑(𝑟)=2𝑟+1𝐿𝑒𝑓𝑡𝑐ℎ𝑖𝑙𝑑(𝑟)=2𝑟+1, 当 2𝑟+1<𝑛2𝑟+1<𝑛 时
𝑅𝑖𝑔ℎ𝑡𝑐ℎ𝑖𝑙𝑑(𝑟)=2𝑟+2𝑅𝑖𝑔ℎ𝑡𝑐ℎ𝑖𝑙𝑑(𝑟)=2𝑟+2, 当 2𝑟+2<𝑛2𝑟+2<𝑛 时
𝐿𝑒𝑓𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟−1𝐿𝑒𝑓𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟−1, 当 r 为偶数时
𝑅𝑖𝑔ℎ𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟+1𝑅𝑖𝑔ℎ𝑡𝑠𝑖𝑏𝑙𝑖𝑛𝑔()=𝑟+1 , 当 r 为奇数并且 𝑟+1<𝑛𝑟+1<𝑛 时
插入数值:在堆的末尾插入,然后不断向上提升,直到没有大小颠倒。
删除数值:首先把堆的最后一个节点的数值放到根上去,并且删除最后一个节点,然后不断向下交换直到没有大小颠倒为止。向下交换的时候如果 2 个儿子都比自己小,那么选择数值较小的儿子进行交换。
复杂度:建堆需要 On 的时间,但删除、插入都和树深度成正比,时间复杂度是 O𝑛𝑙𝑜𝑔𝑛。
相关文章:

#### golang中【堆】的使用及底层 ####
声明,本文部分内容摘自: Go: 深入理解堆实现及应用-腾讯云开发者社区-腾讯云 数组实现堆 | WXue 堆(Heap)是实现优先队列的数据结构,Go提供了接口和方法来操作堆。 应用 package mainimport ("container/heap&q…...

OpenAI Gym Atari on Windows
题意:在Windows系统上使用OpenAI Gym的Atari环境 问题背景: Im having issues installing OpenAI Gym Atari environment on Windows 10. I have successfully installed and used OpenAI Gym already on the same system. It keeps tripping up when t…...
Java进阶----接口interface
接口 接口概述 接口是一种规范,使用接口就代表着要在程序中制定规范. 制定规范可以给不同类型的事物定义功能,例如: 利用接口,给飞机、小鸟制定飞行规范,让其都具备飞行的功能;利用接口,给鼠…...
【网络协议】ISIS
ISIS IS-IS(Intermediate System to Intermediate System,中间系统到中间系统)协议是一种用于在自治系统(AS)内部进行路由选择的链路状态路由协议。它最初是为OSI(开放系统互连)网络设计的&…...

一.4 处理器读并解释储存在内存中的指令
此刻,hello.c源程序已经被编译系统翻译成了可执行目标文件hello,并被存放在硬盘上。要想在Unix系统上运行该可执行文件,我们将它的文件名输入到称为shell的应用程序中: linux>./hello hello, world linux> shell是一个命令…...

【Android面试八股文】Android性能优化面试题:怎样检测函数执行是否卡顿?
文章目录 卡顿一、可重现的卡顿二、不可重现的卡顿第一种方案: 基于 Looper 的监控方法第二种方案:基于 Choreographer 的监控方法第三种方案:字节码插桩方式第四种方案: 使用 JVMTI 监听函数进入与退出总结相关大厂的方案ArgusAPMBlockCanaryQQ空间卡慢组件Matrix微信广研参…...
C语言7 控制语句
目录 1. 条件语句 if 语句 if-else 语句 if-else if-else 语句 switch 语句 2. 循环语句 for 循环 while 循环 do-while 循环 3. 跳转语句 break 语句 continue 语句 return 语句 goto 语句 1. 条件语句 if 语句 if语句根据给定条件的真或假来决定是否执行某段…...

go mod 依赖管理补充2
依赖包的版本问题,别的开发语言有没有类似的问题?是怎么解决的? 举例:java java的依赖包的版本问题,通过Maven模块来操作,可以指定依赖包版本号,如下: go.mod 文件 go.mod文件是G…...
【Git】取消追踪多个文件或目录
文章目录 场景方法1. 添加到 .gitignore2. 从暂存区移除 示例1. 编辑 .gitignore 文件2. 从暂存区移除文件或目录 场景 清理:不再希望某些文件被 Git 追踪。配置忽略文件:通常配合 .gitignore 文件使用,以便以后这些文件不会被重新添加到索引…...

【Linux详解】进程等待 | 非阻塞轮询
引入: 为什么?是什么?怎么办 是什么? 进程等待是指父进程暂停自己的执行,直到某个特定的子进程结束或发生某些特定的事件。 为什么? 僵尸进程刀枪不入,不可被杀死,存在内存泄露…...

聊一下Maven打包的问题(jar要发布)
文章目录 一、问题和现象二、解决方法(1)方法一、maven-jar-pluginmaven-dependency-plugin(2)方法二、maven-assembly-plugin 一、问题和现象 现在的开发一直都是用spring boot,突然有一天,要自己开发一个…...

JavaScript中,正则表达式所涉及的api,解析、实例和总结
JS中正则的api包括以下: String#searchString#splitString#matchString#replaceRegExp#testRegExp#exec 1. String#search 查找输入串中第一个匹配正则的index,如果没有匹配的则返回-1。g修饰符对结果无影响 var string "abbbcbc"; var r…...
【计算机】同步/异步
同步/异步 在计算机科学和编程中,“同步”(Synchronization)是一种机制,用于协调不同进程或线程之间的操作,以避免竞态条件(race conditions)、死锁(deadlocks)和其他并…...

谈大语言模型动态思维流程编排
尽管大语言模型已经呈现出了强大的威力,但是如何让它完美地完成一个大的问题,仍然是一个巨大的挑战。 需要精心地给予大模型许多的提示(Prompt)。对于一个复杂的应用场景,编写一套完整的,准确无误的提示&am…...

工厂自动化相关设备工业一体机起到什么作用?
在当今的制造业领域,工厂自动化已成为提高生产效率、保证产品质量和降低成本的关键。在这一进程中,工业一体机作为一种重要的设备,发挥着不可或缺的作用。 工业一体机是自动化生产线上的控制中心。它能够整合和处理来自各个传感器、执行器和其…...

哈佛大学 || 概念空间中学习动态的涌现:探索隐藏能力
获取本文论文原文PDF,请在公众号【AI论文解读】留言:论文解读 今天主要看一个问题:在模型中的学习动态是如何涌现的。 在现代生成模型的研究与应用中,不断发现这些模型在处理训练数据时展现出了惊人的能力,这些能力很…...
Dockerfile打包部署常用操作
文章目录 1、Dockerfile部署java程序(jar包)1.1、创建Dockerfile1.2、将Dockerfile和要上传的jar包放到一个目录下,构建镜像1.3、创建启动容器 2、Dockerfile部署vue2.1、创建dockerfile文件2.2、将打包的dist文件放到dockerfile同文件目录下…...

ArcGIS:探索地理信息系统的强大功能与实际应用
ArcGIS是一款功能强大的地理信息系统(GIS)软件,由Esri公司开发。它广泛应用于各个领域,包括城市规划、环境保护、资源管理、交通运输等。作为一名长期使用ArcGIS的用户,我深感这款软件在数据分析、地图制作和空间信息管…...
Python 全栈体系【三阶】(二)
第一章 Django 五、模板 1. 概述 Django中的模板是指可以动态生成任何基于文本格式文件的技术(如HTML、CSS等)。 Django中内置了自己的模板系统,称为DTL(Django Template Language), Django模板语言。 2. 配置 settings.py中关于模板的…...
【VUE】 深入理解 Vue 动态路由:简介、实际开发场景与代码示例
深入理解 Vue 动态路由:简介、实际开发场景与代码示例 Vue.js 是一个用于构建用户界面的渐进式框架,它拥有丰富的生态系统,其中 Vue Router 是其官方的路由管理库。动态路由是 Vue Router 的一个强大特性,允许我们在应用运行时根…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度
一、引言:多云环境的技术复杂性本质 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时,基础设施的技术债呈现指数级积累。网络连接、身份认证、成本管理这三大核心挑战相互嵌套:跨云网络构建数据…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...