问题标签 [heap]

您如何跟踪插入堆的位置：我认为使用检查每个子树高度的函数会将算法从 O(log N) 降级为 O(N)。

因此，您是在每个节点中保留一个变量，还是在具有最后一个插入点的堆中保留一个变量（如何定义？）。

我找不到有关此功能的文档...

我特别想知道参数是什么以及这些参数究竟代表什么......

使用python 3

我一直在尝试学习如何实现堆排序。

特别是，我有一个堆排序算法，它按升序对输入进行排序，但我不知道需要更改什么才能使其降序。

这是代码：（其中一些来自教科书）

如果有人能指出代码的哪一部分需要更改，那将非常有帮助:)。

我正在尝试使用 PriorityQueue 实现堆，如下所示：

我将 Node 定义为包含上述方法的同一类中的私有类。节点定义为：

但是，当我将节点添加到 PriorityQueue 时，它​​们不是按频率排序的。根据我的 println 语句的输出，Node.compareTo() 返回了正确的值。例如，给定数据集：

• 名称、频率
• 需要，3
• 猫，1
• 整洁，2

我的代码产生：
// add need
[need]
// add cat
cat < need
[cat, need]
// 添加整洁的
整洁 > cat
[cat，need，need]
当 PriorityQueue 应该是 [cat，neat，need]
任何为什么会发生这种情况的提示？

所以我正在尝试实现一个二进制最小堆。我了解二进制最小堆在其结构和属性方面的含义。但是，当我尝试使用指针和节点来实现它时，我碰壁了。

我使用的是Node, right/left and pointers,int element和parent pointer. 我还有一个LastNodein place 指向插入的最后一个节点。

我的争吵是当我插入一个元素时，我不知道该怎么做，就最后一个节点而言。这就是我的意思。

步骤 1.) 假设 Heap 是空的，因此您创建一个root即 x 其中 x 包含元素并且您设置root.left/right = nulland LastNode = root.left。

这是我卡住的部分。我知道当您创建另一个节点来存储另一个元素时，它将位于 X 的左侧或 LastNode 指向的位置。我的问题我接下来用 LastNode 做什么，我是否将它指向 x.right ？我试图继续insert(int x)在 logN 中运行，并且 lastNode 操作将在每个级别变得更长和更广泛。

有人可以分解吗？谢谢

我正在尝试在 Java 中实现一个有效的优先级队列。我得到了一个很好的二进制堆实现，但它没有理想的缓存性能。为此，我开始研究二进制堆中的 Van Emde Boas 布局，这使我找到了二进制堆的“阻塞”版本，其中的诀窍是计算子索引和父索引。

尽管我能够做到这一点，但缓存行为（和运行时间）变得更糟。我认为问题是：引用的局部性可能没有实现，因为它是 Java -我不太确定使用对象数组是否真的使对象在 Java 中的内存中是连续的，有人可以确认一下吗？

此外，我非常想知道 Java 的本机 PriorityQueue 使用什么样的数据结构，如果有人知道的话。

我有一种情况，我想从堆中删除一个随机节点，我有什么选择？我知道我们可以轻松删除堆的最后一个节点和第一个节点。但是，如果我们说删除最后一个节点，那么我不确定是否正确定义了从堆中删除随机节点的行为。

例如

所以在这种情况下，我可以删除节点 12 和 22，这是已定义的，但是我可以删除一个随机节点，例如 13，并且仍然以某种方式维护堆的完整树属性（以及其他属性）吗？

http://www.cplusplus.com/reference/algorithm/make_heap/

在这个链接中。它说：

在内部，堆是一棵树，其中每个节点都链接到不大于其自身值的值。在 make_heap 生成的堆中，一个元素在树中的具体位置，而不是由消耗内存的链接确定，是由它在序列中的绝对位置确定的，其中 *first 始终是堆中的最大值。

关于“由它在序列中的绝对位置决定”。我在这里感到困惑。它还说“堆是一棵树，其中每个节点都链接到不大于其自身值的值”

这2句话矛盾吗？在这里很困惑。C++ 中的堆到底是什么树？

希望有好心人能帮帮我 非常感谢

可能重复：
Binary Min Heap 的链表实现（操作有问题……）

问候，

我无法找出一种算法，该算法将为我提供二叉堆的链表实现中树节点的位置。我已经使用数组实现了一个堆，现在我想尝试使用链表；如果我使用数组来表示堆，有没有办法找到其数组索引的树节点？

对于我的数据结构类，我们的作业是创建一个通用堆 ADT。在 siftUp() 方法中，我需要进行比较，如果父级较小，我需要进行交换。我遇到的问题是比较运算符对泛型类型无效。我相信我需要使用 Comparable 接口，但从我读到的内容来看，与数组一起使用并不是一个好主意。我也搜索了这个网站，我找到了与这篇文章相关的好信息，没有一个能帮助我找到解决方案

我删除了一些不相关的代码谢谢