问题标签 [min-heap]

如何在 prolog 中获取谓词以返回值？

我需要找到树的一个节点，并检查它是否是最小堆。我猜它是这样的： -

到目前为止我的代码是这样的

输入的类型是-

输出应该是真的。

我在考试中得到了这个问题，但我不确定我是否理解它要我做什么。如果我做了正确的事情，你能澄清一下吗？

问题

一个整数数组 A 被传递给函数makeHeap。如果 A[0] 包含 n，则 A[1] 到 A[n-1] 包含任意顺序的数字。写成makeHeapA[1] 到 A[n-1] 包含一个最小堆。您的函数必须通过按 A[2]、A[3]、...、A[n-1] 的顺序处理元素来创建堆。

我的解决方案

这个解决方案甚至远程正确吗？另外，siftUp函数的名称是否正确？

编辑：

我的新解决方案

我正在尝试从头开始实现我自己的 PriorityQueue 类（不使用任何现有的 Java 导入或库）。我知道我想使用最小堆数据结构。但我将堆可视化为二叉搜索树上的一种形式。我应该使用链表样式节点来实现这个最小堆，还是应该使用数组？两者的好处或首选方法是什么？或者我可以使用第三种选择吗？

我有最小堆的 Dijkstra 实现，我试图将最小堆更改为最大堆以找到最大路径，但我做不到，输出错误所以，请你帮我将此实现更改为最大堆？非常感谢

}

您好，我想知道这些 x 是否位于最小堆的正确位置？我对么？

我正在尝试保留一大组元组的前 k 个元素的列表。由于不可能将其保存在内存中，因此我想使用固定大小的列表来仅保留前 k 个值（使用键）。我曾尝试使用最小堆，但 python 的堆很糟糕，因为它允许插入非唯一键。这是一个巨大的问题。所以我想我可以使用排序列表/字典（具有唯一键的元组）。使用草图函数我检索子字符串在整个文本中出现的计数（O（1）时间））。我开始认为我在循环或弹出和分配方面做错了，因为 minheap 也有类似的问题，只有前 k 出现在 25 大小列表中，其余的计数相当低（当它在事实更高）

我正在尝试使用 heapq 模块（ https://docs.python.org/3/library/heapq.html ）中的 Python（2.0）内置最小堆数据结构来构建最大堆。为此，我只需使用需要推入堆中的数字的负数。

使用这个（最大堆版本）：

我得到一些看起来不正确的东西：

最小堆版本看起来不错：

如你看到的：

我错过了什么？

我检查了其他 SE 问题/答案（例如，python topN 最大堆、使用 heapq 还是自我实现？、我在 Python 中使用什么来实现最大堆？等）但他们没有提到这个问题。

我正在尝试返回一系列流数字的运行中位数。为此，我使用了一个最大堆（将值存储在系列的下半部分）和一个最小堆（将值存储在系列的上半部分）。

特别是我正在使用来自 heapq 模块（ https://docs.python.org/2/library/heapq.html ）的 Python (2.0) 内置 min-heap 数据结构。相反，要构建最大堆，我只需使用需要推入堆中的数字的负数。

我的 Python 代码如下：

以下是我为检查代码而构建的测试用例的完整列表：

我的代码对我来说似乎没问题，但我无法通过在线法官 ( https://www.hackerrank.com/challenges/ctci-find-the-running-median/problem )的 10 个测试用例中的 4 个。

你有什么提示吗？

有一个问题询问从最小堆中获取最小元素是否是 o(logn) 时间，我认为这是错误的，因为它需要恒定时间，因为最小元素在顶部。但答案是正确的，导师的解释是常数时间也是 O(logn)，这是一个措辞问题。我很困惑。所以在实践中，我们是否认为常数时间是 O(logn) 的运行时间？

我是堆新手，并试图了解堆是如何工作的。你如何找出最小堆中的最大值？我知道可以通过查找根来找到最小值，但是最小堆中的最大值呢？不是在寻找代码，更多的是为了理论和我的理解。