问题标签 [binary-heap]

尽管我拥有计算机科学学士学位（这在大学里有介绍），但我一直无法理解二进制堆和优先级队列之间的关系。它只是......没有点击。我完全理解二进制堆是什么，并且我知道如何在数组中实现一个。我也知道什么是优先队列。但是他们两个是如何结合在一起的呢？

一个快速的谷歌查询显示了很多这样的文章。哪种解释它，但我还有更多问题：

1. 优先级队列需要确保如果添加了两个具有相同优先级的项目，那么它们将按照它们被添加的顺序被删除。二叉堆如何确保这一点？（事实上​​，如果我没记错的话，那么所有项目都具有相同优先级的边界情况会产生一个违反此规则的堆）。
2. 当您从堆中删除根，然后放入最后一个元素代替根，然后需要与其中一个子交换它时会发生什么 - 但两个子元素具有相同的值。你如何选择与哪一个交换？（牢记同优先级项目的先进先出规则）

我在这里想念什么？

我必须在二进制堆优先级队列 ADT 中实现 increaseKey() 方法，但我就是不知道该怎么做。BinaryHeap 只接受扩展 Comparable 的对象，这允许我使用 a.compareTo(b)，但没有明显的方法来增加对象的键。

那么，关于如何做到这一点的任何想法？我在 google 和 here 上进行了搜索，但是在我目前看到的 binaryheap 实现中，它们不包含这些方法，或者它们返回错误。

我对如何正确使用Binary Heap. std.container更具体地说，我想创建一个最大的整数堆，所以我试着写

auto maxHeap = BinaryHeap!int();

并收到编译器抱怨int不能用 [] 切片。我试图在 Phobos 上阅读它的文档，但我不明白如何创建一个新的、空的二进制堆，用于存储整数。

有人可以帮帮我吗？

我试图通过传递一个整数数组来构建一个二进制堆。我想知道是否应该先构建一个 BinaryTree 类，然后再构建一个 Heap 类以实现二进制堆，还是应该构建一个二进制堆类？我很困惑..谢谢！

Java：我已经实现了我自己版本的Binary Heap. 它应该能够存储任何类型的 Comparable 对象。插入到堆中的对象来自输入数据，并且所有输入数据将属于同一类型。有没有办法告诉给定输入是什么对象类型？我在用着

读取输入，并in.readLine()始终返回一个字符串。现在，我正在明确测试用户是否输入了整数，否则该对象始终存储为字符串。

读取输入的最佳方法是什么，查看它是什么类型，然后创建BinaryHeap<T>该类型，然后正确插入？

问题在于selection algorithm选择总和至少为某个值 N 的最少项目数的变化。例如，您可能想要一个总和为 5,000 或更多的项目列表，但您不想要更多的项目您必须从输入列表中获取。因此，如果一个数字是 5,001，那么您的输出列表将包含一个数字。

另一个例子：Input list {3,4,5,1,2} target = {8}. output list will be : {5,3}。

这个问题已经binaryHeap在这个优秀的系列文章中被证明可以解决；但是当我实现时Java，我没有得到想要的输出。我得到了整个input list. 我无法找出问题的确切原因。这是我的代码；

我正在尝试使用 Boost d_ary_heap，但我无法弄清楚如何获取推送元素的句柄。就我而言，我需要在以后的迭代中更新值，所以我需要那个句柄。我可以用斐波那契堆来做到这一点，但在这种情况下，它看起来要复杂得多。

这是我到目前为止所拥有的：

push 函数是我在斐波那契堆中使用它的方式，它返回一个句柄类型。但在这种情况下，我无法理解它应该返回什么（http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/d_ary_heap.html#idp52218904-bb）

欢迎在推动时如何获得把手的任何帮助！谢谢。

我有一个大小超过 500 万的向量，每次我想从向量中取出一个键最小的元素，并对这个元素做一些处理。然而，随着这个特定元素的处理，向量中的所有剩余元素也将受到影响，以便它们的键更新。所以下次如果我想从向量中取出键最小的元素，我必须再次对向量进行排序。问题是从向量中拾取最小元素的次数会高达50万，所以程序运行的很慢。为了您更清楚地理解，我可以编写以下代码来说明：

有没有办法让代码尽可能高效地运行？欢迎任何想法，而不是算法的有限改进，例如并行或其他任何东西。太感谢了！

我已经为此苦苦挣扎了几个小时，我似乎也无法在这里找到答案。（有很多关于二进制堆的帖子，但我没有这个特殊问题）。

问题是：

对于具有 1492 个节点的二叉堆，高度为 2 的节点数为 _ 187 _。

我知道对于 1492 个节点，二进制堆的深度 log(1492)/log(2) = 10 高度两个应该有 2^(10-2) 个节点，应该是 256

为什么答案是 187？

谢谢

我现在这是一个被问过很多次的问题。但是，我找不到针对我的具体问题的解决方案。

我已经在 C++11 和两个不同的变体中实现了快速行进方法（非常类似于 Dijkstra）：斐波那契堆和二进制堆。为此，我使用了 Boost 1.55 堆实现（Fibonacci 和 D_ary，D=2）。

预计二进制堆在小型网格中更快，而斐波那契在大型网格中更快。但是，二叉堆总是更快（并且存在“巨大”差异）。例如：

我-Ofast -fno-finite-math-only在 G++ 4.8 中使用标志。

要点是我可以保证几周前完全相同的实现返回了预期的结果。

有人可以给我一些启示吗？

谢谢！