从优先级队列中删除元素
哈喽!大家好,很高兴又见面了,我是golang学习网的一名作者,今天由我给大家带来一篇《从优先级队列中删除元素》,本文主要会讲到等等知识点,希望大家一起学习进步,也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧!
// This example demonstrates a priority queue built using the heap interface. package main import ( "container/heap" "fmt" ) // An Item is something we manage in a priority queue. type Item struct { value int // The value of the item; arbitrary. priority int // The priority of the item in the queue. // The index is needed by update and is maintained by the heap.Interface methods. index int // The index of the item in the heap. } // A PriorityQueue implements heap.Interface and holds Items. type PriorityQueue []*Item func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { // We want Pop to give us the highest, not lowest, priority so we use greater than here. return pq[i].value > pq[j].value } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = j pq[j].index = i } func (pq *PriorityQueue) Push(x interface{}) { n := len(*pq) item := x.(*Item) item.index = n *pq = append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old := *pq n := len(old) item := old[n-1] item.index = -1 // for safety *pq = old[0 : n-1] return item } // update modifies the priority and value of an Item in the queue. func (pq *PriorityQueue) update(item *Item, value int, priority int) { item.value = value item.priority = priority heap.Fix(pq, item.index) } func main() { nums := []int{1, 3, 2, -3, 5, 3, 6, 7, 8, 9} k := 3 result := maxSlidingWindow(nums, k) fmt.Println("result", result) } func maxSlidingWindow(nums []int, k int) { pq := make(PriorityQueue, len(nums)) res := []int{} for i := 0; i < k; i++ { pq[i] = &Item{ value: nums[i], priority: nums[i], index: i, } res = append(res, nums[i]) } heap.Init(&pq) peek := pq[0] fmt.Println(peek.value) // its a maxheap and gives the largest element temp := heap.Pop(&pq).(*Item) fmt.Println("temp:", temp) remove := heap.Remove(&pq, 0).(*Item) // pq = slices.Delete(pq, 5) fmt.Println("remove:", remove) for i:=0;i<len(nums);i++{ //remove the desired element from the priority Queue // insert the next element in the Priority queue // peek the highest value } }
我正在尝试打印滑动窗口中的最大值。将窗口大小的元素(这里k = 3)放入优先级队列(maxheap),然后查看值。 "heap.init(&pq)"将根据优先级分配pq中的索引。查找 maxslidingwindow 函数,最后一个 for 循环打印每个大小为 k 的窗口的最大元素。如果比较 pq 和 nums 数组中的索引,索引将会不同。因此从优先级队列中删除所需的元素似乎几乎是不可能的。
正确答案
你的问题不够明确。我假设您希望 maxslidingwindow
的行为如下:
maxslidingwindow([]int{1, 3, 2,-3, 5, 3, 6, 7, 8, 9}, 3) returns --> []int{3, 3, 5, 5, 6, 7, 8, 9}
要实现这一目标,可以执行以下操作:
使用
nums
中的第一个k
值填充优先级队列。您的代码将
nums
中的所有值放入队列中,这看起来不像移动窗口方法。我确实怀疑我是否误解了你的问题。从队列中取出最大值,将其附加到
result
。对于我,从
k
到len(数据)- 1
:从优先级队列中丢弃
nums[i-k]
元素,并将其推入队列nums[i]
。您应该使用
heap.remove
来删除元素。 go 的heap.fix
提供了一种将删除和推送步骤结合起来的方法。取修改后的优先级队列的最大值,将其附加到
result
。
此外,您的队列实现有一个错误:
func (pq priorityqueue) swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] pq[i].index = j // should be: pq[i].index = i pq[j].index = i // should be: pq[j].index = j }
从优先级队列中删除元素
根据问题的标题,似乎您无法使这部分工作:
使用go的heap
,修改一项(使用heap.fix
)或删除一项(使用heap.remove
),需要该项的索引。要获取相应的索引,至少有两种方法。
请注意,我们需要区分 nums
中元素的索引和队列中元素的索引。我将在下面的代码中将前一个称为 i
,而将后者称为 j
。我们知道要删除的元素的 i
,但是由于 heap
改变了队列,所以我们需要找到 j
。
循环队列并找到元素
足够简单。这样,您就可以简化 priorityqueue
类型:
type priorityqueue []int // i will skip the heap.interface part func maxslidingwindow(nums []int, k int) []int { pq := make(priorityqueue, k) result := make([]int, 0, len(nums)-k+1) for i := 0; i < k; i++ { // 1. pq[i] = nums[i] } heap.init(&pq) result = append(result, pq[0]) // 2. for i := k; i < len(nums); i++ { for j, value := range pq { // 3.1. if value == nums[i-k] { pq[j] = nums[i] // instead of removing then pushing heap.fix(&pq, j) // we modify the content with heap.fix break } } result = append(result, pq[0]) // 3.2. } return result }
它可以正确处理重复值。
保留外部 i -> j
映射
下面只是一种可能的方法,可能不太优雅。我使用 circulararray
来保留我们的映射:
type circulararray []int func (a circulararray) wrapped(index int) int { return index % len(a) } func (a circulararray) get(index int) int { return a[a.wrapped(index)] } func (a circulararray) set(index int, value int) { a[a.wrapped(index)] = value } func (a circulararray) swap(i, j int) { ii, jj := a.wrapped(i), a.wrapped(j) a[ii], a[jj] = a[jj], a[ii] }
type PriorityQueue struct { Window []int // The queue IndicesOfIndices CircularArray // `i -> j` mapping } // func (pq *PriorityQueue) Len() ... func (pq *PriorityQueue) Push(x interface{}) {} // don't use func (pq *PriorityQueue) Pop() interface{} { return nil } // don't use func (pq *PriorityQueue) Less(a, b int) bool { return pq.Window[a] > pq.Window[b] } func (pq *PriorityQueue) Swap(a, b int) { pq.Window[a], pq.Window[b] = pq.Window[b], pq.Window[a] pq.IndicesOfIndices.Swap(a, b) } func maxSlidingWindow(nums []int, k int) []int { pq := PriorityQueue{ Window: make([]int, 0, k), IndicesOfIndices: make(CircularArray, k), } result := make([]int, 1, len(nums)-k+1) for i := 0; i < k; i++ { pq.PushWithIndex(nums[i], i) // 1. } heap.Init(&pq) result[0] = pq.Window[0] // 2. for i := k; i < len(nums); i++ { result = append(result, pq.NextWithIndex(nums[i], i)) // 3. } return result } // Pushes into the queue and sets up the `i -> j` mapping func (pq *PriorityQueue) PushWithIndex(value int, i int) { pq.IndicesOfIndices.Set(i, len(pq.Window)) pq.Window = append(pq.Window, value) } // Updates the queue and returns the max element func (pq *PriorityQueue) NextWithIndex(pushed int, i int) int { j := pq.IndicesOfIndices.Get(i) // 3.1. pq.Window[j] = pushed heap.Fix(pq, j) return pq.Window[0] // 3.2. }
到这里,我们也就讲完了《从优先级队列中删除元素》的内容了。个人认为,基础知识的学习和巩固,是为了更好的将其运用到项目中,欢迎关注golang学习网公众号,带你了解更多关于的知识点!

- 上一篇
- Go Struct JSON 数组数组

- 下一篇
- 如何使用 python 从 pkg.go.dev 获取最新版本的软件包
-
- Golang · Go问答 | 1年前 |
- 在读取缓冲通道中的内容之前退出
- 139浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 戈兰岛的全球 GOPRIVATE 设置
- 204浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 如何将结构作为参数传递给 xml-rpc
- 325浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 如何用golang获得小数点以下两位长度?
- 477浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 如何通过 client-go 和 golang 检索 Kubernetes 指标
- 486浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 将多个“参数”映射到单个可变参数的习惯用法
- 439浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 将 HTTP 响应正文写入文件后出现 EOF 错误
- 357浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 结构中映射的匿名列表的“复合文字中缺少类型”
- 352浏览 收藏
-
- Golang · Go问答 | 1年前 |
- NATS Jetstream 的性能
- 101浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 如何将复杂的字符串输入转换为mapstring?
- 440浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 相当于GoLang中Java将Object作为方法参数传递
- 212浏览 收藏
-
- Golang · Go问答 | 1年前 |
- 如何确保所有 goroutine 在没有 time.Sleep 的情况下终止?
- 143浏览 收藏
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 508次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 484次学习
-
- 茅茅虫AIGC检测
- 茅茅虫AIGC检测,湖南茅茅虫科技有限公司倾力打造,运用NLP技术精准识别AI生成文本,提供论文、专著等学术文本的AIGC检测服务。支持多种格式,生成可视化报告,保障您的学术诚信和内容质量。
- 139次使用
-
- 赛林匹克平台(Challympics)
- 探索赛林匹克平台Challympics,一个聚焦人工智能、算力算法、量子计算等前沿技术的赛事聚合平台。连接产学研用,助力科技创新与产业升级。
- 161次使用
-
- 笔格AIPPT
- SEO 笔格AIPPT是135编辑器推出的AI智能PPT制作平台,依托DeepSeek大模型,实现智能大纲生成、一键PPT生成、AI文字优化、图像生成等功能。免费试用,提升PPT制作效率,适用于商务演示、教育培训等多种场景。
- 153次使用
-
- 稿定PPT
- 告别PPT制作难题!稿定PPT提供海量模板、AI智能生成、在线协作,助您轻松制作专业演示文稿。职场办公、教育学习、企业服务全覆盖,降本增效,释放创意!
- 138次使用
-
- Suno苏诺中文版
- 探索Suno苏诺中文版,一款颠覆传统音乐创作的AI平台。无需专业技能,轻松创作个性化音乐。智能词曲生成、风格迁移、海量音效,释放您的音乐灵感!
- 160次使用
-
- GoLand调式动态执行代码
- 2023-01-13 502浏览
-
- 用Nginx反向代理部署go写的网站。
- 2023-01-17 502浏览
-
- Golang取得代码运行时间的问题
- 2023-02-24 501浏览
-
- 请问 go 代码如何实现在代码改动后不需要Ctrl+c,然后重新 go run *.go 文件?
- 2023-01-08 501浏览
-
- 如何从同一个 io.Reader 读取多次
- 2023-04-11 501浏览