问题标签 [min-heap]

我正在为软件开发人员面试做准备，并且一直在研究算法问题。我的书展示了一种 Heapsort 算法，它可以按升序对无序数组进行排序。我正在尝试修改它，以便它可以使用最小堆进行排序。但是当我按照代码中的逻辑进行操作时，我的数组并没有正确排序。我的代码（伪代码）有什么问题？

本书使用max-heapify的Heapsort算法：

我使用 min-heapify 修改的代码：

看最后一行。这是priority_queue max_heap 的初始化。为什么它忽略 c++ const Compare&。我以为会

它看起来与下面的不同，我理解。

我读了这个页面： http ://www.cplusplus.com/reference/queue/priority_queue/priority_queue/

无法获得priority_queue 构造函数范式的明确定义。

另外，为什么有时它会重载“<”作为比较器。有时重载“（）”作为比较器？ 谢谢

一旦调用了 remove min 函数，我将如何在 java 中“堆化”基于数组的最小堆（这只是获取索引 1 处的元素并将其删除，然后将其替换为数组中的最后一项）。在 remove min 发生后，我对如何将数组再次放入最小堆感到困惑。

索引 0 在堆最小数组中始终保持为空。父索引为 i/2，右孩子为 2i + 1，左孩子为 2i。

任何帮助将不胜感激，谢谢大家！

我正在尝试使用 minheap 实现优先级队列，但是我的对象以错误的顺序从队列中出来。我的直觉告诉我问题在于我在队列中向上或向下筛选的方法，但我看不出问题出在哪里。有人可以看看我的算法，看看是否有任何立即显而易见的错误？先感谢您。

下面是筛选的方法：

以及筛选方法：

编辑：

比较方法定义如下：

作为免责声明，我是该网站的新手，因此不太了解如何提问。请不要太苛刻，因为我真的只是想了解其中一些概念是如何工作的。如果我在开始时缺少理解，请告诉我，这样我就可以从那里开始，而不会浪费你的时间。这里什么都没有。因为我认为我的理解可能存在缺陷，所以我提出了一些关于堆如何在不同领域发挥作用的问题，然后尝试回答这些问题。

首先，我想帮助了解添加到空堆中的一组随机数字的外观。例如，我有 9、4、5、3、2、7、8、7。将其添加到堆后，堆会是什么样子？我可以直观地理解这一点（我认为）9 是根，4 是第一个左孩子等等，但由于这不是专门的树，而是一个堆，它会通过切换对数字进行排序吗它们（见“如果我的理解是正确的”段落），以便它们按最小或最大顺序排序？

现在假设我们从堆中删除了 9（我相信 9 将是根），我们将如何应对这种变化，然后将什么放入根中？我认为如果 9 是根节点，我们将取下一个最大的数字并将其复制到 9 的插槽中，而如果这是一个最小堆并且我们只是在底部删除一个节点，它只会被删除 no问题。

沿着类似的思路，获取数组中堆项的父项的公式是什么？--我想我明白这一点，如果父母在i，左孩子将在i * 2，右孩子将在i * 2 + 1。因此要找到父代，我们必须除以 i/2 才能找到父代。例如，如果我们在 i=7 处，父级将是 i=3，因为 3.5 将被截断，如果我们在 i=6 处，父级也将是 i=3。在这个例子中，i = 7 处的孩子将是 i = 3 的右孩子，而 i=6 将是 i = 3 的左孩子。

如果我对此的理解是正确的，那么在将新术语添加到根后进行重新整理，我会将孩子与父母进行比较，如果孩子更大，请切换术语。但是我需要比较两个孩子（如果有两个），看看哪个更大，然后决定哪个孩子需要交换。这将是一个最大堆，而另一个方向是最小堆。

最后，如果我在哪里添加根元素，它将如何重新堆积？

使用 Ordering 将 PriorityQueue 变成 minHeap 最简洁有效的方法是什么？

当试图解决这个问题时https://www.hackerrank.com/challenges/cut-the-tree 我试图总是挑选和切割一片叶子，然后将它的重量结合到它连接的节点上。我使用 PriorityQueue 来存储所有节点，并使用它们相邻节点的大小作为优先级。但是当我尝试一些测试用例时，似乎违反了优先队列属性，这意味着非叶子节点可能出现在叶子节点之前。PriorityQueue 会自动更新还是我应该调用一些函数来更新它。我的临时解决方案是使用列表来存储所有叶子。

以下是我的代码：

谢谢。

我正在尝试构建一个最小堆，但我没有得到正确的结果。我不确定可能出了什么问题。

input = 209 97 298 54 110 27 250 455 139 181 446 206 478 90 88

output = 27 54 97 88 110 206 90 209 139 181 446 298 478 250 455

如您所见，90不应该是97...的右孩子

这是我的代码：

这就是我构建的方式min-heap：

谢谢

我遇到的问题是 buildHeap 和 buildMinHeap 中的那个。以前，那些根本没有触发，这就是为什么我知道打印部分应该或多或少地工作，因为它正确打印了节点，如果使用未排序的数组。

目前我假设我在那里有一个无限循环，因为程序在显示我输入的一些调试消息后崩溃。我对可能出现的问题没有任何想法。有任何想法吗？

编辑：哦，还有，我还是个学生，所以还不太精通C。只是为了提供一些背景。

My heap is suppposed to print out in breadth order and sort the sheep from lightest to heaviest (min-heap). My test file should add 15 sheep and remove at least 5. I havent attempted the remove part yet because i'm getting an array index out of bounds error. Any help is appreciated.

Here are my classes: