程序员经验分享-hwhale

使用链表进行堆排序

2024-05-23

我想知道是否有人曾经使用链表进行堆排序，如果他们可以提供代码。我已经能够使用数组进行堆排序，但尝试在链表中进行排序似乎不切实际，而且在你知道的地方很痛苦。我必须为我正在做的项目实现链接列表，任何帮助将不胜感激。

我也用C。


答案是“你不想在链表上实现堆排序”。

堆排序是一种很好的排序算法，因为它O(n log n)并且它就位。然而，当你有一个链表时，堆排序就不再是O(n log n)因为它依赖于对数组的随机访问，而链表中没有这种访问。所以你要么失去你的就地属性（通过需要定义一个树状结构是O(n)空间）。或者你需要不需要它们，但请记住链接列表是O(n)用于会员查找。这使得运行时复杂性达到类似的程度O(n^2 log n)这比冒泡排序更糟糕。

只需使用归并排序即可。你已经拥有了O(n)内存开销要求。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

Sorting

LinkedList

heapsort

使用链表进行堆排序 的相关文章

  • WPF DataGrid 多选

    我读过几篇关于这个主题的文章 但很多都是来自 VS 或框架的早期版本 我想做的是从 dataGrid 中选择多行并将这些行返回到绑定的可观察集合中 我尝试创建一个属性 类型 并将其添加到可观察集合中 它适用于单个记录 但代码永远不会触发多个

  • 如何将 std::string& 转换为 C# 引用字符串

    我正在尝试将 C 函数转换为std string参考C 我的 API 如下所示 void GetStringDemo std string str 理想情况下 我希望在 C 中看到类似的东西 void GetStringDemoWrap r

  • 调用 McAfee 病毒扫描引擎

    我收到客户的请求 要求使用他们服务器上的 McAfee 病毒扫描将病毒扫描集成到应用程序中 我做了一些调查 发现 McScan32 dll 是主要的扫描引擎 它导出各种看起来有用的函数 我还发现提到了 McAfee Scan Engine

  • 没有特殊字符的密码验证器

    我是 RegEx 的新手 已经进行了大量搜索 但没有找到任何具体内容 我正在编写一个验证密码字符串的正则表达式 可接受的字符串必须至少具有 4 种字符类型中的 3 种 数字 小写字母 大写字母 特殊字符 我对包含有一个想法 也就是说 如果这

  • 通过引用传递 [C++]、[Qt]

    我写了这样的东西 class Storage public Storage QString key const int value const void add item QString int private QMap

  • std::list 线程push_back、front、pop_front

    std list 线程安全吗 我假设不是这样 所以我添加了自己的同步机制 我认为我有正确的术语 但我仍然遇到问题 每个函数都由单独的线程调用 Thread1 不能等待 它必须尽可能快 std list

  • -webkit-box-shadow 与 QtWebKit 模糊？

    当时有什么方法可以实现 webkit box shadow 的工作模糊吗 看完这篇评论错误报告 https bugs webkit org show bug cgi id 23291 我认识到这仍然是一个问题 尽管错误报告被标记为RESOL

  • 对类 static constexpr 结构的未定义引用，g++ 与 clang

    这是我的代码 a cp p struct int2 int x y struct Foo static constexpr int bar1 1 static constexpr int2 bar2 1 2 int foo1 return

  • 需要帮助优化算法 - 两百万以下所有素数的总和

    我正在尝试做一个欧拉计划 http projecteuler net问题 我正在寻找 2 000 000 以下所有素数的总和 这就是我所拥有的 int main int argc char argv unsigned long int su

  • 方程“a + bx = c + dy”的积分解

    在等式中a bx c dy 所有变量都是整数 a b c and d是已知的 我如何找到整体解决方案x and y 如果我的想法是正确的 将会有无限多个解 由最小公倍数分隔b and d 但我只需要一个解决方案 我可以计算其余的 这是一个例

  • C# 列表通用扩展方法与非通用扩展方法

    这是一个简单的问题 我希望 集合类中有通用和非通用方法 例如List

  • x:将 ViewModel 方法绑定到 DataTemplate 内的事件

    我基本上问同样的问题这个人 https stackoverflow com questions 10752448 binding to viewmodels property from a template 但在较新的背景下x Bind V

  • C# xml序列化必填字段

    我需要将一些字段标记为需要写入 XML 文件 但没有成功 我有一个包含约 30 个属性的配置类 这就是为什么我不能像这样封装所有属性 public string SomeProp get return someProp set if som

  • LINQ：使用 INNER JOIN、Group 和 SUM

    我正在尝试使用 LINQ 执行以下 SQL 最接近的是执行交叉联接和总和计算 我知道必须有更好的方法来编写它 所以我向堆栈团队寻求帮助 SELECT T1 Column1 T1 Column2 SUM T3 Column1 AS Amoun

  • 如何在当前 Visual Studio 主机内的 Visual Studio 扩展中调试使用 Roslyn 编译的代码？

    我有一个 Visual Studio 扩展 它使用 Roslyn 获取当前打开的解决方案中的项目 编译它并从中运行方法 程序员可以修改该项目 我已从当前 VisualStudioWorkspace 成功编译了 Visual Studio 扩

  • 如何在 Android 中使用 C# 生成的 RSA 公钥？

    我想在无法假定 HTTPS 可用的情况下确保 Android 应用程序和 C ASP NET 服务器之间的消息隐私 我想使用 RSA 来加密 Android 设备首次联系服务器时传输的对称密钥 RSA密钥对已在服务器上生成 私钥保存在服务器

  • 编译时展开 for 循环内的模板参数？

    维基百科 here http en wikipedia org wiki Template metaprogramming Compile time code optimization 给出了 for 循环的编译时展开 我想知道我们是否可以

  • 相当于Linux中的导入库

    在 Windows C 中 当您想要链接 DLL 时 您必须提供导入库 但是在 GNU 构建系统中 当您想要链接 so 文件 相当于 dll 时 您就不需要链接 为什么是这样 是否有等效的 Windows 导入库 注意 我不会谈论在 Win

  • DotNetZip：如何提取文件，但忽略zip文件中的路径？

    尝试将文件提取到给定文件夹 忽略 zip 文件中的路径 但似乎没有办法 考虑到其中实现的所有其他好东西 这似乎是一个相当基本的要求 我缺少什么 代码是 using Ionic Zip ZipFile zf Ionic Zip ZipFile

  • Mono 应用程序在非阻塞套接字发送时冻结

    我在 debian 9 上的 mono 下运行一个服务器应用程序 大约有 1000 2000 个客户端连接 并且应用程序经常冻结 CPU 使用率达到 100 我执行 kill QUIT pid 来获取线程堆栈转储 但它总是卡在这个位置

随机推荐

  • 在 Vulkan 中，图形队列系列与当前队列系列分离是否有益？

    据我所知 队列系列可能支持呈现到屏幕但不支持图形 假设我有一个同时支持图形和呈现的队列系列 以及另一个仅支持呈现的队列系列 我应该为两个进程使用第一个队列系列 还是应该将第一个队列系列委托给图形 将后者委托给呈现 或者这两种方法之间没有明显

  • VLC 媒体播放器有 C# 界面吗？ [关闭]

    Closed 这个问题正在寻求书籍 工具 软件库等的推荐 不满足堆栈溢出指南 help closed questions 目前不接受答案 是否可以使用 C 控制台应用程序中的包装器从 VLC 播放中当前播放的文件中读取曲目统计信息 时间 标

  • Rust 中的表达式模板实现类似于 boost::yap

    我正在尝试自学 Rust 作为一个具有挑战性的学习项目 我想复制 C 表达式模板库的设计模式提升 雅普 https www boost org doc libs 1 74 0 doc html yap html 我不需要一个完整的实现 我只

  • SWI-Prolog 中的跨模块“接口”调用

    这可能是 SWI Prolog 模块系统特有的 假设我们有三个 Prolog 模块 在 SWI Prolog 模块系统中 robin 在文件中robin pl arthur 在文件中arthur pl helper 在文件中helper p

  • ijson 失败并出现尾随垃圾解析错误

    for prefix event value in parser print prefix 执行上面的代码后出现以下错误 我不明白错误是什么 ijson common IncompleteJSONError 解析错误 尾随垃圾 nt 194

  • Java：从集合中获取第一项

    如果我有一个集合 例如Collection

  • Graph API：如何获取其他用户的 Outlook 类别

    我想通过 Graph API 获取用户类别 显示名称和颜色列表 GET users id userPrincipalName outlook masterCategories 微软API文档网站 https learn microsoft

  • 控制 OverlayItem 大小

    我正在构建一个在单个 ItemizedOverlay 中包含几十个 OverlayItems 的地图 我的地图设计为可以非常近距离地查看 大约缩放级别 18 并且 OverlayItems 彼此非常接近 地图放大时看起来不错 但是 如果用户

  • 使用 Boto3 以字符串形式打开 S3 对象

    我知道使用 Boto 2 可以使用以下命令将 S3 对象作为字符串打开 get contents as string http boto readthedocs org en latest ref file html highlight c

  • 使用 IE9、10、11 的 CSS 将比例打印到 50% 等百分比

    Zoom css 属性不适用于 IE9 10 11 观察到打印预览 UI 令人不安 默认比例为 缩小以适合 当我将此比例从 缩小 更改为适合 50 时 页面显示正常 打印预览 任何人都可以帮助我如何使用 CSS 代码将比例设置为 50 为页

  • 在后台运行 URL 请求

    我想在一定的时间间隔内发出 url 请求 例如 每 10 分钟应用程序应该发出一次 url 调用并获取一些 json 数据 应用程序在后台运行时应该能够执行此操作 这可以做到吗 如果是这样 这是否违反 Apple 服务条款 有什么限制吗 i

  • Scala UpperBound 和 LowerBound 概念

    下面是我尝试运行的代码 class Student def printDetails println I am a student def printSomeOtherDetails println I love Studying clas

  • iPhone 和 iPad 滚动结束

    我正在制作一些无限滚动的 jQuery 跨浏览器画廊 我工作得很好 但在 iPhone 上 我想也在 iPad 上 而不是相等的值 我有一些不成比例的值不匹配 window scrollTop document height window

  • 使用 Qt 的网络服务

    我正在寻找使用 Qt 服务器端 实现 Web 服务的代码 如果您有任何信息 我将不胜感激 Regards 您可以使用libqxt http libqxt bitbucket org doc 0 6 qxtweb html实现服务器端Web服

  • 如何使用 SharedPreferences 保存多个值？

    我正在开发一个字典应用程序 在我的应用程序中 我假设用户想要保存最喜欢的单词 我决定使用共享首选项保存这些值 我知道 SQLite 和文件更好 但我坚持使用 SharedPreferences 所以继续使用它 下面是我的代码 Overrid

  • 是否可以从 servlet 内部以编程方式设置请求上下文路径？

    这是一个特殊情况 我陷入了处理 企业 网络应用程序的困境 企业应用程序正在调用request getContext 并将其与另一个字符串进行比较 我发现我可以使用 getServletContext getContextPath 获取 se

  • 无法在 selenium 和 requests 之间传递 cookie，以便使用后者进行抓取

    我用 python 结合 selenium 编写了一个脚本来登录网站 然后从driver to requests这样我就可以继续使用requests进行进一步的活动 I used item soup select one div class

  • 为什么我需要使用 setState 回调来设置依赖于第一个项目的 setState 完成的第二个状态项目的状态？

    在此 componentDidUpdate 方法中 执行 setState 将引号设置为从 fetch 返回的内容后 我必须使用回调再次执行 setState 将 randomQuoteIndex 设置为调用 randomQuoteInde

  • 使用 DirectCast、CType、TryCast 转换数据类型

    自从我在 2005 年从 VB6 迁移到 VB NET 以来 我一直在使用 CType 将一种数据类型转换为另一种数据类型 我这样做是因为它打字速度更快 以前存在于 VB6 中 而且我不知道为什么我必须使用 DirectCast 如果它们之

  • 使用链表进行堆排序

    我想知道是否有人曾经使用链表进行堆排序 如果他们可以提供代码 我已经能够使用数组进行堆排序 但尝试在链表中进行排序似乎不切实际 而且在你知道的地方很痛苦 我必须为我正在做的项目实现链接列表 任何帮助将不胜感激 我也用C 答案是 你不想在链表

热门标签