程序员经验分享-hwhale

在 O(n) 时间内将堆转换为 BST？

2023-11-24

我认为我知道答案并且最小复杂度是O(nlogn).

但是有什么方法可以让我从堆中创建二叉搜索树O(n)复杂？


没有算法可以在 O(n) 时间内从堆构建 BST。原因是给定 n 个元素，您可以在 O(n) 时间内从它们构建一个堆。如果您有一组值的 BST，则可以通过中序遍历在 O(n) 时间内对它们进行排序。如果您可以在 O(n) 时间内从堆构建 BST，那么您就可以通过以下方式获得 O(n) 排序算法：

  1. 在 O(n) 时间内构建堆，
  2. 在 O(n) 时间内将堆转换为 BST，并且
  3. 在 O(n) 时间内遍历 BST 以获得排序序列。

因此，不可能在 O(n) 时间内（或 o(n log n) 时间内将堆转换为 BST，其中 o 是小 O 表示法).

However, it is possible to build a BST from a heap in O(n log n) time by repeatedly dequeueing the maximum value from the BST and inserting it as the rightmost node in the tree. (You'd need to store a pointer there for fast access; just inserting at the root repeatly would take O(n2) time.)

希望这可以帮助！

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

Algorithm

datastructures

bigo

binarysearchtree

binaryheap

在 O(n) 时间内将堆转换为 BST？ 的相关文章

  • 修改排列算法以防止重复打印输出的策略

    我一直在审查实践算法 目前正在研究一种我非常喜欢的排列算法 void permute char set int begin int end int range end begin if range 1 cout lt lt set lt l

  • O(mn) 比 O((m+n)^2) 更好吗？

    算法的输入是m and n 我的算法的时间复杂度是O mn 我有一个时间复杂度为的基准算法O m n 我的实现在时间复杂度方面是否优于基准 许多评论者和回答者希望只考虑以下情况 m n或者至少当它们通过一个常数因子相关时 这不是它的工作原理

  • 在 O(n) 时间内运行的指数乘法算法？

    我正在读一本算法教科书 我被这个问题难住了 假设我们要计算值 x y 其中 x 和 y 为正数 分别具有 m 和 n 位的整数 解决该问题的一种方法是执行 y 1 乘以 x 你能给出一个仅使用 O n 乘法步骤的更有效的算法吗 这会是一个分

  • 给定与总和匹配的长度的唯一 3 位数字 (-1,0,1) 序列的数量

    假设您有一个长度为 n 即空格数 的垂直游戏板 你有一个三面骰子 有以下选项 前进一 停留和后退 如果您低于或高于棋盘游戏空间的数量 则该游戏无效 一旦到达棋盘末端 唯一有效的动作就是 停留 给定确切的骰子投掷次数 t 是否可以通过算法计算

  • 如何找到最长的回文子序列（不是它的长度）

    我想找出字符串中最长的回文子序列 我到处都找到了找出子序列长度的算法 并声明该算法也可以扩展以返回子序列 但我没有找到如何实现的 有人能解释一下我怎样才能得到序列吗 既然你提到了链接最长回文子序列 http www geeksforgeek

  • 检查数独字段的很酷的算法？

    有谁知道一个简单的算法来检查数独配置是否有效 我想出的最简单的算法是 对于大小为 n 的板 伪代码 for each row for each number k in 1 n if k is not in the row using ano

  • 我想优化这个短循环

    我想优化这个简单的循环 unsigned int i while j 0 j is an unsigned int with a start value of about N 36 000 000 float sub 0 i 1 unsig

  • 将非平凡函数应用于 data.table 的有序子集

    Problem 我正在尝试使用我新发现的 data table 功能 永久 来计算一堆数据的频率内容 如下所示 Sample Channel Trial Voltage Class Subject 1 1 1 196 82253 1 1 1

  • 两个非嵌套循环的大 O 表示法

    对于两个非嵌套的 for 循环 大 O 表示法是什么 Example for int i 0 i

  • 如何在Scala中实现尾递归快速排序

    我写了一个递归版本 def quickSort T xs List T p T T gt Boolean List T xs match case Nil gt Nil case gt val x xs head val left righ

  • 如何从数组表示构建不完全二叉树

    如果输入是一个数组 其中null表示没有节点 input 1 2 3 null 5 null 7 请假设我已经检查过输入 对于每个array i 它的父母array i 2 不会是null 递归地 所以根不能是null 如何构建具有这样的逻

  • C 中的菱形数组排序

    我有以下 C 语言作业 我基本上需要一种方法而不是解决方案 我们有一个 13 x 13 的数组 在数组中 我们有一个需要考虑的菱形形状 该菱形之外的所有内容都初始化为 1 不重要 下面的 5 x 5 数组示例 x x 1 x x x 2 2

  • 用惯用的 Scala 更新大型数据结构

    我已经尝试 Scala 一段时间了 并且经常遇到支持不可变数据结构的建议 但是当你有一个像这样的数据结构时3D 场景图 大型神经网络或任何具有大量需要频繁更新的对象的东西 对场景中的对象进行动画处理 训练神经网络 这似乎是 运行时效率极低

  • 32 位数字中 1 的数量

    我正在寻找一种在 32 位数字中包含 1 数量的方法 之间不使用循环 任何人都可以帮助我并向我提供代码或算法吗 这样做 提前致谢 See Integer bitCount int http java sun com javase 6 doc

  • 缩短文本并仅保留重要句子

    德国网站 nandoo net 提供了缩短新闻文章的可能性 如果使用滑块更改百分比值 文本会发生变化并且某些句子会被遗漏 您可以在这里看到它的实际效果 http www nandoo net read article 299925 http

  • 将嵌套字典中的所有键从camelCase转换为snake_case

    我有一本类似这样的字典 firstName abc lastName xyz favoriteMovies Star Wars The lone ranger favoriteCountries country China capitalC

  • 快速求解子集和

    考虑这种解决子集和问题的方法 def subset summing to zero activities subsets 0 for activity cost in activities iteritems old subsets sub

  • 使用主方法求解 T(n) = 2T(n/2) + n/log n 和 T(n) = 4T(n/2) + n/log n 之间的差异

    我最近偶然发现了一个资源 其中 2T n 2 n log ntypeMM 宣布复发无法解决 我接受它作为一个引理 直到今天 另一种资源被证明是矛盾的 在某种意义上 根据资源 下面的链接 其中的 Q7 和 Q18 是建议 分别在问题中的1和2

  • 通过分布式数据库聚合作业优化网络带宽

    我有一个分布式 联合数据库 结构如下 数据库分布在三个地理位置 节点 每个节点集群有多个数据库 关系数据库是 PostgreSQL MySQL Oracle 和 MS SQL Server 的混合体 非关系数据库是 MongoDB 或 Ca

  • 如何从一组重叠的圆计算多边形集？

    这个问题是一些计算细节的扩展这个问题 https stackoverflow com questions 1667310 combined area of overlapping circles 假设有一组 可能重叠的 圆 并且希望计算这组

随机推荐

  • 在 CSS 中使用 OS 9 资源分支字体和 @font-face

    我有一些旧的 OS 9 字体 其中包含资源分支中的字体数据 当我尝试在 font face 中链接此类字体并在浏览器中打开 HTML 时 文本仍然以默认字体显示 在搜索过程中 我发现可以使用 rsrc 属性将字体数据复制到常规 ttf 文件

  • OpenMP 中 private 子句中的变量与并行区域中定义的变量之间有什么区别吗？

    我想知道是否有任何理由选择private var OpenMP 中关于 私有 变量本地定义的子句 即 int var pragma omp parallel private var vs pragma omp parallel int va

  • 更改 Rails 中的当前选项卡

    我的应用程序顶部有一个选项卡列表 我将其包含在 application html erb 的常规布局中 它们看起来像这样 li class current li li li li li 当我点击该页面时 我想将所选选项卡更改为 当前 选项卡

  • 将数据从活动发送到另一个活动而不启动它

    如果我有两个活动 Activity1 和 Activity2 并且我想在不启动 Activity2 的情况下将数据从 Activity1 发送到 Activity2 我知道如果我想启动 Activity2 我在 Activity1 java

  • 如何为基于 YAML 的管道创建管道变量？

    使用设计器 类构建管道 您可以定义具有要传递到任务中的默认值的管道变量 如何对基于 YAML 的管道执行相同的操作 我想创建三个构建管道 每个管道都有一个设置为不同值的变量 所有三个都指向一个 YAML 文件 这文档 states 您可以选

  • 如何计算两个 Rust 数组/切片/向量的点积？

    我试图找到两个向量的点积 fn main let a vec 1 2 3 4 let b a clone let r a iter zip b iter map x y Some x y gt x y sum println r 这失败了

  • 评估 if 语句中可选对象的 Bool 属性

    我正在寻找一种评估 Swift 的方法Bool简洁地概括为一个if声明 当Bool是可选对象的属性 var objectWithBool ClassWithBool if let obj objectWithBool if obj bool

  • 在 C 中如何将浮点值限制为小数点后仅两位？

    在 C 中如何将浮点值 例如 37 777779 四舍五入到小数点后两位 37 78 如果您只想对数字进行四舍五入以用于输出目的 那么 2f 格式字符串确实是正确的答案 但是 如果您实际上想要舍入浮点值以进行进一步计算 则可以使用如下所示的

  • 如何在没有 ssh 身份验证的情况下设置 git 服务器

    不久前 我偶然发现了关于如何通过 Web 服务器以某种方式设置 git 身份验证的解释 这样客户端就不需要 ssh 密钥交换 真遗憾 我既没有为其链接添加书签 也记不起该技术 我只是怀念抛出一个用户名 密码组合来访问一些一次性存储库 当对一

  • `warm_start` 参数及其对计算时间的影响

    我有一个逻辑回归具有一组定义的参数的模型 warm start True 一如既往 我打电话LogisticRegression fit X train y train 并使用之后的模型来预测新的结果 假设我改变一些参数 比如说 C 100

  • Google 是否正在为 HTML 自定义数据属性建立索引？

    我正在使用 PushState hash bangs 构建一个基于 AJAX 的投资组合模块 并且由于我排除了没有 JavaScript 的浏览器 所以我唯一关心的是 HTML 自定义数据属性在 SEO 方面的限制 例如 使用下面的代码 u

  • 按需显示或隐藏标题栏

    我想向我的 Windows 窗体应用程序 用 vb net 编写 添加一个选项 该选项将为用户提供隐藏菜单栏和标题栏的选项 我可以做菜单 但我不确定隐藏标题的最佳方法是什么 我可以将 FormBorderStyle 更改为 none 但这是

  • Laravel 从数据库加载设置

    我正在寻找一种使用 Laravel 5 从数据库加载设置 配置的有效方法 设置包括key and value列中 模型类基本上如下所示

  • 避免seaborn箱线图中被群图覆盖的重复图例

    在下面基于seaborn的图中 我正在制作一个由群图覆盖的箱形图 两者都是色调的子集 有什么办法可以让它们在图例中不重复两次吗 这是我的代码 ax sns boxplot x name xaxis y name col hue hue da

  • TelephonyManager 对于 IMEI 号码返回 null：什么可能导致此情况？

    我正在开发一个 Android 应用程序 并且正在得到null使用时返回 IMEI 号码TelophonyManager 多款华为手机都出现这种情况 均为 Ascend Y530 这些手机都有 SIM 卡 其他方面似乎都运行正常 我的印象是

  • 如何调试 Rust 中的内存问题？

    我希望这个问题不要太开放 我遇到了 Rust 的内存问题 我得到了通话中出现 内存不足 next on an Iterator特质对象 我不确定如何调试它 印刷品只是把我带到了失败发生的地方 我对其他工具不太熟悉 例如ltrace 所以虽然

  • Spark.python.worker.memory 与 Spark.executor.memory 有何关系？

    这张图对于不同 YARN 和 Spark 内存相关设置之间的关系非常清楚 除了涉及到spark python worker memory 如何spark python worker memory适合这个内存模型吗 Python 进程是否受以

  • Zoho mail 显示 Node Js 中的 535 身份验证失败

    我正在使用 Node Express 和 MongoDB 创建一个应用程序 用户创建成功后 想要发送给用户的邮件 我正在使用 zohomail 并且可以使用这些用户名和密码在线登录 zohomail 但是当我尝试发送邮件时出现错误 code

  • 在 Django 中覆盖外部应用程序的模板

    我想覆盖外部应用程序的模板 allauth 安装在站点包中 不幸的是我读到的建议没有起作用 我将以下内容添加到我的settings py PROJECT ROOT os path normpath os path dirname os pa

  • 在 O(n) 时间内将堆转换为 BST？

    我认为我知道答案并且最小复杂度是O nlogn 但是有什么方法可以让我从堆中创建二叉搜索树O n 复杂 没有算法可以在 O n 时间内从堆构建 BST 原因是给定 n 个元素 您可以在 O n 时间内从它们构建一个堆 如果您有一组值的 BS

热门标签