问题标签 [min-heap]

本着空间复杂性的精神，我不愿意创建一个接受 k 个列表并将 List 的内容合并到另一个 List 的“合并”方法。这是可以使用“最小堆”实现的 k 路合并问题吗？任何指针都会非常有帮助。

}

我不认为这是最好的方法（使用树）。关于如何仅通过覆盖 next() hasNext() 和 remove() 来实现这一点的任何建议？

我正在尝试使用最小堆来实现 Prim 的算法。我不想随机选择源/起始节点，但想以非递减的权重顺序对边进行排序以找到根节点。我想获得有关如何去做的指导。

当使用最小/最大堆算法时，优先级可能会改变。处理此问题的一种方法是删除和插入元素以更新队列顺序。

对于使用数组实现的优先级队列，这可能是一个似乎可以避免的性能瓶颈，尤其是在优先级更改很小的情况下。

即使这不是优先级队列的标准操作，这是一个自定义实现，可以根据我的需要进行修改。

是否有众所周知的最佳实践方法来更新最小/最大堆中的元素？

背景信息：我不是二叉树专家，我继承了一些在优先级队列中重新插入元素时存在性能瓶颈的代码。我已经为重新排序新元素的最小堆创建了一个重新插入函数 - 这对（删除和插入）提供了可衡量的改进，但这似乎是其他人可能已经解决的问题更优雅方法。

如果有帮助，我可以链接到代码，但不想过多地关注实现细节——因为这个问答可能会保持一般性。

I was trying to implement MST with Priorityqueue with custom comparator, but I am facing problem in building min-heap with it in O(n) time. The problem is only one constructor of Priorityqueue allows to create PriorityQueue in O(n), but it does not take any comparator as argument. I want it to use my custom comparator. Is there workaround for this problem ? PriorityQueue.addAll() will lose the purpose of using Min-heap for MST as it is O(nlogn) method. Here is my code.

And the comparator that I want to use:-

我正在努力在 Ruby 中构建一个 minheap，并且想知道使用 push 方法与赋值运算符的含义是什么。（这只是一个更好地理解 Ruby 的理论问题！）

给定一个 k-ary 树，我想将其转换为一个最小堆，并且更改次数最少。更改被定义为重新标记节点。

我发现的一个解决方案是，我可以尝试更改节点值或不更改的 dp 解决方案。但它的时间复杂度会呈指数级增长吗？任何想法，（最好有最优性证明）。

示例：假设树是 1-3、3-2、1-4、4-5。其中 1 是根。然后我可以将节点 3 重新标记为 1 或 2，即在 1 中更改它成为一个最小堆。

我有这个作业，我必须转换以数组表示的最小堆：

并像这样在树中实现它：

提醒一下，最小堆数组的索引如下：

那么，我该怎么做呢？

我开始这样的事情：

我在正确的道路上吗？我认为这应该递归地完成，但是如何呢？

提前致谢

在锦标赛树的实现中，额外的空间被用作要比较的数据被设置在树的叶子上然后进行比较。我读到当我们必须合并 k 个排序数组时很有帮助。现在，假设我们要合并 k 个排序数组。如果不是存储实际值，而是存储索引并创建一个最小堆，然后在 min_heap 实现中使用自定义比较器函数，该函数按该索引处的值排序。这样我们就可以知道要添加到堆中的下一个元素。这不是更好的实施，因为它可以节省我们一半的空间吗？此外，时间复杂度也将相同。上面的实现不是比锦标赛树方法更好吗？
那么，在哪些情况下锦标赛树会有所帮助？

我code::blocks对它的工作原理还很陌生，但是我将它用于 uni 的分配，基本上，它使用 ADT 和邻接列表实现了 dijkstra 算法，代码有效，我得到了输出，但我得到了错误

进程返回 -1073741819 (0xC0000005)

最小堆代码：

抱歉，代码太长了我一直在试图找出问题的原因，我认为这可能与没有分配内存的指针有关，但我找不到任何这样的指针

我在网上搜索了这个在 Python 中实现 MinHeap 和 Maxheap 的方法。

现在我需要为这两个类添加一个 peek 方法。在当前的实现中，我可以弹出并推回。但我的问题是，有没有更好的方法来做到这一点。O(1) 时间内的东西。