如何识别属于最大堆的元素和属于最小堆的元素？
本摘录自《破解编码访谈》第5版
作者向我们介绍了一个基于堆的解决方案：
堆非常擅长基本排序和跟踪max和mins。这实际上很有趣——如果你能跟踪元素的大一半和小一半。大一半保存在最小堆中，这样大一半中的最小元素在根。小一半保存在最大堆中，这样最小一半中的最大元素在根。现在有了这些数据结构，你就有了潜在的中值元素在根。”如果堆不再相同大小，您可以通过从堆中弹出一个元素并将其推到另一个堆上来快速“重新平衡”堆
我对这种方法有几个问题，我一次问他们一个，以保持它有条理。首先，使用这种方法，如果您循环访问数组中的元素，您如何知道特定元素属于算法所描述的最小堆或最大堆？假设我们的数据元素是[20，39，14，7，86，90]。当您迭代数组时，您会放置哪个堆，假设 20？
共有2个答案
这里有一种填写细节的方法。
我们保持以下不变量。
>
最小堆和最大堆的内容的多集联合是迄今为止的输入。
最大堆中的所有元素都不大于最小堆中的所有元素。
最小堆的大小减去最大堆的大小是零或一。
要扫描新元素，我们将其插入到最小堆中。现在大小上的差异是一两个。如果是 2，我们从 min 堆中弹出 min 元素并将其插入 max 堆中，恢复不变的 3。
中位数是最小堆中的最小元素，或者是该元素的平均值和最大堆中的最大值元素，具体取决于大小差是 1 还是零。
每次插入元素时，检查最小堆的最小值和最大堆的最大值，以查看每个元素属于哪个堆。
当你看到20时，两个堆都是空的，所以这无关紧要——假设在平局的情况下，我们将把元素放在较小html" target="_blank">元素的最大堆中。
[20] []
当你看到39时，它比20大，所以它在上面的堆中
[20] [39]
14小于20，因此它位于较低的堆中
[14, 20] [39]
7比20低，所以它进入下堆，但是下堆现在太大了，所以20从下堆出来，进入上堆。
[7, 14][20, 39]
86
[7, 14] [20, 39, 86]
90
[7, 14, 20] [39, 86, 90]
事情以哪种方式得到平衡并不重要——也许您应该坚持使用较低的堆大小
-
我正在研究最小堆实现，对这个概念非常陌生。 以此作为参考:< br > https://www.geeksforgeeks.org/building-heap-from-array/ https://algorithm tutor . com/Data-Structures/Tree/Binary-Heaps/ 我修改了代码并想出了： (这是我遇到问题的代码，所有其他代码都与我的问题无关，至少我是
-
我是Java的初学者，刚开始使用Intellij作为我的IDE。 当我使用它时，有时会延迟。 我更改了我的 xms 和 xmx 以获得更大的堆大小（xms = 1024，xmx = 2048），但它抛出了一个错误。 所以，我把它回滚了。 错误消息是这样的:“初始堆大小设置为大于最大堆大小的值”。 有什么问题？ 如果可能，如何增加最大堆大小？ 我用的是笔记本电脑，它有8GB内存。x64Intelli
-
本文向大家介绍C语言实现基于最大堆和最小堆的堆排序算法示例，包括了C语言实现基于最大堆和最小堆的堆排序算法示例的使用技巧和注意事项，需要的朋友参考一下 堆定义 堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小顶堆）或者：Key[i]>=Key[2i+1]&&key>=key[2i+2]（大顶堆） 即任何一非叶节点的关
-
我正在使用IntelliJ 2020.1 Ultimate，并且有一个JBoss 7.0.2服务器，我想从IntelliJ运行。 我将其添加为配置： 但是当我尝试启动服务器时，我收到以下错误： IDEA.app/Contents/plugins/Kotlin/lib/jps/kotlin-jps-plugin.jar:/Applications/IntelliJ IDEA.app/Contents
-
我有一个对象流，我想找到一个最大值的一些属性，计算起来很昂贵。 作为一个特定的简单示例，假设我们有一个字符串列表，我们希望找到最酷的一个，给定函数。
-
问题内容： 我有一个对象流，我想找到一个具有某些属性最大值的对象，该属性的计算成本很高。 作为一个简单的具体示例，假设我们有一个字符串列表，并且希望找到给定功能的最酷的字符串。 以下应该工作： 现在，这有两个问题。首先，假设计算起来很昂贵，这可能不是很有效。我想该方法将需要重复使用比较器，该比较器将依次重复调用，最后每个字符串将被多次调用。 其次，必须提供比较器会导致代码有些冗余。我更喜欢这样的语