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

golang 使用双向链表作为container/heap的载体

MyHeap:container/heap的数据载体,需要实现以下方法:

Len:堆中数据个数

Less:第i个元素 是否必 第j个元素 值小

Swap:交换第i个元素和 第j个元素

Push:向堆中追加元素

Pop:从堆中取出元素

下面是使用双向链路作为数据载体的最小堆实现方式:

package mainimport ("container/heap""fmt"
)type HeapItem struct {Value intPrev  *HeapItemNext  *HeapItem
}type MyHeap struct {Head   *HeapItemTail   *HeapItemLength int
}func (h *MyHeap) Len() int {return h.Length
}func (h *MyHeap) Less(i, j int) bool {return h.Find(i).Value < h.Find(j).Value
}func (h *MyHeap) Swap(i, j int) {nodeI, nodeJ := h.Find(i), h.Find(j)isNear := h.IsNear(nodeI, nodeJ)// 记录I的前和后nodeIPrev, nodeINext := nodeI.Prev, nodeI.Next// 记录J的前和后nodeJPrev, nodeJNext := nodeJ.Prev, nodeJ.Next// 把J放到I的位置nodeIPrev.Next = nodeJnodeJ.Prev = nodeIPrevnodeJ.Next = nodeINext // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeINext.Prev = nodeJ // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值// 把I放到J的位置nodeJPrev.Next = nodeI // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeI.Prev = nodeJPrev // near, 对于相邻元素, 这样操作有问题, 下面会重新赋值nodeI.Next = nodeJNextnodeJNext.Prev = nodeI// 对于相邻元素,重新赋值if isNear {nodeJ.Next = nodeInodeINext.Prev = nodeIPrevnodeJPrev.Next = nodeJNextnodeI.Prev = nodeJ}
}func (h *MyHeap) Push(v interface{}) {newItem := v.(*HeapItem)temp := h.Tail.Prevtemp.Next = newItemnewItem.Prev = tempnewItem.Next = h.Tailh.Tail.Prev = newItemh.Length++return
}func (h *MyHeap) Pop() interface{} {realTailNode := h.Tail.PrevrealTailNode.Prev.Next = realTailNode.NextrealTailNode.Next.Prev = realTailNode.Prevh.Length--return realTailNode
}func (h *MyHeap) IsNear(nodeI, nodeJ *HeapItem) bool {if nodeI.Next == nodeJ {return true}return false
}func (h *MyHeap) Find(i int) *HeapItem {nodeI := h.Headfor k := 0; k <= i; k++ {nodeI = nodeI.Next}return nodeI
}func (h *MyHeap) Show() {forward := ""backward := ""i := 0for curr := h.Head; curr != nil && i < 10; curr = curr.Next {forward += fmt.Sprintf("'%d'->", curr.Value)i++}j := 0for curr := h.Tail; curr != nil && j < 10; curr = curr.Prev {backward = fmt.Sprintf("'%d'<-", curr.Value) + backwardj++}fmt.Printf("forward=%s, backward=%s\n", forward, backward)
}func InitHeap() *MyHeap {head := &HeapItem{Value: -1}tail := &HeapItem{Value: -2}head.Next = tailtail.Prev = headreturn &MyHeap{Head:   head,Tail:   tail,Length: 0,}
}func main() {myHeap := InitHeap()heap.Init(myHeap)heap.Push(myHeap, &HeapItem{Value: 10})heap.Push(myHeap, &HeapItem{Value: 1000})heap.Push(myHeap, &HeapItem{Value: 5})heap.Push(myHeap, &HeapItem{Value: 1})heap.Push(myHeap, &HeapItem{Value: 7})myHeap.Show()for myHeap.Len() > 0 {item := heap.Pop(myHeap).(*HeapItem)fmt.Printf("%d ", item.Value)}fmt.Println()
}

相关文章:

golang 使用双向链表作为container/heap的载体

MyHeap&#xff1a;container/heap的数据载体&#xff0c;需要实现以下方法&#xff1a; Len&#xff1a;堆中数据个数 Less&#xff1a;第i个元素 是否必 第j个元素 值小 Swap&#xff1a;交换第i个元素和 第j个元素 Push&#xff1a;向堆中追加元素 Pop&#xff1a;从堆…...

C#集合操作优化:高效实现批量添加与删除

在C#中&#xff0c;对集合进行批量操作&#xff08;如批量添加或删除元素&#xff09;通常涉及使用集合类型提供的方法和特性&#xff0c;以及可能的循环或LINQ查询来高效地处理大量数据。以下是一些常见的方法和技巧&#xff1a; 批量添加元素 使用集合的AddRange方法&#x…...

142.WEB渗透测试-信息收集-小程序、app(13)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;141.WEB渗透测试-信息收集-小程序、app&#xff08;12&#xff09; 软件用法&#xff0c…...

24.日常算法

1. 数组中两元素的最大乘积 题目来源 给你一个整数数组 nums&#xff0c;请你选择数组的两个不同下标 i 和 j&#xff0c;使 (nums[i]-1)*(nums[j]-1) 取得最大值。请你计算并返回该式的最大值。 示例 1&#xff1a; 输入&#xff1a;nums [3,4,5,2] 输出&#xff1a;12 解释…...

分布式理解

分布式 如何理解分布式 狭义的分布是指&#xff0c;指多台PC在地理位置上分布在不同的地方。 分布式系统 分布式系**统&#xff1a;**多个能独立运行的计算机&#xff08;称为结点&#xff09;组成。各个结点利用计算机网络进行信息传递&#xff0c;从而实现共同的“目标或者任…...

wordpress调用指定ID页面的链接

在WordPress中&#xff0c;如果你想调用一个指定ID的页面链接&#xff0c;可以使用以下几种方法&#xff1a; 方法一&#xff1a;使用页面ID 你可以直接使用页面的ID来生成链接。例如&#xff0c;如果你想链接到ID为123的页面&#xff0c;可以使用以下代码&#xff1a; <…...

单值二叉树(C语言详解版)

一、摘要 今天要讲的是leetcode单值二叉树&#xff0c;这里用到的C语言&#xff0c;主要提供的是思路&#xff0c;大家看了我的思路之后可以点击链接自己试一下。 二、题目简介 如果二叉树每个节点都具有相同的值&#xff0c;那么该二叉树就是单值二叉树。 只有给定的树是单…...

python学opencv|读取图像(四十二)使用cv2.add()函数实现多图像叠加

【1】引言 前序学习过程中&#xff0c;掌握了灰度图像和彩色图像的掩模操作&#xff1a; python学opencv|读取图像&#xff08;九&#xff09;用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像&#xff08;四十&#xff09;掩模&#xff1a;三…...

速通Docker === Docker Compose

目录 Docker Compose 简介 Docker Compose 常用命令 使用 Docker Compose 启动 WordPress 普通启动方式&#xff08;使用 Docker 命令&#xff09; 使用 Docker Compose 启动 Docker Compose 的特性 Docker Compose 简介 Docker Compose 是一个用于定义和运行多容器 Dock…...

LMI Gocator GO_SDK VS2019引用配置

LMI SDK在VS2019中的引用是真的坑爹,总结一下经验,希望后来的人能少走弯路.大致内容如下: &#xff08;1&#xff09; 环境变量 &#xff08;2&#xff09;C/C 附加包含目录 E:\GWQ\Gocator\GO_SDK\Gocator\GoSdk E:\GWQ\Gocator\GO_SDK\Platform\kApi &#xff08;3&#…...

技术之翼,创作之心

引言&#xff1a;初入编程的迷茫与追求 当我第一次接触到编程时&#xff0c;心中充满了既期待又迷茫的情感。那时&#xff0c;我还是一名刚刚踏入大学的学生&#xff0c;面对一门陌生而复杂的学科——计算机科学&#xff0c;我的内心充满了好奇与困惑。课堂上&#xff0c;老师…...

WebSocket异步导出

WebSocket异步导出 1、安装sockjs-client和stompjs2、连接后台3、vite.config.ts 配置反向代理4、导出并实时通信5、 封装WebSocket 文件注册登录(城通网盘) 1、安装sockjs-client和stompjs import SockJS from sockjs-client/dist/sockjs.min.js import Stomp from stompjs2、…...

OS2.【Linux】基本命令入门(1)

目录 1.操作系统是什么? 2.好操作系统的衡量标准 3.操作系统的核心工作 4.在计算机上所有行为都会被转换为硬件行为 5.文件 6.简单介绍一些基本命令 1.clear 2.pwd 3.ls 1.ls -l 2.隐藏文件的创建 3.ls -al 4.ls -ld 5.ls -F(注意是大写) 4.cd 1.cd .. "…...

【二叉树】4. 判断一颗二叉树是否是平衡二叉树。5. 对称二叉树。6. 二叉树的构建及遍历 7. 二叉树的分层遍历 。

判断一颗二叉树是否是平衡二叉树。OJ链接 可以在求树高度的过程中判断树是否平衡 对称二叉树。OJ链接 二叉树的构建及遍历。OJ链接 注意&#xff1a;public static int i最好把static去掉 否则当有多个测试用例时 i无法重新为0二叉树的分层遍历 。OJ链接 但此题要求返回List…...

OS Copilot功能测评:智能助手的炫彩魔法

简介&#xff1a; OS Copilot 是一款融合了人工智能技术的智能助手&#xff0c;专为Linux系统设计&#xff0c;旨在提升系统管理和运维效率。本文详细介绍了在阿里云ECS实例上安装和体验OS Copilot的过程&#xff0c;重点评测了其三个核心参数&#xff1a;-t&#xff08;模式…...

MFC结构体数据文件读写实例

程序功能将结构体内数组数据写入文件和读出 2Dlg.h中代码: typedef struct Student {int nNum[1000];float fScore;CString sss;}stu; class CMy2Dlg : public CDialog { // Construction public:CMy2Dlg(CWnd* pParent NULL); // standard constructorstu stu1; ... } 2Dl…...

音频 PCM 格式 - raw data

文章目录 raw 音频格式&#xff1a;PCM其他音频格式&#xff1a;mp31. 无损压缩音频&#xff08;类比 PNG 图像&#xff09;2. 有损压缩音频&#xff08;类比 JPEG 图像&#xff09; 试了一下科大讯飞的音频识别云 api&#xff0c;踩了点坑 与本文无关&#xff1a;讯飞的 api 使…...

关于deepin上运行Qt开发的程序

国产化替代是将来各单位的主流趋势&#xff0c;探索自行开发应用程序在国产操作系统上正常运行是将来的主要工作之一。本文浅尝gui程序在统信社区版——deepin上遇到的小问题。 使用Qt在deepin上做了一个类似gif的帧动画弹窗&#xff0c;在编译运行时&#xff0c;程序可以正常…...

css 如何将字体进行压扁,即水平缩放scaleX

1、下面是来自baidu ai的结果&#xff1a; 2、下面是测试结果&#xff1a; .font-yh {text-align: center;font-family: msyh;display: inline-block; /* 确保transform作用于元素本身 */transform: scaleX(1.5); /* 水平缩放 */ } font-face {font-family: msyh;font-style:…...

C++AVL树(二)详解

文章目录 AVL树旋转单旋右单旋左单旋 双旋左右双旋右左双旋 平衡因子的更新左右双旋右左双旋 判断是不是AVL树时间复杂度分析全部的代码 AVL树 旋转 单旋 单旋是纯粹的一边高 单旋平衡因子是同号 右单旋 a,b,c自身不能发生旋转 并且也不能不向上继续更新&#xff08;不能停…...

使用VSCode开发Django指南

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

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?

在大数据处理领域&#xff0c;Hive 作为 Hadoop 生态中重要的数据仓库工具&#xff0c;其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式&#xff0c;很多开发者常常陷入选择困境。本文将从底…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...

goreplay

1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具&#xff0c;可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长&#xff0c;测试它所需的工作量也会呈指数级增长。GoRepl…...