问题标签 [min-heap]

我这里有一个最小堆类，它根据权重属性存储 Link 对象。我的目标是能够直接访问和更改存储在最小堆中的对象的属性。我需要能够仅基于“loc”属性访问这些对象。
因此，例如，我可能想要访问 loc 值为 6 的 Link 对象并更改其父属性或权重属性；但是我只知道它在访问时的 loc 属性值。
我的理解是我应该使用指向这些对象的指针数组，但我不确定我将如何实现它。

谢谢！

I'm trying to implement a binary search tree in C by using minheap. I've got the basic code down but I cannot get it to work properly. My main problem, according to the build messages, seem to be that I compare pointers and integers. As this code is based off of various explanations that I found in my textbooks and online, I'm not sure how to avoid that.

Here is the complete code (final and working - see edit history for original):

Here is the output (final and working - see edit history for original):

It looks like I need to exclude the connection from "nothing" to the root of the tree still.

printTree I added for debugging purposes but there seem to be problems with it as well.

我正在尝试将值插入到最初为空的二进制堆中。

这是相关代码：

我NullPointerException从 insert 方法中获得了 for 循环内的内容。这与我处理最初的空数组的方式有关吗？

这是初始化类：

我正在学习使用堆，作为练习，我正在尝试使用我创建的堆类来编写一个程序来对单词进行排序。我已从文件中读取单词并将它们成功添加到堆中。我在弄清楚如何打印出单词的排序列表时遇到了一些麻烦。根据我对最小堆如何工作的理解，如果我从最小/根节点中删除，它们将始终按排序顺序删除。到目前为止，我已经尝试过做一个简单的 for 循环，但是只有一半的堆被删除了。

我的主要尝试

这是我的堆类中的删除函数

我需要为最小堆二叉树编写递归来检查这棵树是否是最小堆。其中一个测试用例是 NONE。

被None认为是最小堆树并返回True，或者None是False？

我问的原因是我会在某个时候到达叶子并且它们的节点是None并且如果基本情况是True那么它将返回True。

我正在阅读本文档中提到的问题 1（b 部分）：

找到二进制最小堆的最小元素需要对数时间： T / F？

应该是真的，因为当我们构造一个最大堆时，时间复杂度就是这里O(logn)提到的。

同样，如果我构造一个最小堆，它应该是O(logn). 最小堆类似于最大堆，只是在 C++ 中，默认情况下会构建最大堆，我们必须为最小堆编写自定义比较器。那么，有什么区别呢？

我刚刚学习了“算法简介”，并开始在 c# 中实现堆和堆排序算法。

实现一个从双精度数组构造最小/最大堆的函数，我注意到构造的堆具有一些有趣的属性。

构建的最小堆可以从左到右，从上到下（从根到叶，按级别）读取，并将对其进行排序。

这是 minheap 的属性，还是我无法获得此属性不适用的情况。最大堆不能以这种方式工作，至少我在这里得到了什么。

输出：

2345 7 34 6 3 5 4 5 1 2 3 2 1 3 1 3 2 1（最大堆）

1 1 1 1 2 2 2 3 3 3 3 4 5 5 6 7 34 2345（最小堆）

感谢您提前回复！

我接受了 Facebook 的采访，他们问了我这个问题。

假设您有一个具有 N 个不同值的无序数组

$输入 = [3,6,2,8,9,4,5]

实现一个查找第 K 个最大值的函数。

EG：如果 K = 0，则返回 9。如果 K = 1，则返回 8。

我做的就是这个方法。

我刚刚测试过，该方法根据问题运行良好。不过，受访者表示，in order to make your life complex! lets assume that your array contains millions of numbers then your listing becomes too slow. What you do in this case? 作为提示，他建议使用min heap. 根据我的知识，堆的每个子值不应超过根值。因此，在这种情况下，如果我们假设 3 是根，那么 6 是它的子节点，并且它的值大于根的值。我可能错了，但是您的想法是什么以及它的实现基于min heap什么？

我在堆栈溢出中搜索这个问题。但是我很难理解编码，因为有人使用了递归过程。

我知道在 Min Heap 中每个父节点都小于或等于其子节点...我也知道我们使用公式 Tree[K/2] 表示 Tree[K] 中的父节点，其左子节点是 Tree[2K]，其右子节点child 是 Tree[2K+1]，只有当我们的数组从 1 而不是 0 开始时才成立。

有三种情况可以检查我的数组是否是最小堆：
1. 内部节点有左右子节点。
2. 最后一个节点可能只有一个左孩子。
3.叶子没有孩子。

但我不明白如何在我的程序中以代码的形式做到这一点......请修改我的程序或给我提示，我该怎么做......？？？？

我想知道为什么要使用 , 创建最小priority_queue堆std::greater？

对我来说，由于最小值总是位于堆的顶部，所以使用的类应该是std::less

更新： 另一方面，由于priority_queue(max heap) 的默认行为是在顶部保存最大值，在我看来std::greater应该用于最大堆创建而不是最小堆创建