问题标签 [max-heap]

给定一个中序遍历列表，创建二进制最小/最大堆的最佳方法是什么？

我试图限制以下结构：

1. 二进制堆中没有要使用的数组。实现是基于节点的。 BinaryNode { value, parent, l_child, r_child }

2. 让我们坚持使用 Max-Heap。

问题：我们能否比涉及 BubbleDown 的标准插入做得更好。

我正在阅读有关堆数据结构的信息，但我不知道何时使用 max heapify 函数以及为什么。

我写了一个插入函数，它将始终保持堆为最大堆，我看不到何时会使用最大堆。

你能解释一下吗？谢谢

这是我的代码：

所以我已经阅读了堆，我理解了基本概念，

但不是如何实际实施它。

基本上，我的问题是

1. 你怎么知道在哪里放置一个新节点？

2. 删除时如何知道用哪个节点替换根？

此代码在“算法简介”一书中给出。为此，我使用了 1 个索引数组

对于这个输入

在 ideone.com 上写着“超出时间限制”。我在 Visual Studio 中尝试过调试器，结果如下

怎么了？

我有一个作业问题说：

问题 1：给定数组 [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] 为数组构建一个最大堆。显示所有步骤而不跳过任何细节。

这是我在互联网上研究对最大堆的理解：

最大堆是一个数组，可以更容易地用二叉树表示，其中父节点总是大于它的子节点，并且“每次添加子节点时，都会将其添加到左侧，以便每次树增加它的高度是一棵完整的树”

无论如何，这就是我构建的

我认为这是正确的答案，直到我读到作业的问题 2 说：

问题 2：使用与问题 1 相同的数组，使用 Heapsort 对数组进行排序。显示所有步骤而不跳过任何细节。

现在我很困惑。也许我回答了问题 2...

传统Heapsort算法在每个 之后将堆的最后一个元素与当前堆的根交换heapification，然后再次继续该过程。但是，我注意到这是不必要的。

在heapification子数组的 a 之后，虽然节点包含最高值（如果它是 a max-heap），但数组中接下来的 2 个元素必须跟随排序数组中的根，或者按照与现在相同的顺序，或者交换它们如果它们是反向排序的。因此，与其仅将根与最后一个元素交换，不如将前 3 个元素（包括节点以及在必要时交换第 2 和第 3 个元素之后）与最后 3 个元素交换，这样 2随后heapifications的（对于第 2 和第 3 个元素）被省去了？

这种方法有什么缺点吗（除了如果需要交换第二个和第三个元素，这应该是微不足道的）？如果不是，如果它确实更好，它会带来多少性能提升？这是伪代码：

假设数组是[4,1,3,2,16,9,10,14,8,7]。运行一个之后heapify，就会变成[16,14,10,8,7,9,3,2,4]。现在 的heapsort第一次迭代将交换 16 和 4，导致[4,14,10,8,7,9,3,2,16]. 由于这现在已经将新堆的根渲染[4,14,10,8,7,9,3,2]为，嗯，未堆，（14 和 10 都大于 4），运行另一个heapify来生成[14,8,10,4,7,9,3,2]. 现在 14 是根，将其与 2 交换为 yield [2,8,10,4,7,9,3,14]，从而使数组 current [2,8,10,4,7,9,3,14,16]。我们再次发现 2 未堆，因此再次执行 aheapify使堆为[10,8,9,4,7,2,3]。然后将 10 与 3 交换，使数组为[3,8,9,4,7,2,3,10,14,16]. 我的观点是heapification，我们可以从第一个开始，而不是在 16 之前存储 10 和 14，而不是执行 2nd 和 3rd sheapification因为 10 和 14 在 16 之后，所以它们是第二和第三大元素（反之亦然）。因此，在它们之间进行比较之后（如果它们已经排序，则 14 在 10 之前），我将那里的所有内容(16,14,10)与 交换(3,2,4)，使数组[3,2,4,8,7,9,16,14,10]. 这将我们减少到与另外两个heapifications 之后的情况类似的情况——[3,8,9,4,7,2,3,10,14,16]最初，与[3,2,4,8,7,9,16,14,10]现在相比。两者现在都需要进一步heapification，但第二种方法让我们直接通过两个元素（14 和 10）之间的比较来到达这个关口。

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

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

这是到目前为止的堆排序程序。

在 maxheapify 函数中，要确定是向下堆到左子还是右子，它会进行两次比较。对于最坏的情况，这意味着它将进行两次比较，乘以树的高度（ lg(n) ）。这意味着 maxheapify 的成本为 2*lg(n)。如何更改 maxheapify 使其只需要大约 1*lg(n)？

我得到一个提示说我可以递归地使用二进制搜索，但我一点也不知道如何这样做。

我感谢任何帮助/见解！

我有一个使用数组存储元素的 MaxPQ 堆。我可以使用什么算法在堆中查找给定元素？我当前使用的算法从索引 1 开始遍历数组，直到添加到堆中的元素数。该算法的复杂度为 O(N)，是否有复杂度为 O(logN) 的算法？

我有一个大小为 10 的整数数组。我需要绘制完整的二叉树。现在我需要使用 siftup 过程插入其他三个元素。显示每次插入后的最大堆。

我不确定每次插入后显示的最大堆是什么。这是否意味着每次插入一个元素时我都需要显示最大堆的大小？

定义（最大堆） HEAP(X) 令 X 是一个完全有序的集合。X 上的堆要么是空的，∅，要么是一棵完全二叉树，t，包含 nt ≥ 1 个节点，每个节点都分配有 X 的值，这样：节点 i 的值 ≤ 节点 i 的父节点的值, 我 = 2,3,...,nt。堆的大小是树中节点的数量。当且仅当它的大小为 0 时，堆是空的。

最大堆的定义是这样的，但对我来说似乎有点模棱两可。