问题标签 [minmax-heap]

你知道一个流行的库（Apache、Google 等，集合），它有一个可靠的 Java 实现最小-最大堆，这是一个允许查看其最小值和最大值O(1)并删除元素的堆O(log n)？

我正在实现一个最小最大堆，一种双端优先级队列。您可以在这里查看有关最小-最大堆的更多信息。

插入和删除最小操作的代码很简单，可以在网上找到。但是，我也在尝试在最小最大堆上实现删除最大操作。

最初，我觉得 min-max heap 中的 delete-max 与 max-min heap 中的 delete-max 相同（如果我们考虑包含最大元素的 min-max heap 的子树，它类似于 max-min heap）。因此，实现将简单且类似于 min-max 堆的 delete-min。

但有个问题：

从上图中可以看出，虽然70是最大元素，但是最小-最大堆的最后一个元素（12）不在包含70的子树中。那么，我可以用它来替换左子树中留下的间隙吗删除70后？

如果我们不使用该元素，而是按照max-min heap 的 delete-max 过程并使用 20 来替换间隙，那么插入到堆中的下一个元素将是 10 的右孩子，并且永远不会有右孩子9。

那么，任何人都可以帮助我吗？

I have a specific question about min-max heap related problem in Java.

If you have inputs in this order:

Would the tree look like the following?

What about after deleteMin and deleteMax?

I am trying to understand what would happen if the max node is somehow smaller than some of the min nodes... If you can help me by explaining it with a tree that would be great :)

我写了一个min-max heap，即找到最小值和最大值的堆是常量操作。现在我想为我的类创建测试，所以我决定实现一个函数来检查堆是否是最小最大堆。在这里，但我不确定它是否 100% 正确。

请注意，这个堆的元素用 class 表示HeapNode，这就是我检查是否self.heap只包含该类的对象的原因。偶数级别例如为 0、2、4 等。此堆的最小值位于self.heap[0]. 最大值是max(self.heap[1], self.heap[2])（前提是两者都存在）。如果节点 at 的祖父母不存在，则h.grandparent_index(i)返回。Nonei

我的算法的想法很简单。我从底部开始，检查我是否处于奇数水平。如果在一个均匀的水平上，那么我必须确保该元素大于其祖父母。如果我处于奇怪的水平，我必须确保它比它的祖父母小。

我的算法正确吗？我错过了一些观点吗？如果它是正确的，改进它的建议会被广泛接受。

最终我的实现可能对其他人有用。

编辑 1

我刚刚注意到我的函数检查偶数（和奇数）级别中的元素是否正确布置，但它不检查最大元素是否位于self.heap[1]或self.heap[2]并且最小元素是否位于self.heap[0]。

编辑 2

我正在根据编辑 1 和@goCards 的答案添加新的更新代码。

我对删除最大操作后的最终图像感到困惑。当87被删除时，48会被带到87曾经拥有的地方吗？之后树的其余部分不会改变吗？

最小-最大堆原始

我正在实现一个同时具有 popMin 和 popMax 方法的队列类。到目前为止，我已经使用两个优先级队列，但即使删除是 log(n) 时间，我也必须从另一个队列中删除，这是线性的。我知道可以使用二进制堆来实现双端优先级队列，但是如果我没记错的话，这需要线性时间来构建吗？有没有办法可以更有效地做到这一点？我也只能使用 Java 库类。

假设我们要根据值对 hashmap 进行排序。我们实现了一个带有比较器的 priorityQueue 来做到这一点。结果，生成的 pq 是从索引 0 到结尾从最大到最小排序。

这是代码：

但是，有人说它是 maxheap，我知道 heap 只是父值大于子值，但我不明白为什么它是 maxheap？它只是在priorityQueue中实现比较器？这与堆有什么关系？

最小-最大堆对于实现双端优先级队列很有用，因为它的时间find-min和find-max操作是恒定的。我们还可以在O(log ₂ n)时间内检索最小和最大堆中的最小和最大元素。但是，有时我们可能还想删除 min-max 堆中的任何节点，这可以在O(log ₂ n)中完成，根据介绍 min-max heaps的论文：

...

对于任何固定值（或一组值），该结构还可以推广以支持在常数时间内进行操作Find(k)（确定结构中的第k个最小值）和在对数时间内进行操作Delete(k)（删除结构中的第 k 个最小值）的k。

...

如何在最小-最大堆上执行第 k 个元素的删除？

如果 dp[n] 存储了形成包含 n 个元素的最大堆的方式的数量，那么我们有。

IE

1. 从 n - 1 中选择 n1 个元素作为左子树。

2. 左子树中的元素可以以 dp[n1] 的方式形成最大堆。

3. 右子树中的元素可以以 dp[n2] 的方式形成最大堆。

如何计算n1和n2？

我在 Wikipedia 上找到了min-max heap的主题。我想知道是否有任何方法可以在O(n).

我知道你可以用最小堆和最大堆来做到这一点，但我不确定这会是什么方法。插入一个元素需要O(log n)时间复杂度，我觉得这种树的构建效率不能比O(n log n).