问题标签 [min-heap]

我正在使用 min-heap 实现 heapSort，它的排序很好，低于 350 个元素。一旦数组有大约 350 个元素，它就不能正确排序。我不确定错误在哪里，但我相信它可能与extractMin(), 或与递归有关。我添加了整个minHeap课程，以确保该错误不在其他地方。

这是我的代码：

从minHeap课堂开始：

这是extractMin（仍然是minHeap课程的一部分），这可能是罪魁祸首：

heapSort函数（与类无关minHeap）：

我的主要：

我得到的输出：

假设您有一个 C++ 程序，它必须从给定的 .txt 文件中读取文本。该计划将：

• 计算文件中每个字符的出现次数，然后每个唯一字符（及其频率）将存储为新的树节点
• 然后程序构建一个包含这些节点的最小堆，然后使用这个最小堆构建 Huffman 代码树。
• 遍历（前序和有序）将被写入输出文件。树的每个内部节点都有标签 I:xxx，其中 xxx 是 int 标签，叶子有 L:xxx
• 程序最终构建了一个表，其中包含存储为字符串的每个字符的编码（基于 ASCII，不是真正的 .bin 版本）

我想我会将每个节点存储在一个霍夫曼类中，如下所示：

我不确定从哪里开始。任何帮助将非常感激！

我必须在 Python 中构建一个完整的 MIN-HEAP 实现，而不使用内置的堆函数。

所以我有父母，左孩子和右孩子的定义，考虑到从0开始的python编号列表元素：

然后我有一部分代码为我生成（伪）随机列表到列表l中：

直到此时一切正常。然后我有一个函数 bkop 用于将表l变成最小堆。

然后我想运行一个程序并查看结果：

程序崩溃，错误列表索引超出范围，指向我用######### 标记的 3 行。我大约一个月前开始写这篇文章，我很确定，那个父母、lchild 和 rchild 当时都在工作。你知道，怎么了？

EDIT1：好的，所以我已经修复了 parent/lchild/rchild 定义。我检查过，它们返回正确的值。这是代码：

生成随机列表的函数几乎完好无损。然后我有这个 bkop 函数（从l列表中生成一个最小堆）。我故意在前后使用 print 来确定它是否有效......但它没有。它两次返回相同的列表，没有编译错误或任何东西。知道如何解决吗？

EDIT2：好的，所以我已经按照您的建议修复了 bkop ：

但是当我运行它时，我首先得到一个随机生成的表（我应该这样做），而不是最小堆表，我得到None值，如下所示：

有任何想法吗？也许我应该换一种方式来做，不是将 l[i] 与父母进行比较，而是将 l[i] 与左右孩子进行比较？

嘿，我尝试在 javascript 中实现最小堆，但我对删除 min 的算法有疑问。我在内部使用一个数组来表示堆。当我向下渗透时，停止条件应该是什么？在我的代码中，我将其设置为 2 * k <= this.size，因此它可能会向下移动到最后一个元素，但感觉不“正确”，是否有更好的停止条件？提前致谢！

我试图以最小堆的形式表示一个数组。我在其中一个叶节点中遇到问题，其中父节点大于（12 大于 6）右子节点。我不明白我的编码有什么问题，请帮忙。

这是我的代码：

我得到的输出是：

功能一

功能二

问题详情

在这里，堆化的工作方式与制作 min_heap 的方式相同，但问题是，我在下面的问题中使用堆来解决它，但不幸的是，我通过观看 MIT 讲座实现的函数 2 在查看了一段时间后并没有解决这个问题我发现第一个功能可以无缝地解决这个问题。我只是困惑它们不是相同的功能吗？------

问题

是的！！问题名称反映了您的任务；只需添加一组数字。但是你可能会觉得自己居高临下，编写一个 C/C++ 程序只是为了添加一组数字。这样的问题只会质疑你的博学。所以，让我们为它添加一些独创性的味道。

加法运算现在需要成本，成本是要相加的两者的总和。所以，加 1 和 10，你需要 11 的成本。如果你想加 1、2 和 3。有几种方法——</p>

我希望您已经了解您的任务，即添加一组整数以使成本最小化。

输入

每个测试用例都以一个正数 N (2 ≤ N ≤ 5000) 开始，后跟 N 个正整数（都小于 100000）。输入由 N 的值为零的情况终止。这种情况不应该处理。

输出

对于每种情况，在一行中打印最低总成本。

样本输入

样本输出

我昨天问了一个问题，但不是很清楚，所以这是一个更具体的问题。

我将我的 minheap 表示为一个数组。我对我认为的 minheaps 有很好的理解，但我对其中的某个概念很模糊。Minheaps 总是应该有最小的节点作为根。要删除一个值，将根设置为数组表示中的最后一个元素（叶节点），并且数组的大小会递减。然后通过使用 siftDown/PercolateDown 或您想调用的任何名称正确放置根节点。这是超级有效的。例如：

这里 29 取自最后一个元素， siftDown(1) 将放置它：

1. 29 与 15 和 38 进行比较。交换 29 和 15。
2. 29 与 25 和 20 进行比较。交换 29 和 20。
3. 29 与 30 进行比较，29 < 30 因此我们完成了。

这一切都很好，但是如果在两次删除最小值之间，其他一些数据发生了变化怎么办？例如：

那么这里：

1. 29 与 15 和 38 进行比较。交换 29 和 15。
2. 29 与 30 和 32 进行比较。29 < 30 和 29 < 32 因此我们完成了。

1 是树中的最小值，但尚未设置为最小值，15 已设置。这对我来说是个大问题。我正在尝试实现 Dijkstras 算法，我也在尝试使用我自己的数据结构而不触及 Java 内置类。

因此，与我的问题更相关的示例是：

对于熟悉 Dijkstras 的人来说，99 代表一个无限远的暂定距离，其他数字代表接下来应该访问的图节点（距离最小的节点，在本例中为 3）。

一个解决方案是每次删除 min 时都重建树，但这意味着 minheap 的功能会丢失，并且任何实现都会慢下来。

抱歉，如果我没有正确理解这一点，但我已经坚持了好几天了，我真的需要一些帮助。

I would like to know how min heap is used here to solve the following problem.

What I thought to solve it is to use hashtable and save the counts of the numbers. but I don't know how to use the min heap to contiune solving the problem.

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

我正在尝试实现大小为 k 的 minHeap。

尽管最小堆的属性在创建的数组中维护，但值不正确。

示例=> k=5；输入：5,3,9,6,13,1；输出是：1 3 5 6 13 而正确的输出应该是 3,5,6,9,13

我的代码：

例如，我有一个整数的 MinHeap。我想问一下是否有办法从堆中间增加一些值，并且仍然正确保存堆排序。

谢谢