问题标签 [min-heap]

我试图使用最小堆进行堆排序，这也是一个指向数组指针的结构。现在createHeap函数或heapify函数中存在一些逻辑错误。注意：程序的其余部分不需要检查或编辑，Heapify和createHeap需要根据程序的其余部分进行修改。

问题是什么？

当我使用 STL 的优先级队列时，我想使用最小堆，所以我使用如下代码。

它适用于默认选项，但不适用于“更大的选项”。

它总是像上图一样排列。我完全不知道为什么会这样。

其实我也听说过向上再堆化和向下再堆化这两个名词。但是 max-heapify 和 min-heapify 是什么意思呢？这两个术语（最大堆和最小堆）是否与向上再堆和向下再堆有关？根据我的说法，向上再堆和向下再堆都属于最大堆和最小堆。如果我错了，请纠正我。另外请告诉我所有这四个术语的时间复杂度。

这是我的遍历方法：

这是我的输出：

它似乎工作正常，但我拥有所有这些我不应该拥有的垃圾值，我无法确定问题所在。

我怀疑控制结构有问题，我的逻辑是正确的还是应该使用 else if 语句？

这是我在 python 中实现的 MinHeap 和 MaxHeap。这使用了一个比较器来反转 MaxHeap 中的存储顺序

MinHeap 似乎工作正常，但是 MaxHeap 抛出以下错误。

我似乎不太明白我在这里做错了什么。有人可以帮我弄这个吗。

我正在尝试实现一个将列表转换为 MinHeap 的函数。我看不出哪里出错了。

示例输入：

输出（4 不正确）：

所以我被问到 K 最佳候选问题的奇怪反转。正常问题如下。

给定一个“投票”列表，这些“投票”是时间戳和候选者的元组，如下所示：

返回得票最多的前 K 个候选人。

这是一个典型的问题，解决方案是在时间戳范围内使用候选者的哈希图->投票还构建一个大小为 K 的最小堆，其中基本上堆的顶部是容易被从 K 个最佳候选者中弹出的候选者.

最后你返回堆。

但最后我被问到：给定 K 个候选者的列表，返回与这些匹配的时间戳作为 K 个最佳候选者。我不确定我是否 100% 正确地回忆了这个问题，因为它要么必须是这些 K 候选人中最好的第一次出现，要么我会得到他们的投票结果。

我真的很难过，我不知道如何处理它 - 非常感谢你的帮助：

一家公司试图构建一个 SP 树数据结构，以便每个交集包含两个键：一个排序键 skey，它赋予 SP 二叉搜索树的能力，一个 pkey 键，赋予 SP 最小堆的能力（假设所有的 pkey 键彼此不同）。

如何证明存在由 n 对键（skey，pkey）组成的奇异（单个）数据结构 SP？

我的意思是，由于 pkey（最小堆），它说堆树将被定义，以便它的每个儿子的价值都大于他们的父母。但是，由于skey（二叉树），这意味着只有在右侧才会有值大于父级的元素（左侧应该更少，但我不知道它如何与pkey要求结合- 因为它的儿子应该比父母具有更高的价值）。我真的不明白 - 应该获得的树看起来像一条向右的线吗？

我真的不明白，如果你们能帮助我，我将不胜感激。

在 C++ Sort 函数中，第三个可选参数是用于对对象进行排序的比较器。如果我们传入 less 作为比较器，我们将按递增顺序获取对象。（如果比较器被评估为真，则位置不会改变，否则元素将被交换！）我的理解是否正确？

按照同样的方式，如果我们将一个 less 比较器传递给优先级队列，我们​​应该得到一个最小堆，（如果底层数据结构选择为向量，则对象按升序排序。如果我们调用 top()，则会返回vector的第一个元素，也就是最小的数。所以，我认为是最小堆）为什么我们得到最大堆？

我必须将文件中的所有数据（整数）读取到数组中，然后迭代数组以生成最小堆并将它们添加到当前堆的最后一个元素之后。读入数组后，我必须调用SiftUp()每个元素，这意味着将 int 移动到数组中的正确位置。此外，我必须在读取整数时对其进行计数并将全局 heapSize 设置为该值。在所有输入结束时，我试图打印出最小堆数组的前五个元素。输出错误。我的代码没有做任何最小堆，这就是为什么输出是随机的。逻辑有什么问题？

输入文件有 97 个整数：

输出：

我的程序：