问题标签 [heap]

在选择要在二进制堆中向下渗透的子节点方面是否有任何优化？例如，在最小堆中，如果父节点是 10，其子节点是 8 和 3，那么交换哪个节点更好？

选择与较大的子节点交换似乎会增加停止的可能性，因为它下面的子节点将大于 8。是否对此进行过任何研究？

基本上我需要使用 sqlite 作为我的数据存储的最小堆功能。
假设我需要一个有 2 列的表。第一个是唯一的 ID，
第二个是整数值。
我总是需要具有最小整数值的 id。

有什么建议么 ？？

我正在编写一个需要我使用堆的程序，除了我的排序方法之外，一切都运行良好，显然非常重要！我不确定我的逻辑有什么问题，或者我是否遗漏了一些愚蠢的东西。但是，如果有一双新的眼睛来看待这件事，那就太好了。

函数被传递给我的向量，它当然是堆、根的位置，然后是 STL less 或 greater 作为谓词。

知道有什么问题吗？

可能重复：
如何在 Python 的 heapq 中实现减少键功能？

你好，

我在 Python 中使用 heapq 来实现优先级队列。队列中的项目的优先级发生了很大变化，当发生这种情况时，我需要堆化 heapq。
问题是 heapq 只有一个 heapify 函数来堆整整个堆，而不是从堆内的某个项目开始的 heapify 知道其余部分已经是一个有序的堆（就像经典的 CS 教科书 heapify）。
差异很大，因为每个 heapify 调用都是 O(n) 而不是 O(lgn)。可以在不使用标准列表实现堆的情况下完成吗？

谢谢！

看来我的问题与如何在 Python 的 heapq 中实现减少键功能重复？
那里的答案表明，没有办法使用特定项目的适当 O(lgn) heapify 重新实现基于堆的队列。

不久前，我们被分配编写 ac 程序，该程序使用 d-ary max-heap（每个节点最多有 d 个子节点的堆）对包含 n 个数字的数组进行排序。程序需要要求用户输入 d 的值，一个介于 2 和数组大小之间的值。当我检查我的程序时，我不小心输入了 1 作为 d 的值，并且不知何故，该算法成功地使用一元堆正确地对数组进行了排序，尽管它比 d 的正常值花费了更多的时间。

这怎么可能？一元堆甚至不是堆，它就像一个列表，每个节点只有一个孩子。谁能解释这种排序是如何发生的？

我的问题如下：

给定一个三元组列表，它们存储在一个名为 hash_heap 的数据结构中（我不确定名称，只是表示它应该是哈希表和堆的混合体）。我希望数据结构提供以下方法，

是否可以实现一些这样的数据结构？我知道 hashtable 可以支持第一种方法，而 heap 可以支持第二种和第三种方法，但我不知道如何将它们混合在一起。有任何想法吗？

谢谢！

我发现了很多 MinMax Heap 实现，它们将数据存储在一个数组中。这真的很容易实现，这就是我正在寻找不同的东西的方式。我想创建一个 MinMax 堆，只使用堆的元素和指向左孩子和右孩子的指针（当然还有一个比较的键）。所以堆只有指向根对象的指针（最小级别），而根对象有一个指向他的孩子的指针（最大级别）等等。我知道如何插入一个新对象（根据堆大小使用 int 的二进制表示找到正确的路径），但我不知道如何实现其余的（上推（下推）元素，查找父级或祖父级） .

谢谢帮助

总的来说，我正在尝试使用优先级队列来实现 Dijkstra 算法。

根据 golang-nuts 的成员，在 Go 中执行此操作的惯用方式是使用带有自定义底层数据结构的堆接口。所以我像这样创建了 Node.go 和 PQueue.go：

和 PQueue.go：

和 main.go：（动作在 SolveMatrix 中）

问题是，在编译时我收到错误消息：

并注释掉 PQ.Push(firstNode) 行确实满足编译器。但我不明白为什么我首先收到错误消息。Push 不会以任何方式修改参数。

更新：为了那些将来在搜索中遇到这种情况的人，上面的代码充满了严重的误解。看看下面的一个更有用的模板来工作：Node.go：

PQueue.go：

给定以下代码：

为什么返回值如下：

如果我调用 sort_heap(v.begin(), v.end(), Greater)，则返回值为30 20 15 10 9.

问题 > 在这个示例中，我创建了一个最小堆。这就是我不能调用 sort_heap(v.begin(), v.end()) 的原因吗？

谢谢你

面试题：

下面编辑 给你一个数组。你用它做了 2 个堆，一个 minheap 和另一个 max heap。现在使用这 2 个提供的堆在 O(nlog n) 时间内找到数组的中位数。

更正的问题 编号随机生成并存储到（扩展）数组中。您将如何跟踪中位数？

解决方案 这个问题可以使用 2 个堆来解决，并且总是可以在 O(1) 时间内访问中位数。