问题标签 [binary-heap]

假设我想将一个节点插入到二进制堆中，如何在插入和堆化后找到堆中节点的索引？二叉堆表示为一个数组。我需要在 O(log(log(n)) 中找到这个算法。

我知道如何在 log n 复杂度中找到它，但在 log log n 中找不到它。

谢谢你们。

在浏览一个项目的代码时，我遇到了一个实现，BinaryHeap其中两个实现（使用 Array 和 Tree）被打包在接口本身中。我发现它有些复杂。代码是：

这种方法有什么问题吗？在可读性方面如何改进？

我有一个数组$heap = array(9, 9, 9, 8, 9, 9, 8, 9, 9, 9, 9, 9, 8, 8, 9, 7, 9, 8, 8, 9, 9,);，我想像二叉树一样输出它，当我们可以通过这个公式知道两个子节点时，$heap[$key*2+1]第二个$heap[$key*2+2]. 我尝试使用 foreach 运行，但收到​​关于未定义偏移量 21 的错误。这是 foreach：

我做错了什么以及如何解决这个问题？

我见过的大多数 BST 示例都是以下形式

但是 BSTs 看起来像是具有额外约束的二进制堆的一种特定形式，即左子值应小于父值，父值应小于右节点值。

使用数组很容易实现二进制堆。为什么不使用数组创建 BST 以确保维护这个额外的规则？这样做有什么缺点？

    我正在处理来自练习数据结构决赛的练习题

问题

   当使用保持组织为最小堆的数据结构数组时，找到最坏情况的渐近运行时删除。

我最初的想法是删除操作是O(log n)因为删除的算法是

1. 将开始元素与结束元素交换。将结束元素设置为空
2. 减小大小
3. 将新的根向下渗透到树上
4. 返回原始开始元素

步骤 1、2 和 4 都应该是常数时间。第 3 步应该在O(log n)中运行，因为完整树的高度是log n。所以总的来说，删除的运行时间不应该是O(log n)

但是，如果您查看答案键（来自链接），当使用保持组织为最小堆的数组时，删除的最坏情况渐近运行时间是O(n)。有人可以解释为什么会这样吗？

我读过二进制堆在删除最小操作时更快，而 d-ary 堆在降低优先级操作时更快（虽然我不明白为什么），但后来我也读到 4 堆在它们都与二进制堆相比。

那么什么时候使用二叉堆，什么时候使用二叉堆呢？我如何决定 d 应该是什么 d 堆？

我正在开发一个基于代理的模型来模拟细胞培养的体外生长。

我正在使用 MASON 库（Java），但我猜测可能适用于不同的实现。

本质上，我的代理程序被编程为在创建后每 12 +/- 2 个时间步进行划分。每次代理分裂时，都会将一个新代理添加到模拟中。

这导致问题复杂性的快速增长，这很快使模拟变得特别慢。

为了解决这个问题，我决定代理应该在创建的t个时间步之后“死亡”。

但是，MASON 的调度是建立在 BinaryHeap 之上的，一旦添加了对象（代理），就不容易删除它们。我的解决方案是设置一个布尔标志：

在t个时间步之后设置为 true 。

所以

然后我开始我的 step 方法，即每次执行 agent 时调用的方法，如下所示：

但是，我知道只需访问计划中的对象就足以减慢模拟速度。

有人对我如何取消设置代理或阻止它被调用有任何建议吗？

谢谢，达里奥

自从我参加 DSA 课程以来，已经快十年了。我浏览了Wikipedia 的排序算法列表，但没有一个比这更突出。它是优先级队列实现的一部分，似乎排序的一部分发生在 push 函数 ( EnQueue) 中，而另一部分发生在 pop 函数中 (DeQueue ) 中。

这是原始的Mathematica代码，但由于大多数人不熟悉Mathematica，所以我在每个函数下方进行了一些翻译。

该EnQueue函数首先检查元素的数量是否n已达到堆的大小ar，如果是，则将堆加倍。接下来，它增加元素的数量并将新元素存储在该索引处（Mathematica索引是从 1 开始的，而不是从 0 开始的）。然后，它设置i为该索引（新元素的），并进入一个设置j为的循环floor(i/2)，即堆中间的某个元素。现在，如果j < 1（据我所知，这相当于检查 if i == 1），或者ar[j]（中间的元素）是否应该在ar[i]（新元素）之前，那么我们就中断了。否则，我们交换元素i和处交换元素j，并继续；所以在第二次迭代中，我们从i指向中间开始，然后j指向四分之一。

同时，DeQueue返回堆的前面，并将堆的后面移动到前面（并取消设置后面，并减少元素的数量）。然后，从j指向前面开始，它进入一个以设置i为 double开始的循环j。如果i在边界内（指向一个元素）但相对于下一个元素是无序的，i则递增。如果i相对于j（前部；换句话说，如果前部相对于 ）是有序的，i则交换两个位置，并j设置为所在的位置i。我们继续循环，直到j经过中间。

大部分是上面的粗体部分我不明白。我认为它正在做的是对一半的堆进行排序DeQueue，并为 中的新元素做一些排序EnQueue，但我不确定......

我目前正在做一项家庭作业，要求我：

使用二进制堆实现 DIJKSTRA 的单源最短路径问题算法。运行时间应为 O(ElogV)。

够简单！但是，问题必须通过代码来解决。在此之前仍然不是那么困难的概念：

您的程序应该从文件中读取数据（参见下面的示例）并输出一个数字 = 从节点 0 到每个节点的最短路径的长度之和。输入格式：下面每个文件的第一行包含图中的顶点数和边数（格式为“n=XXXX m=XXXXX”）。文件的其余部分组织如下：每个顶点 i 单独出现在一行上，然后是 i 的每个邻居 j>i 的一行（包含 j 和边的长度 (i,j)）。每个邻居列表都以空行结束。不表示没有索引大于 i 的邻居的顶点 i。注意：顶点的索引从 0 到 n-1。注意：每条边仅被提及一次，其端点数量较小，SAMPLE INPUT: 1. first input 2.第二个输入 最短路径树的长度应该分别是10721073和625349。程序应在 3-10 秒内为第一个输入提供输出，第二个输入应在 1 秒内输出。

我的问题：我不太明白我的教授对文件格式的解释以及它们应该如何翻译成代码。我也不明白我应该可视化什么样的图，我是在二叉树上找到最短路径，还是在具有许多顶点和边的图（不是二叉树）上找到最短路径？（我很困惑，因为他提到了二进制堆，所以我不确定在这里可视化什么）

我不明白的文件怎么办：看看图表，我们有这样的东西：

从他的解释中，我明白n = number of vertices了m = number of edges。我不明白的是，在0我应该使用 Dijkstra 的图形中，顶点后的数字对代表什么。此外，如果您查看任一文件的末尾，您会注意到以这种格式列出的顶点数不是n ='s. 为什么是这样？

以下是基于数组的优先级队列/二叉堆的递归 heapify 函数。

谁能告诉我为什么我要进入无限递归？

好的，所以我修复了无限循环，但该函数仍然无法正确堆积。

这是新代码，