问题标签 [max-heap]

我在 Java 中实现了一个 MaxHeap，它根据它的键进行排序。每个键还与一个值相关联。当我尝试运行我的程序时，我得到一个异常：Exception in thread "main" java.lang.ClassCastException: [Ljava.lang.Object; cannot be cast to [LMaxHeap$Obj;

编辑此行引发异常：o = (Obj[])new Object[n+1];

我该如何解决我的问题？

这是我的代码：

可能重复：
我们如何在 O(k) 时间内从最大堆中找到第 k 个最大元素？

有一个给定的最大堆，我们想找到一个时间复杂度为 o(k) 的算法来检查第 k 个最小元素是否大于任意给定数字。

我需要实现一个函数 HEAP-DELETE-MIN(Array) 删除最大堆中的最小整数。我不要求函数本身，但有人可以为我提供一些 伪代码来帮助我开始吗？这将是一个很大的帮助。该数组应在函数结束时保持最大堆。

我正在尝试将 minHeap 类转换为 maxHeap 类。我得到了 minHeap 类的代码，其中一种方法是 add。它看起来像这样：

第一个节点自动设置为 null，因此添加的所有内容都放在节点 1 以后。如前所述，这段代码给出了一个 minHeap 结构。所以将其更改为 maxHeap，我只是像这样翻转比较器符号：

我输入的项目由一个整数值存储。按插入顺序，它们是：

在 minHeap 结构中，这些存储在节点中，如下所示：

在 maxHeap 结构中，更改符号会像这样存储它们：

请注意，它们的顺序不再与 minHeap 结构中的顺序相同。这很重要还是仍然是有效的 maxHeap？

为我展示树状结构的糟糕尝试道歉。

我目前正在做一个最大堆。当我使用 remove() 方法时，我知道我会与较大的孩子交换。如果两个孩子的优先级相同怎么办？例如

情况1：

堆 = [5,7,7,16,15]

如果我删除 5 并用 15 替换它，我会滴到右边（这是错误的），所以我会滴到左边。

但使用相同的逻辑，如果我有

堆 = [5,7,7,16,15,18]

并且我向左滴流，它将不再是一个有效的堆。

我可以做些什么来确保我有一个有效的堆？

是否有一种算法可以在最多一次交换的情况下执行插入到堆中（允许 O(log n) 比较）

我是一名机械专业的学生，​​我已将我的领域改为计算机。需要通过算法类。这个问题是练习题之一

1. 如果最大堆算法的运行时间是 O(klogn) 那么有没有比这更好的运行时间的算法？

在 Udi Manber 的名著《算法导论》中有这个问题，它指出

算法 *Insert_To_Heap* 可能会在堆上多次交换。修改算法，以便最多执行一次交换。仍然允许 O(log n) 比较。

我想不出任何这样的算法，我什至认为这是不可能的（好像你在最大堆中插入了最大元素，它似乎并没有以任何方式工作）。甚至存在一些答案，表明这是不可能的。但是考虑到这个问题的来源很好，我再次问你是否可以提出一些好的想法并找出作者试图问的问题？

创建最大堆 O(n) 的时间复杂度如何。是子节点仅在 O(i) 中与其父节点进行比较还是 O(log n)。

我需要解决方案验证。我找不到标签，所以如果有人可以帮助我。问题如下。

令 A [1..n] 为具有 n 个元素的最大堆。假设没有重复的键。

编写伪代码以查找 A 中的最小元素。然后使用 O-notation 找到 RT

我的尝试：

假设伪代码是正确的。最大堆有什么改变吗？

运行时间为O(n)。