问题标签 [min-heap]

我正在尝试学习和实现一个最小堆来解决一个问题：循环创建双精度并将它们插入到排序数组中，在 C

基本上，我从一组双打开始，从小到大排序。然后，我生成双打（可能是随机的）并且必须将新生成的双打添加到集合中，同时保持排序。此外，每次我插入一个双精度数时，我都会从集合中删除最小的双精度数。

（编辑- 集合不必完全排序。目标是能够在每次插入双精度后查找并删除最小元素。保持集合排序是我的第一个天真的解决方案。）

听起来像是最小堆要做的事情。

试图

由于在 C 中，数组大小是预先声明的，因此我必须创建一个长度 = 最大双精度数的数组。然后，用值 max_double 填充该数组的所有条目。

使用此处描述的方法作为指南： http: //opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html，我可以创建函数来将值插入和删除到这个数组中。

插入：用数字替换数组的最后一个条目（始终是 max_double）。然后不断与父节点的值进行交换，直到父节点的值小于新增的值。

移除：将根节点替换为 max_double，然后与它的两个子节点进行比较，与最小的子节点交换，直到它的两个子节点为 max_double。

问题

我对所有这些都使用了正确的方法吗？

可能重复：
我在 Python 中使用什么来实现最大堆？

我正在尝试以某种方式实现 python 的 heapq，但用于最大堆。一个解决方案是使用 (-1) 和多个队列编号，但这对我没有帮助，因为我需要将 url 存储在堆中。所以我想要一个最大堆，我可以在其中弹出最大值。

我正在为算法和数据结构课程分配作业。我无法理解给出的说明。我会尽力解释问题。

给定的输入是一个正整数n，后跟n 个正整数，表示有序字符集中符号的频率（或权重）。第一个目标是构建一棵树，为有序字符集中的每个字符提供近似的保序霍夫曼码。我们将通过“贪婪地合并权重总和最小的两棵相邻树”来实现这一点。

在分配中，我们看到传统的霍夫曼代码树是通过首先将权重插入优先级队列来构建的。然后通过使用 delmin() 函数从优先级队列中“弹出”根，我可以获得频率最低的两个节点并将它们合并为一个节点，其左右为这两个最低频率节点，其优先级为其孩子的优先事项的总和。然后将该合并节点插入回最小堆中。重复该过程，直到所有输入节点都已合并。我已经使用大小为 2*n*-1 的数组实现了这一点，输入节点来自 0... n -1，然后来自n ...2*n*-1 是合并节点。

我不明白如何贪婪地合并权重和最小的两棵相邻树。我的输入基本上被组织成一个最小堆，从那里我必须找到两个具有最小和的相邻节点并将它们合并。通过相邻，我假设我的教授意味着他们在输入中彼此相邻。

示例输入：

然后我的最小堆看起来像这样：

那么，总和最小的两个相邻树（或节点）是出现在输入末尾附近的两个连续的 1。我可以应用什么逻辑从这些节点开始？我似乎错过了一些东西，但我无法完全掌握它。如果您需要更多信息，请告诉我。如果有不清楚的地方，我可以详细说明自己或提供整个作业页面。

我在从霍夫曼树中正确弹出时遇到问题。现在我正在创建一个基于 minheap 的 Huffman 树，我想做以下事情：

如果我们假设 A 和 B 是两个不同的子树，我会说如果 A 的频率小于 B 的频率，则 A 将首先弹出。如果它们具有相同的频率，那么我会在 A 的任何叶节点中找到 ASCII 值中的最小字符。然后我会看看 A 中最小的字符叶节点是否小于 B 的任何叶节点中的那个。如果是这样，我会在 B 之前弹出 A。如果不是，我会弹出 B。 <-这就是我遇到的麻烦。

例如：

假设我输入：

进入我的霍夫曼树。然后我的树看起来像这样：

下面是我从 Huffman minheap 中弹出的尝试。我在比较两个字母的频率是否相同时遇到了麻烦。如果有人可以提供帮助，那就太好了。谢谢！

我正在从 stl 优先级队列创建一个最小堆。这是我正在使用的课程。

} ;

我主要是这样实例化一个对象。

我收到一个xutility我无法理解的错误。

d:\microsoft visual studio 10.0\vc\include\xutility(674): 错误 C2064: 术语不计算为采用 2 个参数的函数

对其解决方案的任何帮助将不胜感激。

我正在尝试使用 STL 等在 C++ 中创建 s的最小堆¹，但我的比较器似乎没有正确比较。以下是我目前的比较器：longmake_heap

但是，当我执行std::pop_heap(humble.begin(),humble.end(),g);where gis an instance greater1and humbleis a heap who make [9,15,15,25]when sort_heapis called 时，我会15弹出一个。

我的比较器正确吗？可能出了什么问题？

编辑：
我意识到我正在运行没有比较器的 sort_heap，而当我运行这个比较器时，我[15,15,9,25]从sort_heap. 现在我在想我的比较器肯定不起作用，但不确定为什么。

¹ STL 默认创建一个最大堆，所以我需要一个比较器。

我有一个关于使用最小堆查找第 k 个最大元素的问题。算法如下：

1. 我们取前 k 个元素并构建一个 minheap

2. 令 Sk 为 S 中的最小元素。

3. 从剩余的 nk 个元素中看一个新元素。

4. 如果新元素大于 Sk，则将其替换到 S 中，并对堆进行重新排序。

5. S 然后将有一个新的最小元素。

6. 在查看了所有其他元素之后，Sk 就是答案

我不明白这个算法。例如，让数字为 1、2、3、4。我们想找到第 4 个最大的，即 4。但是当我们使用算法时，我们取前 4 个元素，构建 minheap，Sk 为 1。

我究竟做错了什么？如果有人可以提供帮助，我将不胜感激。谢谢

所以我做了一小堆二叉树。为了测试它，我创建了一堆具有 2 个不同值的节点。

说

说频率是堆主要排序的，但是如果节点频率相同，那就是按照节点数据排序。

当我制作一堆节点并加载堆并弹出并打印它们时，我得到了（大小，是树中有多少节点，min是每棵树拥有的最小数据）

如果你没有注意到，第三个条目是错误的，因此堆是错误的。

我的错误位于 minheap upheap downheap 的某个地方，删除或插入。

我已经尝试了好几天，我的大脑无法处理它，还有很多其他有趣的事情要做，比如模拟城市。（不是真的，我必须完成这个）

这是我的堆

我应该提一下，我需要创建自己的 STL 类，如果频率相同，堆也应该选择优先级，其中树中保存的最小值是相同的，所以这就是代码中的 minkey 指针。只需要弄清楚为什么它的顺序不正确。

我的程序适用于霍夫曼编码器，这里是： 我的文件

它有一个在 ubuntu 64 系统上编译的 make 文件。使用重定向输入。

上面的堆来自
echo "Sally Sold Sea Shells By The Sea Shore" > input
./huff < input

我正在尝试建立一个最小堆。我已经完成了插入、删除、交换、上堆、下堆，它工作正常。

但是，我正在尝试为 Min-Heapify 编写一个方法。

这是我的输入：{20,14,9,6,4,5,1}

我期望的输出是最小堆：{1,5,4,20,9,6,14} 但我得到的是：{14,6,9,20,4,5,1} 这是对面的。

这是我的代码：

我遵循了 MAX-Heapify 的这个伪代码

我正在尝试将 minHeap 类转换为 maxHeap 类。我得到了 minHeap 类的代码，其中一种方法是 add。它看起来像这样：

第一个节点自动设置为 null，因此添加的所有内容都放在节点 1 以后。如前所述，这段代码给出了一个 minHeap 结构。所以将其更改为 maxHeap，我只是像这样翻转比较器符号：

我输入的项目由一个整数值存储。按插入顺序，它们是：

在 minHeap 结构中，这些存储在节点中，如下所示：

在 maxHeap 结构中，更改符号会像这样存储它们：

请注意，它们的顺序不再与 minHeap 结构中的顺序相同。这很重要还是仍然是有效的 maxHeap？

为我展示树状结构的糟糕尝试道歉。