问题标签 [max-heap]

我在网上搜索了这个在 Python 中实现 MinHeap 和 Maxheap 的方法。

现在我需要为这两个类添加一个 peek 方法。在当前的实现中，我可以弹出并推回。但我的问题是，有没有更好的方法来做到这一点。O(1) 时间内的东西。

我目前需要实现一个最大节点堆，我的节点类在其中跟踪数据、父节点，然后是左右子节点。我的最大堆插入方法需要永远填充 100 个字符串的数组。这是我的代码：`

如果有人代码提供建议或告诉我出了什么问题，我们将不胜感激。

其实我也听说过向上再堆化和向下再堆化这两个名词。但是 max-heapify 和 min-heapify 是什么意思呢？这两个术语（最大堆和最小堆）是否与向上再堆和向下再堆有关？根据我的说法，向上再堆和向下再堆都属于最大堆和最小堆。如果我错了，请纠正我。另外请告诉我所有这四个术语的时间复杂度。

上面是最大堆，它是一系列插入和删除最大操作后的结果。假设最后一个操作是插入。最后一次插入操作的可能键是什么？

我不确定的原因是因为这个问题没有说明它是否已经被堆化，所以它可以或不能已经被排序。但话又说回来，我可能错了。

附加问题：“删除最大操作”是否与“删除”相同，因为我之前没有遇到过这个术语，这有助于澄清我的困惑。

谢谢！

这是我在 python 中实现的 MinHeap 和 MaxHeap。这使用了一个比较器来反转 MaxHeap 中的存储顺序

MinHeap 似乎工作正常，但是 MaxHeap 抛出以下错误。

我似乎不太明白我在这里做错了什么。有人可以帮我弄这个吗。

在 C++ Sort 函数中，第三个可选参数是用于对对象进行排序的比较器。如果我们传入 less 作为比较器，我们将按递增顺序获取对象。（如果比较器被评估为真，则位置不会改变，否则元素将被交换！）我的理解是否正确？

按照同样的方式，如果我们将一个 less 比较器传递给优先级队列，我们​​应该得到一个最小堆，（如果底层数据结构选择为向量，则对象按升序排序。如果我们调用 top()，则会返回vector的第一个元素，也就是最小的数。所以，我认为是最小堆）为什么我们得到最大堆？

I am trying to insert in a maxHeap in java and then bubble up the object. This is what I have done, I am not sure how I should approach the bubble up method.

I do understand the algorithm behind bubble up, which is as follows:

1. get parent node
2. see if L_childNode is less than parent Node. If Yes, then swap parent with L_child.
3. see if R_childNode is less than parent Node. If Yes, then swap parent with L_child.

Please point out what am I doing wrong?

对于一个项目，我是否正在使用堆。在这个项目中，我必须“调查”一个数组是否是一个最大堆。

这 2 条规则适用于最大堆：

1. 父母应大于或等于其孩子/孩子
2. 堆中的每个节点都应包含一个元素

因此，我创建了 2 个用于检查这些规则是否适用的循环。对我来说不幸的是，我的代码不起作用。

我有 2 个 for 循环：

最后一个 for 循环有效，但由于某种原因，我在第一个 for 循环中出错。循环可以找到一个数字。Lets say that i picked 15 to be equal with A[i], then it would work and return false, but when the selected number 0 isn't there, then it sends me the error, and it wont go further for the second loop .

整个代码：

最大堆可以在同一棵树本身内具有任意分支因子。

例如给定 [8,5,3,1] 一些生成的堆可能是

出于我的目的，我认为上面的树 (a) 与下面的树 (d) 和 (e) 相同

编辑 ：

(1) 我尝试了一种算法来生成所有可能的树，然后根据 max-heap 属性进行过滤。但显然这是指数级的，因此在 Python 中，即使是超过 10 个元素的列表也需要一段时间。

(2) 因此，我只想构建那些服从最大堆属性而不是过滤但无法从中制定递归子问题的树。

我的 HeapSort 返回一个顺序不正确的数组。我的原始数组是 {15, 9, 11, 5, 6, 7}，当运行 heapSort 方法时，我得到这个数组：{15, 11, 9, 6, 7, 5}。

我打印了该方法以查看 maxHeap 做了什么并得到了：{15, 9, 11, 5, 6, 7}，当映射到二叉树中时，它实际上是一个 maxHeap。这让我相信排序方法或 buildMaxHeap 方法有问题。