问题标签 [heap]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
binary - 向下渗透/筛选二进制堆启发式
在选择要在二进制堆中向下渗透的子节点方面是否有任何优化?例如,在最小堆中,如果父节点是 10,其子节点是 8 和 3,那么交换哪个节点更好?
选择与较大的子节点交换似乎会增加停止的可能性,因为它下面的子节点将大于 8。是否对此进行过任何研究?
sql - 当我只需要在整数列中插入和检索最小条目时,sqlite 中的高效数据库设计是什么?
基本上我需要使用 sqlite 作为我的数据存储的最小堆功能。
假设我需要一个有 2 列的表。第一个是唯一的 ID,
第二个是整数值。
我总是需要具有最小整数值的 id。
有什么建议么 ??
c++ - c++ 筛选堆
我正在编写一个需要我使用堆的程序,除了我的排序方法之外,一切都运行良好,显然非常重要!我不确定我的逻辑有什么问题,或者我是否遗漏了一些愚蠢的东西。但是,如果有一双新的眼睛来看待这件事,那就太好了。
函数被传递给我的向量,它当然是堆、根的位置,然后是 STL less 或 greater 作为谓词。
知道有什么问题吗?
python - 如何在 O(lgn) 中堆积 heapq?
你好,
我在 Python 中使用 heapq 来实现优先级队列。队列中的项目的优先级发生了很大变化,当发生这种情况时,我需要堆化 heapq。
问题是 heapq 只有一个 heapify 函数来堆整整个堆,而不是从堆内的某个项目开始的 heapify 知道其余部分已经是一个有序的堆(就像经典的 CS 教科书 heapify)。
差异很大,因为每个 heapify 调用都是 O(n) 而不是 O(lgn)。可以在不使用标准列表实现堆的情况下完成吗?
谢谢!
看来我的问题与如何在 Python 的 heapq 中实现减少键功能重复?
那里的答案表明,没有办法使用特定项目的适当 O(lgn) heapify 重新实现基于堆的队列。
algorithm - 一元堆排序?
不久前,我们被分配编写 ac 程序,该程序使用 d-ary max-heap(每个节点最多有 d 个子节点的堆)对包含 n 个数字的数组进行排序。程序需要要求用户输入 d 的值,一个介于 2 和数组大小之间的值。当我检查我的程序时,我不小心输入了 1 作为 d 的值,并且不知何故,该算法成功地使用一元堆正确地对数组进行了排序,尽管它比 d 的正常值花费了更多的时间。
这怎么可能?一元堆甚至不是堆,它就像一个列表,每个节点只有一个孩子。谁能解释这种排序是如何发生的?
algorithm - 如何设计混合哈希表和堆的数据结构
我的问题如下:
给定一个三元组列表,它们存储在一个名为 hash_heap 的数据结构中(我不确定名称,只是表示它应该是哈希表和堆的混合体)。我希望数据结构提供以下方法,
是否可以实现一些这样的数据结构?我知道 hashtable 可以支持第一种方法,而 heap 可以支持第二种和第三种方法,但我不知道如何将它们混合在一起。有任何想法吗?
谢谢!
heap - 没有数组的 MinMax Heap 实现
我发现了很多 MinMax Heap 实现,它们将数据存储在一个数组中。这真的很容易实现,这就是我正在寻找不同的东西的方式。我想创建一个 MinMax 堆,只使用堆的元素和指向左孩子和右孩子的指针(当然还有一个比较的键)。所以堆只有指向根对象的指针(最小级别),而根对象有一个指向他的孩子的指针(最大级别)等等。我知道如何插入一个新对象(根据堆大小使用 int 的二进制表示找到正确的路径),但我不知道如何实现其余的(上推(下推)元素,查找父级或祖父级) .
谢谢帮助
heap - 使用容器/堆来实现优先级队列
总的来说,我正在尝试使用优先级队列来实现 Dijkstra 算法。
根据 golang-nuts 的成员,在 Go 中执行此操作的惯用方式是使用带有自定义底层数据结构的堆接口。所以我像这样创建了 Node.go 和 PQueue.go:
和 PQueue.go:
和 main.go:(动作在 SolveMatrix 中)
问题是,在编译时我收到错误消息:
并注释掉 PQ.Push(firstNode) 行确实满足编译器。但我不明白为什么我首先收到错误消息。Push 不会以任何方式修改参数。
更新:为了那些将来在搜索中遇到这种情况的人,上面的代码充满了严重的误解。看看下面的一个更有用的模板来工作:Node.go:
PQueue.go:
c++ - 为什么 sort_heap 没有按照我预期的顺序放置元素?
给定以下代码:
为什么返回值如下:
如果我调用 sort_heap(v.begin(), v.end(), Greater),则返回值为30 20 15 10 9
.
问题 > 在这个示例中,我创建了一个最小堆。这就是我不能调用 sort_heap(v.begin(), v.end()) 的原因吗?
谢谢你
algorithm - 跟踪扩展数组的中位数
面试题:
下面编辑 给你一个数组。你用它做了 2 个堆,一个 minheap 和另一个 max heap。现在使用这 2 个提供的堆在 O(nlog n) 时间内找到数组的中位数。
更正的问题 编号随机生成并存储到(扩展)数组中。您将如何跟踪中位数?
解决方案 这个问题可以使用 2 个堆来解决,并且总是可以在 O(1) 时间内访问中位数。