问题标签 [heap]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
java - 计算堆中的空闲位置?跟踪最后插入?
您如何跟踪插入堆的位置:我认为使用检查每个子树高度的函数会将算法从 O(log N) 降级为 O(N)。
因此,您是在每个节点中保留一个变量,还是在具有最后一个插入点的堆中保留一个变量(如何定义?)。
python - python heapq._siftdown() 功能的规范是什么?
我找不到有关此功能的文档...
我特别想知道参数是什么以及这些参数究竟代表什么......
使用python 3
c - 降序堆排序
我一直在尝试学习如何实现堆排序。
特别是,我有一个堆排序算法,它按升序对输入进行排序,但我不知道需要更改什么才能使其降序。
这是代码:(其中一些来自教科书)
如果有人能指出代码的哪一部分需要更改,那将非常有帮助:)。
java - 添加到 PriorityQueue 的对象不按优先级排序
我正在尝试使用 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]
任何为什么会发生这种情况的提示?
java - Binary Min Heap 的链表实现(操作有问题...)
所以我正在尝试实现一个二进制最小堆。我了解二进制最小堆在其结构和属性方面的含义。但是,当我尝试使用指针和节点来实现它时,我碰壁了。
我使用的是Node
, right/left and pointers
,int element
和parent pointer
. 我还有一个LastNode
in place 指向插入的最后一个节点。
我的争吵是当我插入一个元素时,我不知道该怎么做,就最后一个节点而言。这就是我的意思。
步骤 1.) 假设 Heap 是空的,因此您创建一个root
即 x 其中 x 包含元素并且您设置root.left/right = null
and LastNode = root.left
。
这是我卡住的部分。我知道当您创建另一个节点来存储另一个元素时,它将位于 X 的左侧或 LastNode 指向的位置。我的问题我接下来用 LastNode 做什么,我是否将它指向 x.right ?我试图继续insert(int x)
在 logN 中运行,并且 lastNode 操作将在每个级别变得更长和更广泛。
有人可以分解吗?谢谢
java - Java优先级队列实现——内存局部性
我正在尝试在 Java 中实现一个有效的优先级队列。我得到了一个很好的二进制堆实现,但它没有理想的缓存性能。为此,我开始研究二进制堆中的 Van Emde Boas 布局,这使我找到了二进制堆的“阻塞”版本,其中的诀窍是计算子索引和父索引。
尽管我能够做到这一点,但缓存行为(和运行时间)变得更糟。我认为问题是:引用的局部性可能没有实现,因为它是 Java -我不太确定使用对象数组是否真的使对象在 Java 中的内存中是连续的,有人可以确认一下吗?
此外,我非常想知道 Java 的本机 PriorityQueue 使用什么样的数据结构,如果有人知道的话。
data-structures - 是否可以从堆中删除随机节点?
我有一种情况,我想从堆中删除一个随机节点,我有什么选择?我知道我们可以轻松删除堆的最后一个节点和第一个节点。但是,如果我们说删除最后一个节点,那么我不确定是否正确定义了从堆中删除随机节点的行为。
例如
所以在这种情况下,我可以删除节点 12 和 22,这是已定义的,但是我可以删除一个随机节点,例如 13,并且仍然以某种方式维护堆的完整树属性(以及其他属性)吗?
c++ - 关于 C++ 中的 make_heap 算法
http://www.cplusplus.com/reference/algorithm/make_heap/
在这个链接中。它说:
在内部,堆是一棵树,其中每个节点都链接到不大于其自身值的值。在 make_heap 生成的堆中,一个元素在树中的具体位置,而不是由消耗内存的链接确定,是由它在序列中的绝对位置确定的,其中 *first 始终是堆中的最大值。
关于“由它在序列中的绝对位置决定”。我在这里感到困惑。它还说“堆是一棵树,其中每个节点都链接到不大于其自身值的值”
这2句话矛盾吗?在这里很困惑。C++ 中的堆到底是什么树?
希望有好心人能帮帮我 非常感谢
java - 使用链表实现二叉堆
问候,
我无法找出一种算法,该算法将为我提供二叉堆的链表实现中树节点的位置。我已经使用数组实现了一个堆,现在我想尝试使用链表;如果我使用数组来表示堆,有没有办法找到其数组索引的树节点?
java - 通用堆中的比较运算符
对于我的数据结构类,我们的作业是创建一个通用堆 ADT。在 siftUp() 方法中,我需要进行比较,如果父级较小,我需要进行交换。我遇到的问题是比较运算符对泛型类型无效。我相信我需要使用 Comparable 接口,但从我读到的内容来看,与数组一起使用并不是一个好主意。我也搜索了这个网站,我找到了与这篇文章相关的好信息,没有一个能帮助我找到解决方案
我删除了一些不相关的代码谢谢