问题标签 [binary-heap]

我愿意使用数据结构作为常量空间的溢出缓冲区。我想要有效地插入，但最重要的是有效地删除 min 元素。我正在考虑使用堆，因为我有 O(log(n)) find_min() 和 log(n) 插入和删除。另一方面，我不明白与红黑树相比的优势，因为它也有 O(log(n)) 插入和删除，但 O(1) 找到最小值/最大值。以及排序输出的优势（我不在乎）。

问题涉及：红黑树是我理想的数据结构吗？

既然我可以从 std::map 和 boost::heap 获得两种结构，为什么我应该更喜欢使用堆而不是红黑树？最后，使用红黑树，我还有 O(log(n)) 搜索条目的时间，而对于堆，时间是 O(n)，这很重要，因为存在重复项。

我正在学习堆，我发现了两种从给定数组构建它们的方法：我正在尝试构建一个 MAX 堆。

1.自上而下的方法

在这里，我只是检查每个元素是否在正确的位置。通过使用一种称为 restoreUp 的方法，其中每个键都与其父键进行比较，如果父键小于父键，则向下移动。此过程继续进行，直到父键更大。我检查每个键开始在索引位置 2。

我的代码是：

1. 自下而上的方法

在这里，我从索引层（大小/2）处存在的第一个非叶节点开始，并调用方法 restoreDown 直到节点号 1。我将一个键与其左右子节点进行比较，然后将较大的子节点向上移动。如果两个孩子都大于钥匙，然后将两个孩子中较大的一个向上移动。当两个孩子都小于钥匙时，此过程停止。

我的代码是：

这两种方法都对我有用。我只是想知道哪种方法更有效，为什么？

使用二叉堆实现优先级队列时，说明插入操作最多需要 1+lg N 次比较。（lg N = log of N，以 2 为底）。

考虑下图，

这里树的最大高度为3。即使将节点T添加到最底层，当T向上游时，它也只会遇到包括根在内的最多3个节点。也就是说，只会有3次比较最多。

但该声明表明最多会有 1+lg 11 = 1+3 = 4 compares 。

这怎么可能？有人可以解释一下吗？

来自以下问题的后续问题：https ://codereview.stackexchange.com/questions/30243/how-can-i-improve-upon-my-a-pathfinding-code/

摘要： 我请求帮助改进我的寻路代码 (A*)。一位用户很快发现我正在对特定的节点列表进行很多排序，并且使用 IComparible 来这样做 - 显然效率很低。他建议使用 OrderedBag，但是，我必须自己编写所有代码，并且不能使用来自互联网的代码。

问题：那么，使二进制堆成为维护有序数据的最有效方式，同时仍然能够快速添加和删除数据。如果是这样，是否有人有任何链接指向我创建一个的正确方向，以及创建哪个？

我听说过 LinkedList - 好主意吗？

我正在尝试创建一个使用二进制堆实现 PriorityQueue 接口的 HeapPriorityQueue 类。不使用 Java 集合的 PriorityQueue。

HeapPriorityQueue 类将由该驱动程序类运行：

程序的输出应该是。

(1,一) (3,三) (5,五) (7,七) (9,九) (10,十)

这是我尝试制作的课程：

HeapPriorityQueue（参考）

控制台中的错误行：“线程“main”中的异常 java.lang.Error：未解决的编译问题：类型不匹配：无法从 HeapPriorityQueue 转换为 PriorityQueue

有人可以帮我解决这个问题吗？

我有一个家庭作业问题如下：

创建了将实现优先级队列的 HeapPriorityQueue

这应该实现这个 PriorityQueue

而Driver类是这个

我遇到的问题是

如何将两个堆数组合并为一个平衡堆数组并仍然保持线性复杂度？我读到的关于合并堆的大部分材料都需要 O(nlogn)。

我不想通过给定的数组创建二进制最大堆。我可以通过两种方式实现它：
1.制作整个数组的堆，然后通过叶子节点开始堆到顶部。
2.将一个元素从数组中一个一个地插入到堆中，同时堆化。

这两种方法都给了我一个最大堆，但彼此不同。那么哪种方法是正确的呢？

在我的程序中，我需要从不在顶部的优先级队列中删除一个元素。可以这样做吗？如果没有，请提出一种方法，除了创建自己的堆。

从堆中删除叶节点的时间复杂度是多少？

我想如果你不知道节点在哪里，它会是 log n 因为你必须找到它。

但是，如果您已经知道节点在哪里，它应该是 O(1) 对吗？既然您可以删除它而不必重新堆放所有东西？