当前位置: 首页 > news >正文

#### 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<𝑛 时

20200328Build_heap

插入数值:在堆的末尾插入,然后不断向上提升,直到没有大小颠倒。

删除数值:首先把堆的最后一个节点的数值放到根上去,并且删除最后一个节点,然后不断向下交换直到没有大小颠倒为止。向下交换的时候如果 2 个儿子都比自己小,那么选择数值较小的儿子进行交换。

复杂度:建堆需要 On 的时间,但删除、插入都和树深度成正比,时间复杂度是 O𝑛𝑙𝑜𝑔𝑛。

相关文章:

#### golang中【堆】的使用及底层 ####

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

OpenAI Gym Atari on Windows

题意&#xff1a;在Windows系统上使用OpenAI Gym的Atari环境 问题背景&#xff1a; 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

接口 接口概述 接口是一种规范&#xff0c;使用接口就代表着要在程序中制定规范. 制定规范可以给不同类型的事物定义功能&#xff0c;例如&#xff1a; 利用接口&#xff0c;给飞机、小鸟制定飞行规范&#xff0c;让其都具备飞行的功能&#xff1b;利用接口&#xff0c;给鼠…...

【网络协议】ISIS

ISIS IS-IS&#xff08;Intermediate System to Intermediate System&#xff0c;中间系统到中间系统&#xff09;协议是一种用于在自治系统&#xff08;AS&#xff09;内部进行路由选择的链路状态路由协议。它最初是为OSI&#xff08;开放系统互连&#xff09;网络设计的&…...

一.4 处理器读并解释储存在内存中的指令

此刻&#xff0c;hello.c源程序已经被编译系统翻译成了可执行目标文件hello&#xff0c;并被存放在硬盘上。要想在Unix系统上运行该可执行文件&#xff0c;我们将它的文件名输入到称为shell的应用程序中&#xff1a; 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

依赖包的版本问题&#xff0c;别的开发语言有没有类似的问题&#xff1f;是怎么解决的&#xff1f; 举例&#xff1a;java java的依赖包的版本问题&#xff0c;通过Maven模块来操作&#xff0c;可以指定依赖包版本号&#xff0c;如下&#xff1a; go.mod 文件 go.mod文件是G…...

【Git】取消追踪多个文件或目录

文章目录 场景方法1. 添加到 .gitignore2. 从暂存区移除 示例1. 编辑 .gitignore 文件2. 从暂存区移除文件或目录 场景 清理&#xff1a;不再希望某些文件被 Git 追踪。配置忽略文件&#xff1a;通常配合 .gitignore 文件使用&#xff0c;以便以后这些文件不会被重新添加到索引…...

【Linux详解】进程等待 | 非阻塞轮询

引入&#xff1a; 为什么&#xff1f;是什么&#xff1f;怎么办 是什么&#xff1f; 进程等待是指父进程暂停自己的执行&#xff0c;直到某个特定的子进程结束或发生某些特定的事件。 为什么&#xff1f; 僵尸进程刀枪不入&#xff0c;不可被杀死&#xff0c;存在内存泄露…...

聊一下Maven打包的问题(jar要发布)

文章目录 一、问题和现象二、解决方法&#xff08;1&#xff09;方法一、maven-jar-pluginmaven-dependency-plugin&#xff08;2&#xff09;方法二、maven-assembly-plugin 一、问题和现象 现在的开发一直都是用spring boot&#xff0c;突然有一天&#xff0c;要自己开发一个…...

JavaScript中,正则表达式所涉及的api,解析、实例和总结

JS中正则的api包括以下&#xff1a; String#searchString#splitString#matchString#replaceRegExp#testRegExp#exec 1. String#search 查找输入串中第一个匹配正则的index&#xff0c;如果没有匹配的则返回-1。g修饰符对结果无影响 var string "abbbcbc"; var r…...

【计算机】同步/异步

同步/异步 在计算机科学和编程中&#xff0c;“同步”&#xff08;Synchronization&#xff09;是一种机制&#xff0c;用于协调不同进程或线程之间的操作&#xff0c;以避免竞态条件&#xff08;race conditions&#xff09;、死锁&#xff08;deadlocks&#xff09;和其他并…...

谈大语言模型动态思维流程编排

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

工厂自动化相关设备工业一体机起到什么作用?

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

哈佛大学 || 概念空间中学习动态的涌现:探索隐藏能力

获取本文论文原文PDF&#xff0c;请在公众号【AI论文解读】留言&#xff1a;论文解读 今天主要看一个问题&#xff1a;在模型中的学习动态是如何涌现的。 在现代生成模型的研究与应用中&#xff0c;不断发现这些模型在处理训练数据时展现出了惊人的能力&#xff0c;这些能力很…...

Dockerfile打包部署常用操作

文章目录 1、Dockerfile部署java程序&#xff08;jar包&#xff09;1.1、创建Dockerfile1.2、将Dockerfile和要上传的jar包放到一个目录下&#xff0c;构建镜像1.3、创建启动容器 2、Dockerfile部署vue2.1、创建dockerfile文件2.2、将打包的dist文件放到dockerfile同文件目录下…...

ArcGIS:探索地理信息系统的强大功能与实际应用

ArcGIS是一款功能强大的地理信息系统&#xff08;GIS&#xff09;软件&#xff0c;由Esri公司开发。它广泛应用于各个领域&#xff0c;包括城市规划、环境保护、资源管理、交通运输等。作为一名长期使用ArcGIS的用户&#xff0c;我深感这款软件在数据分析、地图制作和空间信息管…...

Python 全栈体系【三阶】(二)

第一章 Django 五、模板 1. 概述 Django中的模板是指可以动态生成任何基于文本格式文件的技术&#xff08;如HTML、CSS等&#xff09;。 Django中内置了自己的模板系统&#xff0c;称为DTL(Django Template Language), Django模板语言。 2. 配置 settings.py中关于模板的…...

【VUE】 深入理解 Vue 动态路由:简介、实际开发场景与代码示例

深入理解 Vue 动态路由&#xff1a;简介、实际开发场景与代码示例 Vue.js 是一个用于构建用户界面的渐进式框架&#xff0c;它拥有丰富的生态系统&#xff0c;其中 Vue Router 是其官方的路由管理库。动态路由是 Vue Router 的一个强大特性&#xff0c;允许我们在应用运行时根…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...