问题标签 [binary-heap]

给定一个中序遍历列表，创建二进制最小/最大堆的最佳方法是什么？

我试图限制以下结构：

1. 二进制堆中没有要使用的数组。实现是基于节点的。 BinaryNode { value, parent, l_child, r_child }

2. 让我们坚持使用 Max-Heap。

问题：我们能否比涉及 BubbleDown 的标准插入做得更好。

对于我的 C++ 数据结构类，我们正在实现一个拨号调制解调器模拟器。我们的教授给了我们一个使用 STL 优先级队列的工作源文件，但我们的工作是通过实现二进制堆来替换它。今天我去找她寻求帮助，了解二进制堆到底是什么，但她基本上告诉我和我的朋友转移到 IT :(。她周一才开始谈论它，优先级队列和二进制堆，哪个她在一个小时内冲了过去，她今天开始谈论一个新主题，因为她的幻灯片还没有完成，所以她将在周五恢复二进制堆，这是程序到期的时候。

我明白这一点，二进制堆是优先级队列的后端。但是当元素被插入或弹出时我是否排序？她提到使用向量或列表，当你只是建造一棵树时，它在哪里发挥作用？我也不明白为什么这段代码适用于她：

这就是您声明 STL 优先级队列的方式吗？该程序很难描述，因此我将其粘贴在底部。它只是一个源文件。

注意：Random.h 仅具有根据某些统计分布返回随机数的函数。

调制解调器Simu.cpp：

我正在尝试将优先级队列实现为支持最小二进制堆的排序数组。我试图让 update_key 函数以对数时间运行，但要做到这一点，我必须知道该项目在数组中的位置。有没有办法在不使用地图的情况下做到这一点？如果是这样，怎么做？谢谢

自下而上的堆构造不完全取决于 (n+1) 是 2 的幂这一事实吗？（其中 n 是节点数）。

例如，考虑 n = 21 的情况。 (n +1) 不是 2 的幂 - 这将如何工作？

您将创建第一个插入 (n+1)/2 个节点，即 11 个节点。然后，您将插入 (n+1)/4 个节点作为先前插入的节点的父节点，即 5.5 个节点。但是“半个节点”怎么插入呢？每当 n 不是 2 的幂时，您总是会在某个级别上获得十进制的节点插入量 - 您如何处理这个问题？

我考虑删除一定数量的节点，以便剩余节点是 2 的幂，从剩余节点中构建一棵树，然后在完成后将删除的节点冒泡到树中。但是对于大量节点，这变得不可行：即节点数 = 1600。最接近 2 的幂是 1024，这意味着您必须冒泡 576 个节点，这相对耗时。

我试图了解 Python 的一些内置堆功能。当我传入元组列表时，它似乎不喜欢事情（或者更有可能，我没有正确传递列表）。这是我所拥有的：

我得到的错误是

TypeError：堆参数必须是一个列表

难道我做错了什么？还有另一种方法可以传入元组列表吗？

谢谢！

can anyone help me with this please. I am trying to build a priority queue but keep getting a unresolved external symbol error. Any help would be well appreciated.

Error 2 error LNK2019: unresolved external symbol "public: __thiscall Node::Node(void)" (??0Node@@QAE@XZ) referenced in function "public: __thiscall PriorityQueue::PriorityQueue(void)" (??0PriorityQueue@@QAE@XZ)

因此，我正在开发一个程序，该程序应该“堆积”用户添加到集合中的整数等。但是，当我尝试访问作为参数传递给函数的 Node 的左子节点时，我现在遇到了问题。Visual Works 内存不足...

奇怪的是，在调试器中，我可以看到传递节点的左子节点已创建并正确分配给传递节点。但是当我尝试通过源代码访问它时，我得到了一个疯狂的内存错误。

这是相应的代码。希望它是可读的

发生错误的函数，一旦被调用：

下面是 BinaryHeapNode 类的 'left' 的访问器方法

如果查看最初调用 addLeftChildTo: 方法的代码会有所帮助...

我不明白我做错了什么，我已经被这个问题困住了几个小时。有任何想法吗？

我发布了相当混乱的问题，所以我从头开始重写......

这实际上是纯粹的理论问题。

说，我们有二进制堆。让堆为 MaxHeap，因此根节点的值最大，每个节点的值都大于其子节点。我们可以在这个堆上做一些常见的低级操作：“交换两个节点”、“比较两个节点”。

使用这些低级操作，我们可以实现通常的高级递归操作：“sift-up”、“sift-down”。

使用这些 sift-up 和 sift-downs，我们可以实现“插入”、“修复”和“更新”。我对“更新”功能感兴趣。假设我已经有了要更改的节点位置。因此，更新函数非常简单：

我的问题是：（数学上）是否有可能制作更高级的“更新”功能，可以一次更新更多节点，在某种程度上，所有节点都将它们的值更改为 new_values，然后，它们的位置被纠正？像这样的东西：

我用这个“double_update”做了一些测试，它工作了，虽然它没有证明什么。

“三重更新”呢，等等……

我用“多重更新”做了一些其他测试，我改变了所有节点的值，然后调用 { sift-up(); 筛选（）；} 以随机顺序对它们中的每一个执行一次。这不起作用，但结果离正确不远。

我知道这听起来没什么用，但我对它背后的理论很感兴趣。如果我让它发挥作用，我实际上确实有一个用途。

我认为我知道答案并且最小复杂度是O(nlogn)。

但是有什么方法可以从O(n)复杂度的堆中创建二叉搜索树？

给定的原始问题是包含 5GB URL 的文件，该文件包含最后一天访问的 URL，找到前 k 个频繁访问的 URL。该问题可以通过使用哈希映射来计算不同 URL 的出现次数并在最小堆的帮助下找到前 k 个来解决，花费 O(n log k) 时间。

现在我在想，如果输入的是无限的在线数据流（而不是静态文件），那我怎么知道最后一天的前k个URL呢？

或者我可以对系统进行任何改进，使我能够动态获取最后一分钟、最后一天和最后几个小时的前 k 个 URL？

任何提示将不胜感激！