问题标签 [binary-heap]

1. 与使用 k-ary heap 实现的 (Max-heapify) 相关的运行时是多少。
2. 渐近地说，k-ary heap 比二叉堆更有效吗？
3. 在实践中，k-ary heap 是否比二叉堆更有效？
4. 可以将搜索树实现为 k 数组吗？

有必要保留一个城市中排名前 10 位的列表，在任何给定的时刻，我们的食品服务需求都是从那里产生的。这座城市可能有数以万计的地方。如果必须在内存中创建一个近乎实时（延迟不超过 5 分钟）的数据存储，它将 - 按地区（地理哈希）计算传入的需求 - 每分钟读取数百个我们的供应商（ajax 刷新是每分钟)

我在想一个多线程同步的最大堆。这将是一个复杂的解决方案，因为树锁定本身就是一个复杂的实现。

对于可以在多线程环境中读取和更新的最佳内存（可复制主从）数据结构有什么建议吗？

我们预计每秒有 10K QPS 和 100K 更新。当我们扩展到其他城市和地区时，我们将需要每个城市实施前 10 名。

有现成的解决方案吗？

持久性不是必需的，因此没有基于 mySQL 的解决方案。如果您推荐 redis 或 mongo DB 解决方案，请注意查询不是按键指向的查询，而是 top-N 查询。

提前致谢。

我在使用我的优先队列类中使用的定制堆类函数时遇到了真正的麻烦。我的堆类中的哪些函数用于我的 PriorityQueue 的“入队”、“出队”、“前”和“大小”函数时遇到问题。我知道对于“入队”，我需要使用我的插入功能，但我不知道该怎么做，因为我有优先权。有人可以帮我解决我需要做什么才能让我的 PriorityQueue 类使用我的 Heap 类中的函数以便正常工作吗？我已经坚持了一段时间，我一直在寻找答案，包括使用内置的 python 函数，如 queue 和 heapq。

类堆（对象）：

所以这是可行的，但是就像我之前所说的那样，我在如何为此设置优先级队列时遇到了麻烦？我知道要求代码是错误的，但是我很绝望，有人可以在这里帮助我吗？我对我希望我的优先代码执行的操作有基本的了解..

这是我到目前为止得到的，但我不知道它是否完全正确。谁能帮帮我？

我将代码编辑为最​​新版本。

我正在尝试实现一个具有最小堆和最大堆功能的二进制堆（优先级队列）。它需要有一个insert(value), extractMin(), 和一个extractMax()方法。extract 方法从堆中删除值并返回值。

我最初使用两个数组，称为minHeapand maxHeap，一个将数据存储在最小堆结构中，另一个将相同的数据存储在最大堆结构中。因此，当我调用时extractMin()，它会从 中删除并返回值minHeap。然后我也必须从中删除该值maxHeap（如果我调用 ，反之亦然extractMax()），以保持两个堆中的数据集相同。而且由于堆顺序属性，可以保证我会在另一个堆的叶子中找到该值。在另一个堆中搜索该值会导致时间复杂度为 O(n) 或更准确地说是 O(n/2)，因为我只会搜索叶子。更不用说，percolatingDown()和percolatingUp()删除值后恢复堆的方法已经是 O(log n)；所以总的来说，提取方法将是 O(n)。问题是，我需要提取方法为 O(log n)。

有没有更好的方法来解决这个问题？

我也想过这个想法，但想知道大家首先是怎么想的。

我刚刚完成了一个“中值堆”的编码，将较小的一半数据放在最大堆中，将较大的一半放在最小堆中。使用该结构，我可以轻松检索给定值集的中值。我正在考虑使用类似的结构，将较小的一半数据放在最小堆中，将较大的一半放在最大堆中，并使用所有值的平均值（而不是中位数）作为决定是否调用时将值放在最大或最小堆中insert(value)。我认为这可能会起作用，因为提取方法将保持 O(log n)。

我正在尝试使用堆（根小于子级）实现患者队列，但是当我打印队列时，患者队列看起来没有优先级。

插入方法工作正常，但它enqueue不优先项目？

以下是我所做的，但它不处理插入的最大要求。

如何给类一个最大值并在插入中检查它，然后删除最不重要的元素。然后找出实现中最不重要的元素是什么。

有一些问题试图解决这个问题。

嘿伙计们，我正在为我的编程课做一个实验室作业，我们必须创建一个堆，用户将整数输入到数组中然后显示它，然后我们假设使用这些相同的值并在第一部分很好地使用 HeapSort相当容易，我每次尝试调用 HeapSort 方法以对数组进行排序时遇到问题我想出了这个错误

HeapApp.heapSort(HeapApp.java:11)
处 HeapApp.main( HeapApp.java:88) 处的线程“main”java.lang.NullPointerException中的异常

错误特别指出

和

请帮忙！这是我这门课的最后一项作业！

堆类

Java 的 PriorityQueue 构造函数的复杂度是Collection多少？我使用了构造函数：

复杂度是 O(n) 还是 O(n*log(n))？

在具有N节点且高度为的二叉堆中h：

在最后一行： 第一个不等式意味着h是O(log N)。但是为什么第二个不等式意味着h是Ω(log N)？如果是“ log2(N) < h”，我会理解，但我的问题在于“ 1”中的“ h+1”。

特殊的 minHeap 是一个 minHeap，每个级别从左到右排序。在最坏的情况下， 如何n按顺序打印所有元素？O(n)

minHeap 是通过二叉堆实现的，其中的树是一棵完全二叉树（见图）。

下面是一个特殊的 minHeap 的例子：

所以结果应该是：[1,3,4,5,8,10,17,18,20,22,25,30]

来自家庭作业的问题。