问题标签 [max-heap]

I know that the running time for BUILD-MAX-HEAP in heap sort is O(n). But, if we have an array that already sorted in a decreasing order, why do we still have O(n) for the running time of BUILD-MAX-HEAP?
Isn't it supposed to be something like O(1)? It's already sorted from the maximum value to the minimum value, so we do not need MAX-HEAPIFY.

Is my understanding correct? Could someone please explain it to me?

我应该对以下 Java 中的 MaxHeap 实现进行哪些更正？Insert 函数在调用时保持运行。Insert 和 BuildHeap 函数有什么错误？我已经编辑了 PercolateDown 函数。我认为现在应该是正确的..？

我正在尝试创建一个最大堆，逻辑很简单，如果父级小于其子级之一，则交换它们。我尝试使用

我正在使用输入

树应该看起来像

所以数组表示应该是90 36 17 25 26 7 1 2 3 19 代码的输出是

我查了一下，在许多教程中发现了许多相同的代码。为什么输出不是数组中树的表示？我误解了吗？

感谢您的解释

作为一个家庭作业问题，我必须从数组中提取最大堆。问题如下：

请画出以下数组中存储的最大堆（堆大小为6） A[] = {15,10,8,5,2,7,20,30}

所以，当我尝试这个问题时，我只是用老式的方式做，并没有考虑到 heapSize 小于数组大小。

我得到的最大堆是：{30,20,15,10,2,7,8,5}

我的问题是：这是正确的吗？另外，既然 heapSize 小于数组大小，这对产生的最大堆有什么影响？我应该只显示最大堆数组直到第 6 个元素还是应该修改我的最大堆？

谢谢！

考虑以下示例。我将随机数添加到最小堆，同时我以相同的顺序将相同的数字添加到最大堆。所以最后这两个堆将具有相同的数字，不同的是一个是最小堆，第二个是最大堆。

现在问题来了：

如果我决定从最大堆中删除最大元素，那么最大堆中的最大元素是否总是在最小堆的底部？如果不是，那么另一个问题是，如果我想从最小堆中删除该最大元素，并将他与最小堆的最后一个元素交换，删除最后一个元素，我是否需要运行必须比较该切换元素的操作带着他的孩子为了修闵堆？还是总是将其与父级进行比较以修复最小堆？

你好亲爱的电脑爱好者。我又遇到了一个问题。

我应该编写一个最大堆。heap.h和main.c是预设的，应该是正确的。

我现在将实现 5 个功能：

到目前为止，一切都很好。程序编译没有错误。然而 Valgrind 发现内存错误：

我找不到内存错误。下面是我编写的 5 个函数。我为结构道歉。

代码：

valgrind：

我正在做我的算法的中期审查，我试图用 Java 实现所有的伪代码，以便更好地理解算法。但是在堆排序部分，我的代码有问题。我的输入数组是

{10,16,4,10,14,7,9,3,2,8,1}

第一个元素只代表我想要排序的元素数量。换句话说，需要排序的元素从索引 1 开始。

我构建最大堆的输出是：16 14 10 8 7 9 3 2 4 1

我的堆排序输出是：1 3 2 4 7 8 9 10 14 16

看起来我的 build-max-heap 部分运行良好，但我也找不到堆排序部分的错误。

标题说明了一切; 在具有n 个元素的最大堆中找到第n个最大数的最有效方法是什么？ps：我正在阅读的教科书含糊地解释了一个具有时间复杂度的解决方案，即使用另一个我无法理解的堆，我们能做得更好吗？
O(lognloglogn)

我对 Max Heap Sort 的伪代码的一部分感到困惑。降到 2是什么意思？

这是我的代码。我对 c 和指针很陌生，所以可能是指针上的错误。

数组是 MaxHeap，但我不知道为什么我的代码返回 No。（printf 在这里只是为了尝试捕获错误）

谢谢