问题标签 [max-heap]

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

}

我正在尝试实现一种算法，以在 O(1) 时间内找到具有 n 个不同元素的 Max-Heap 的第 10 个最大元素。

我试图绘制它并使用堆属性，但随着我深入堆，它变得越来越复杂。这是我制作的草稿，也是我坚持的地方——从我们有不同的元素和堆属性的事实来看，我们知道父级总是大于其子级。因此，根是最大元素。下一个最大元素是根的儿子之间的较大元素。

编辑：我还考虑过将较大的儿子与另一位父母的儿子进行比较。如果其中至少一个大于另一个父级，则通过堆属性，我们从最大的儿子继续并继续这样做直到我们有 10 个元素，但这并不总是正确的，因为随着我们深入，可能没有元素，现在我们需要从头再来。

任何解释甚至伪代码都会非常受欢迎。

提前致谢！

我正在使用算法，特别是堆排序。据我了解，堆排序算法涉及通过首先将列表转换为最大堆来准备列表。

转动我的

[2、8、5、3、9、1]

进入
[9, 8, 5, 3, 2, 1]

使用 heapsort 我应该用 1 交换 9。但是通过在最大堆之后直接查看数组，我看到一个按降序排列的排序列表。当列表已经按降序排序时，为什么需要交换？

这只是我看完后的想法： https ://www.youtube.com/watch?v=2DmK_H7IdTo

我有一个自定义任务类，其中包含优先级值以及一些附加字段，如下所示：

这些按优先级存储在最大堆中，效果很好。但是，如果我想找到具有特定 ID 值的 Task 对象，由于线性搜索（使用基本的 Tasks 数组作为堆），必须在 O(n) 时间内完成：

我遇到了几个对“修改堆”的引用，可用于将 ID 搜索改进到 O(1) 时间，但还没有找到具体的实现示例。这可能吗，如果可以，我该怎么做？非常感谢 Java 或伪代码示例，但即使只是相关数据结构的名称来开始我的搜索也会有所帮助。感谢您的任何帮助。

编辑：按要求添加的附加代码：

我正在尝试使用 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 个。

你有什么提示吗？

如果我们用简单的时间复杂度计算以自顶向下的方式构建堆有什么缺点。简而言之，使用第一种构建最大堆算法而不是常用的第二种算法

如果我有一个二叉最大堆（具有最大堆属性的几乎完整的二叉树），那么中位数是否总是一个叶节点？我找到了一些例子，但还没有找到反例——尽管到目前为止这还不足以让我正式证明这一点。

即对于中位数为 [3] 的值集 {1,2,3,4,5}，树将是：

所以在这种情况下，中位数是一个叶节点。

I use heapq module in python, I find I only can the min heap, even if I use reverse=True

I still get the min top heap

I still get the result:

I want to get result:

how to do it?

which is the smallest element. I want pop the largest emelment?

ps: this is part of question find the max and then divide into several elements and then put it back to the heap.

这是 Max-Heapify 算法的伪代码：

验证左堆的索引是否小于输入中给定的堆 A 的大小的目的是什么？