标签: max-heap

我想知道是否允许最大或最小堆树具有重复值？我一直试图通过在线资源找到有关这方面的信息是不成功的.

我在python中使用heapq模块,我发现我只能使用min heap,即使我使用reverse = True

我仍然得到最小的顶级堆

from heapq import *

h=[]
merge(h,key=lambda e:e[0],reverse=True)
heappush(h, (200, 1))
heappush(h, (300,2))
heappush(h, (400,3))
print(heappop(h))

我仍然得到结果:

(200, 1)

我想得到结果:

(400,3)

怎么做？

这是最小的元素.我想要流行最大的emelment？

ps:这是问题的一部分找到max然后分成几个元素然后把它放回堆中.

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

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

我的Python代码如下：

import heapq

maxh = []
minh = []
vals=[1,2,3,4,5,6,7,8,9,10]
for val in vals:

    # Initialize the data-structure and insert/push the 1st streaming value
    if not maxh and not minh:
        heapq.heappush(maxh,-val)
        print float(val)
    elif maxh:

        # Insert/push the other streaming values
        if val>-maxh[0]:
            heapq.heappush(minh,val)
        elif val<-maxh[0]:
            heapq.heappush(maxh,-val)

        # Calculate the median
        if len(maxh)==len(minh):
            print float(-maxh[0]+minh[0])/2
        elif len(maxh)==len(minh)+1:
            print float(-maxh[0])
        elif len(minh)==len(maxh)+1:
            print float(minh[0])

        # If min-heap and max-heap grow unbalanced we rebalance them by
        # removing/popping …

我很难理解为什么找到第k个最小元素的解决方案使用最大堆方法。对于第k个最大元素，使用最小堆方法。使用最小堆来查找第k个最小元素是否更有意义，因为最小元素将始终是根？因此，如果要查找第3个最小的元素，则只需删除根两次，构建堆，然后得到第3个最小的元素。在最大堆中，最小不是根，那么为什么更好使用呢？对于数组中的升序或降序排序也是如此。我看到大多数人使用最大堆来提升。

我试着看http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-4-heaps-and -heap-sort/了解堆和堆排序，但没有发现这一点。

我不明白 max-heapify 的功能。它看起来像一个递归函数，但不知何故，由于树的高度，它以对数时间运行。

对我来说这毫无意义。在最坏的情况下，它不是必须反转每个节点吗？我不知道如何在不反复接触每个节点的情况下完成此操作。

我有一个家庭作业问题说:

问题1:给定数组[22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66]为数组构建最大堆.显示所有步骤而不跳过任何细节.

这是我对在互联网上研究的最大堆的理解:

最大堆是一个可以更容易用二叉树表示的数组,其中父节点总是大于它的子节点,并且"每次添加一个子节点时,你都将它添加到左边,这样每次树增加它的高度时它是一棵完整的树"

不管怎样,这就是我构建的

我认为这是正确的答案,直到我读到我的作业问题2说:

问题2:使用与问题1中相同的数组,使用Heapsort对数组进行排序.显示所有步骤而不跳过任何细节.

现在我很困惑.也许我回答了问题2 ...

我有一个大小为10的整数数组.我需要绘制完成的二叉树.现在我需要使用siftup过程插入其他三个元素.显示每个插入后的最大堆.

我不确定是什么显示每个插入后的最大堆.这是否意味着每次插入一个元素时我需要显示最大堆的大小？

定义(最大堆)HEAP(X)设X是一个完全有序的集合.X上的堆是空的,∅,或者它是一个完整的二叉树,t,包括nt≥1个节点到每个节点,其中X的值被分配,使得:节点i的值≤节点i的父节点的值,i = 2,3,...,nt.堆的大小是树中的节点数.当且仅当其大小为0时,堆为空.

max heap的定义是这样的,但对我来说看起来有点模棱两可.

所以我和我的朋友在这个问题上没有一致的看法.它要求在n个元素的最大堆中搜索第7个最大元素的时间复杂度？

我认为它应该是O(n)并且她认为它应该是O(1).我的逻辑是假设n是7然后第7个最大元素将是堆中的最后一个元素,所以如果我们考虑最坏的情况它应该是O(n).然而她说,因为它是最大堆,所以找到第7大元素应该花费不变的时间.但是使用她的逻辑甚至可以在O(1)时间内找到第50大元素或第100大元素.我们遇到这个问题的书也说解决方案是O(logn).

有人可以告诉我哪种解决方案是正确的？

可能重复:
我在Python中使用什么来实现最大堆实现？

我试图以某种方式实现python的heapq但是对于max-heap.一个解决方案是使用(-1)和多个队列号,但这对我没有帮助,因为我需要将URL存储在堆中.所以我想要一个max heapq,我可以弹出最大的值.

我知道std::priority_queue该类实现了最小堆。有没有办法将其用作最大堆？还是有替代的Maxheap结构？我知道我可以std::make_heap()在std::vectorlambda 上使用该函数来创建自己的Maxheap，但是随后使用诸如std::pop_heap()怪异的函数，并且我认为它们不易于使用。应该有一种更简单的方法，就像我认为的min_heap（priority queue）。