我的家庭作业有些麻烦。我被要求使用 C++ 中的堆来实现优先级队列。

在搜索创建堆的代码示例时，我在这个定义中遇到了很多次：

表示堆的数组A是具有两个属性的数组：

– length，数组中的元素个数

– heap-size，存储在数组中的堆元素的数量

所以我的问题是：什么是A？我是否需要自己实现它（假设创建一个包含 3 个字段的类堆 - 元素数组、长度和堆大小）？

我只是不知道如何开始。

的背景

根据维基百科和我发现的其他来源，通过从一个空的二进制堆开始并将n 个元素插入其中来构建一个包含n 个元素的二进制堆是 O( n log n )，因为二进制堆插入是 O(log n )你做了n次。我们称之为插入算法。

它还提供了一种替代方法，您可以在其中下沉/涓涓细流/向下渗透/向下层叠/向下堆积/向下冒泡元素的前半部分/上半部分，从中间元素开始，到第一个元素结束，这是O( n )，一个更好的复杂度。这种复杂性的证明取决于每个元素的接收器复杂性取决于它在二进制堆中的高度：如果它靠近底部，它会很小，可能为零；如果它靠近顶部，它可能很大，可能是 log n。关键是这个过程中下沉的每个元素的复杂度不是log n，所以整体复杂度远小于O( n log n )，实际上是O( n）。我们称其为接收器算法。

问题

为什么插入算法的复杂度与接收器算法的复杂度不同，原因相同？

考虑为插入算法中的前几个元素所做的实际工作。第一次插入的成本不是 log n，它是零，因为二进制堆是空的！第二次插入的成本最坏是一次交换，第四次插入的成本最坏是两次交换，依此类推。插入元素的实际复杂度取决于二叉堆的当前深度，因此大多数插入的复杂度小于 O(log n )。插入成本在技术上甚至不会达到 O(log n ) ，直到插入所有n 个元素 [最后一个元素的 O(log ( n - 1))]！

这些节省听起来就像接收器算法获得的节省，那么为什么两种算法的计算不一样呢？

在实现为二叉树的二叉最大堆中（每个节点存储指向其父、左子和右子的指针），如果您有指向堆根的指针，您将如何实现插入操作？应该发生的是节点首先作为最后一行中的最后一个元素插入。对于基于数组，您可以追加到数组，但对于基于树的实现，您将如何找到正确的位置？

我正在尝试使用数组和链表比较实现二进制堆。我认为数组在各方面都更好，因为所有操作都可以比使用链表的操作更快或相等。它还需要更少的内存。

但是，为什么使用链表比二进制堆中的数组更好，有什么理由吗？

你们可以看看我的函数 somethingWrong() 和我的重载运算符。有时当我运行函数 somethingwrong() 时，我会得到“True”，有时会得到“False”。我没有改变任何东西，为什么会这样？

这是我正在使用的 Dijkstra 算法图。

谢谢你

主.cpp：

图.h

// 最小堆数据结构

在（最大）堆中，很容易及时找到最大的项目O(1)，但要真正删除它，您需要O(log(n)).

因此，如果从堆中插入和删除都是O(log(n))，那么在表示优先级队列方面，堆相对于二叉树的优势是什么？

现在我正在尝试用 Java 编写一个通过二叉树结构实现的二叉堆，虽然我对如何在添加元素后“堆化”树有很好的了解，但找到第一个未占用叶子的逻辑在堆的底部躲避我。

我知道找到第一个未占用的叶子应该是广度优先遍历，但我仍然无法弄清楚广度优先遍历算法究竟是如何工作的。

我正在尝试编写一个在二叉树上实现的二叉堆，但我无法找到一种将新节点添加到堆“底部”的方法，即树上的第一个空空间宽度-第一次遍历。我已经有了一个可用的 heapify 函数，但我不知道如何在 heapifying 之前添加一个新节点。

我似乎想不出一个一致的算法可以找到我可以添加节点的空空间，每次我想我想出什么东西时，它都行不通。我该怎么办？

我知道堆总是完整的二叉树。但我想知道什么时候堆是完整的二叉树？例如，堆必须处于什么条件才能始终是完整的二叉树？

为了下周的考试，我将学习如何构建 BinaryTree、BinarySearchTree 和 BinaryHeap。唯一的问题是，网络上的大多数示例都不够简单易懂。它们只是一堆没有文档的代码。我正在寻找一个简单的示例来构建三个数据结构。考虑一个带有一些函数文档的示例。一切如何运作。有人知道这三种数据结构的一些很好的教程，或者有一个很好的例子吗？