问题标签 [min-heap]

我想通过定义自定义比较函数将一组对象存储在最小堆中。我看到有一个 heapq 模块可用作 python 发行版的一部分。有没有办法在这个模块中使用自定义比较器？如果没有，其他人是否构建了自定义最小堆？

我正在尝试在 C++ 中为我创建的结构类型实现最小堆。我创建了一个该类型的向量，但是当我对其使用 make_heap 时它崩溃了，这是可以理解的，因为它不知道如何比较堆中的项目。如何为结构类型创建最小堆（即顶部元素始终是堆中最小的元素）？

结构如下：

我想使用 rank 成员比较 DOC 结构。我该怎么做？

我尝试使用带有比较器类的优先级队列，但这也崩溃了，而且当我真正需要的是堆时，使用使用堆作为其底层基础的数据结构似乎也很愚蠢。

非常感谢，bsg

我正在尝试从二进制堆中提取最小值，但它不起作用。这是我的 BubbleDown 代码：

看起来它只交换了几个数字，但不是全部，我不明白为什么。我试图以不同的方式重新编码它，而且已经很多次了......

我究竟做错了什么？

据我了解，对于用户定义的结构，这很容易。只需重载运算符 <。但是，对于 int/float 等，我真的需要为 int 重载 operator < 吗？这是我尝试过的：

结果是：

现在 pop_heap，push_heap 不会正确维护最小堆？有没有更简单的方法来实现这一点？谢谢！

编辑：对不起，我没有仔细检查手册。是的，将 comp 传递给 pop_heap 或 push_heap 应该可以解决问题。但是，您是什么意思，我不应该使用外部比较器？如果这不是正确的方法，那么实现这一目标的常用方法是什么？

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

我试图限制以下结构：

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

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

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

这是网站

在页面的一半多一点处，他开始展示用于解决这个名为 boggle 的游戏的伪代码。我对他这句话的意思感到困惑

• 检查是否currentletter是q，在这种情况下，将一个新字母插入到nextheap包含中u，以及与 相同的坐标和指针成员currentletter。

• 恢复currentletter:*的踪迹

如果有人能澄清什么q和u是什么以及该检查试图实现什么，我将不胜感激。

我有以下结构

我有这个结构的几个对象。现在，我想将这些对象插入到 STL 的优先级队列中，以便优先级队列按计数对项目进行排序。关于如何做到这一点的任何想法？最好是最小堆。我知道如何对原始数据类型执行上述操作，而不是结构

我正在尝试在 Java 中实现 Min Heap，但在插入和删除元素时遇到问题（在末尾插入，以 min 删除根）。它似乎在大多数情况下都有效（我使用一个程序来直观地显示堆，并在删除 min 时打印出新的根，诸如此类）。

我的问题是，由于某种原因，添加新项目时根不会切换到新项目，但我根本不知道为什么。此外，这似乎只是有很多重复项时的问题，堆似乎并不完全能够保持有序（父项小于子项）。在大多数情况下，它确实如此。只是偶尔不会，对我来说这似乎是随机的。

这是通过泛型完成的，并且基本上遵循大多数算法。我所知道的所有其他事实都有效，这绝对是这两种方法的问题。

任何未在方法中声明的变量都是全局的，我知道有几件事可能是多余的，比如 add 中的整个当前/最后/临时情况，所以我很抱歉。我试图让所有名称都一目了然，并解释了我在 removeMin 中所做的所有检查。任何帮助将不胜感激，我已经尽我所能查找和调试。我想我只是从根本上错过了一些东西。

我正在阅读 CLRS 并且对练习 6.5-8 有一些问题。

给出一个 O(n lg k) 时间算法将 k 个排序列表合并为一个排序列表，其中 n 是所有输入列表中元素的总数。（提示：使用 min0heap 进行 k 路合并。）

正如大家所说，解决方案是，

1) 使用 k 个列表的第一个元素构建一个 k 元素最小堆，

2) extract-min() 从堆中获取最小元素并将其附加到结果列表中，

3) 从与我们刚刚从堆中提取的元素相同的列表中选择下一个元素。将其插入堆中并转到 2)。

我可以理解时间是 O(n lg k)，但我没有得到步骤 3) 中选择的正确性。这似乎很明显，但有一些正式的证据吗？

弗雷德里克森的堆选择算法是否有任何简单的解释，可以在在线任何地方可用的最小堆中找到 O(k) 时间内排名第 k 的元素？如果没有，任何人都可以解释算法的核心吗？