问题标签 [max-heap]

我正在从书中的伪代码中实现最大堆，并且在调用“buildMaxHeap”函数后得到了奇怪的结果。例如，具有元素 {20, 5, 10, 12, 15, 8, 2, 6, 2, 9} 的整数数组 intHeap 会产生元素 {20, 1066192077, 15, 12, 9, 10, 2, 6 , 2, 5}。我注意到前 5 个元素几乎是按降序排列的，这令人鼓舞。

到目前为止，这是我的实现（删除了一些不相关的代码）：

我真的很难弄清楚 10 位数字是如何在 array[1] 位置结束的，因为它甚至不属于原始数组。

编辑-> 我想我在那个数组索引问题之后让它工作了。

这似乎与我书中的例子一致。由于某种原因，我还不得不将 buildMaxHeap 中的变量 i 从 unsigned int 更改为普通 int （它显示的值低于 0 ...我认为 unsigned only 可能是正数？有谁知道为什么会发生这种情况？）。

无论如何，感谢您指出数组索引问题！

所以我和我的朋友在这个问题上意见不一致。它要求在 n 个元素的最大堆中搜索第 7 大元素的时间复杂度？

我认为应该是 O(n)，她认为应该是 O(1)。我的逻辑是假设 n 是 7，那么第 7 大元素将是堆中的最后一个元素，所以如果我们考虑最坏的情况，它应该是 O(n)。然而，她说，因为它是一个最大堆，所以找到第 7 个最大的元素应该花费恒定的时间。但是使用她的逻辑，即使是第 50 大元素或第 100 大元素也可以在 O(1) 时间内找到。我们遇到这个问题的书也说解决方案将是 O(logn)。

有人可以告诉我哪个解决方案是正确的吗？

我有这个代码heapSort可以正常工作。我也了解algorithm开始时的工作原理，index而1不是0。我的问题是，maxheap下面的方法本身适用于所有大于零的索引，但不适用于索引 0。但是该Sort方法调用 withindex 0和arraygets sorted。when index i = 0，调用maxheapwill have left=2*i=0 and right=2*i+1=1，这导致在 和 at 相同i，这意味着the和相同并且只有树。这让我很困惑。这是代码：left0rightindex 1rootleftright

编辑：这两个博客使用相同的代码： sanfoundry.com/java-program-implement-heap-sort, sciencetechpedia.blogspot.com/2012/11/heap-sort-using-java.html

我想知道java标准集合中的哪个类可以成为Min-Heap或Max-Heap的父类？我开发了 Heap 类，它可以根据策略将堆转换为最小值或最大值，并使用 add、toString、toArray 等方法来服务于标准集合方法名称的目的。我需要为 Heap 创建一个父类。我可以扩展哪个类或集合？

我正在使用左右子节点的节点结构。

我想知道是否允许最大或最小堆树具有重复值？我试图仅通过在线资源查找有关此信息的信息一直没有成功。

令 A = {a1, a2, . . . , an} 是一组完全有序的不同项目，使得 ai<aj iff i < j。假设在对 A 中项目的 m 长序列访问中，ai 被访问 q(i)≥1 次。我想要一个算法来找到一个二叉搜索树 T，其中每个项目 ai 驻留在 T 的一个叶子中，这样如果我们使用 T 服务访问，每次从根到相应的叶子，服务所需的总时间整个序列被最小化。该算法确实必须构造一棵最小化总访问时间的树。

我认为频率的最大堆是一种选择，但我不确定它是否是最好的。

我对这个问题的解决方案是：首先对数组 A 进行降序排序，然后从排序后的数组中创建一个二叉搜索树（A[0] 作为根，left[i]=2*i，right[i]=2*( i+1))。

我的解决方案是最优的吗？

我已经实现了一个 minHeap 类，所以我很好奇，如果不修改代码，是否可以将 minHeap 类用作最大堆？

我编写了以下程序来最大化 Java 中的堆。

我得到与 inp 相同的输出。我觉得我期望使用递归方法来更改 inp ArrayList 有问题。

看最后一行。这是priority_queue max_heap 的初始化。为什么它忽略 c++ const Compare&。我以为会

它看起来与下面的不同，我理解。

我读了这个页面： http ://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

无法获得priority_queue 构造函数范式的明确定义。

另外，为什么有时它会重载“<”作为比较器。有时重载“（）”作为比较器？ 谢谢

我正在尝试使用 Visual Studio 2008 v9.0.30729.1 SP 在 VC++ 中构建最大堆。

在树中，每个节点如下所示：

单个节点创建逻辑如下所示：

我已经设法在树中创建和插入元素（插入逻辑工作正常）。我坚持从这棵树中删除一个节点（准确地说是一片叶子）的逻辑。

我已经尝试了四种不同的方法：

（取消注释 APPROACH 1/2/3/4 以获得所需的效果）。

这些似乎都不起作用。我需要为前一个节点的左/右指针分配一个零/空值。

如何使这项工作？请帮忙。