问题标签 [binary-heap]

考虑一个包含 n 个数字的二进制堆（根存储最大的数字）。给你一个正整数 k < n 和一个数字 x。您必须确定堆的第 k 个最大元素是否大于 x。您的算法必须花费 O(k) 时间。您可以使用 O(k) 额外存储空间

我需要知道二叉堆和二叉堆之间的主要区别，而不管二叉堆只能有两个孩子（树表示）和二叉堆可以有任意数量的孩子的结构差异。

我实际上只是想知道以这样的方式组织二项式树结构有什么特别之处，即第一个孩子在一个节点上，第二个有两个，第三个有四个，依此类推？

如果我们对堆使用一些正常的树而没有两个孩子的限制，然后应用联合程序并只使一个堆成为其他堆的左孩子怎么办？

我查看了 C++0x 标准，发现 make_heap 的比较不能超过 3*N 的要求。

即 heapify 一个无序的集合可以在 O(N) 中完成

为什么是这样？

来源没有给我任何线索（g ++ 4.4.3）

while (true) + __parent == 0 不是线索，而是对 O(N) 行为的猜测

__adjust_heap 看起来像一个 log N 方法：

对我来说是一个沼泽标准日志 N。

任何关于为什么这是 O <= 3N 的线索将不胜感激。
编辑：

实验结果：

这个实际的实现使用

• <2N 比较堆的堆
• <1.5N 以相反的顺序堆积堆。

我创建了一个二进制堆，它代表一个优先级队列。这只是经典的众所周知的算法。这个堆调度不同事件的时间序列（排序键是时间）。

它支持 2 种操作：插入和删除。堆的每个节点的键都大于或等于它的每个子节点。但是，添加具有相同键的事件并不会保留它们添加的顺序，因为每次调用 Remove 或 Insert 之后，heap-up 和 heap-down 过程都会破坏顺序。

我的问题是：在经典算法中应该改变什么来保持具有相同优先级的节点的顺序？

我研究过二进制堆，但我仍然对如何为这个程序做什么感到很困惑如果我能得到一些指导，我将非常感激我仍在学习 java 并且在这样做时遇到了很多麻烦。

k-ary heap 类似于二叉堆（其中 k = 2），但（除了一个可能的例外）非叶节点有 k 个子节点而不是 2 个子节点。将 k-ary heap 实现为任意 k ≥ 2 的最小优先级队列，以支持以下操作：

• insert (x)：将元素x 插入到堆中。

• extract-min()：移除并返回堆中键最小的元素。

k-ary heap 将使用一个预定义大小的数组来实现。还通过测量给定输入文件 k = 2、4、6、8、10 的情况下执行一系列操作所需的时间，研究数据结构在不同 k 值下的相对效率。在输入文件中，“IN”代表插入和“EX”代表提取最小操作。

我只是想学习二进制堆并且对在二进制堆中执行删除操作有疑问。我读过我们可以从二进制堆中删除一个元素，我们需要重新堆放它。

但在以下链接中，它显示不可用：

http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs

我对此有点困惑。

提前感谢所有的澄清。

好的，所以，假设我有一个文本文件（不一定包含每个可能的符号），我想计算每个符号的频率，在计算频率之后，我需要从最频繁访问每个符号及其频率最不频繁。这些符号不一定是 ASCII 字符，它们可以是任意字节序列，尽管长度相同。

我正在考虑做这样的事情（在伪代码中）：

我想知道：有没有更好、更简单的方法来计算和存储每个符号在文件中出现的次数？

假设我们有一个包含 n 个元素的二叉堆，并希望插入 n 个更多元素（不一定一个接一个）。这需要多少时间？

我认为它是θ（n logn），因为一次插入需要logn。

有人可以解释一下，在标题中提到的那些中，我应该如何决定是否使用一个或另一个堆实现？

我想要一个答案来指导我根据问题选择有关结构性能的实现。现在，我正在做一个优先级队列，但我不仅想知道最适合这种情况的实现，还想知道允许我在任何其他情况下选择实现的基础知识......

另一件要考虑的事情是我这次使用的是haskell，所以，如果你知道任何可以改进这种语言实现的技巧或东西，请告诉我！但和以前一样，也欢迎对使用其他语言的评论！

谢谢！对不起，如果这个问题太基本了，但我根本不熟悉堆。这是我第一次面临实施一个任务的任务......

再次感谢！

这是一个家庭作业问题，我被要求展示 8 元素二进制堆需要 8 次比较。

但是当我使用这样的示例时：1 2 3 4 5 6 7 8 我不确定我应该自下而上还是自上而下。但无论如何，我都试过了。

自上而下：我已经完成了 8 个步骤，但是当我计算比较次数时，我得到 13：S

在底部：我已经完成了 7 个步骤，但是当我计算比较次数时，我得到 10：S

在这里尝试算法之后是我得到的比较：

1. H[L]=8 > H[i]=4
2. H[L]=8 > H[i]=2, H[r]=5 > H[最大]=8
3. H[L]=4 > H[i]=2
4. H[L]=6 > H[i]=3, H[r]=7 > H[最大]=6
5. H[L]=8 > H[i]=1, H[r]=7 < H[最大]=8
6. H[L]=4 > H[i]=1, H[r]=5 > H[最大]=4

嗯，关于我应该如何计算比较次数以便我可以向他们展示 8 的任何帮助？我应该使用什么方法（自下而上或自上而下）？