标签: min-heap

使用最小/最大堆算法时,优先级可能会发生变化.处理此问题的一种方法是删除并插入元素以更新队列顺序.

对于使用数组实现的优先级队列,这可能是一个似乎可以避免的性能瓶颈,特别是对于优先级变化较小的情况.

即使这不是优先级队列的标准操作,这也是一个可以根据我的需要进行修改的自定义实现.

是否有众所周知的最佳实践方法来更新min/max-heap中的元素？

背景信息:我不是二叉树专家,我继承了一些代码,这些代码在优先级队列中重新插入了元素.我为重新排序新元素的min-heap做了一个重新插入函数 - 这给了一个可测量的改进(删除和插入),但这似乎是其他人可能已经解决的更优雅的问题办法.

我可以链接到代码,如果它有所帮助,但宁愿不太关注实现细节 - 因为这个Q&A可能保持一般.

val maxHeap = scala.collection.mutable.PriorityQueue[Int] //Gives MaxHeap

使用Ordering将PriorityQueue转换为minHeap最简洁有效的方法是什么？

我想比较以下数组的第二个元素：

int[][] intervals = new int[][]{new int[]{0, 30},new int[]{5, 10},new int[]{15, 20}};

我的优先级队列与自定义比较器：

PriorityQueue<int[]> heap = new PriorityQueue(intervals.length, (a, b) -> a[1] - b[1]);

但我收到以下 2 个错误：

Line 8: error: array required, but Object found
        PriorityQueue<Integer[]> heap = new PriorityQueue(intervals.length, (a, b) -> a[1] - b[1]);
                                                                                       ^
Line 8: error: array required, but Object found
        PriorityQueue<Integer[]> heap = new PriorityQueue(intervals.length, (a, b) -> a[1] - b[1]);
                                                                                             

我试图用自定义比较器实现带有Priorityqueue的MST,但是我在O(n)时间内用它构建min-heap时遇到了问题.问题是,Priorityqueue的一个构造函数只允许在O(n)中创建PriorityQueue,但它不会将任何比较器作为参数.我希望它使用我的自定义比较器.这个问题有解决方法吗？PriorityQueue.addAll()将失去使用Min-heap作为MST的目的,因为它是O(nlogn)方法.这是我的代码.

ArrayList <edge>ar=new ArrayList<>(); 
   for(int i=0;i<e;i++)
   {
       int u=ss.nextInt();
       int v=ss.nextInt();
       int w=ss.nextInt();
       ar.add(new edge(u,v,w));
   }
   PriorityQueue <edge>pr=new PriorityQueue<edge>(ar);

我要使用的比较器: -

PriorityQueue <edge>ar=new PriorityQueue(11,new Comparator() {
        @Override
        public int compare(Object o1, Object o2) {
            edge n1=(edge) o1;
            edge n2=(edge) o2;
            if(n1.w<n2.w)
            {
                return -1;
            }
            else if(n1.w==n2.w)
            {
                if((n1.u+n1.v+n1.w)<=(n2.u+n2.v+n2.w))
                {
                    return -1;
                }   
                else
                {
                    return 1;
                }
            }
            else
            {
                return 1;
            }
        }
    });

我试图在c ++中为我创建的结构类型实现最小堆.我创建了一个类型的向量,但是当我在其上使用make_heap时崩溃了,这是可以理解的,因为它不知道如何比较堆中的项目.如何为结构类型创建最小堆(即顶部元素始终是堆中的最小元素)？

结构如下:

struct DOC{

int docid;
double rank;

};

我想使用rank成员比较DOC结构.我该怎么做？

我尝试使用带有比较器类的优先级队列,但也崩溃了,使用数据结构似乎很愚蠢,当我真正需要的是堆时,使用堆作为其底层基础.

非常感谢,bsg

我有一个关于使用最小堆查找第 k 大元素的问题。算法如下：

1. 我们取出前 k 个元素并构建一个最小堆

2. 设 Sk 为 S 中最小的元素。

3. 从剩余的 nk 元素中查看一个新元素。

4. 如果新元素大于 Sk，则将其替换到 S 中，并对堆重新排序。

5. 然后 S 将有一个新的最小元素。

6. 看完所有其他元素后，Sk就是答案

我不明白这个算法。例如，让数字为1,2,3,4。我们想要找到第四大的，即4。但是当我们使用该算法时，我们取前4个元素，构建minheap，Sk为1。

我究竟做错了什么？如果有人可以提供帮助，我将不胜感激。谢谢

我正在尝试构建一个最小堆.我已经完成了插入,删除,交换,上堆,下堆,它正常工作.

但是,我正在尝试为Min-Heapify编写一个方法.

这是我的输入:{20,14,9,6,4,5,1}

我预期的输出将是最小堆:{1,5,4,20,9,6,14}但我得到的是:{14,6,9,20,4,5,1}这是相反.

这是我的代码:

public void minHeapify(int parentIndex)
    {
        int left = getLeft(parentIndex);
        int right = getRight(parentIndex);
        int smallest = parentIndex;
        if(_size >right && _heapArray[left]<_heapArray[parentIndex])
        {
            smallest = left;
        }

        if(_size>left && _heapArray[right]<_heapArray[parentIndex])
        {
            smallest = right;
        }
        if(smallest !=parentIndex)
        {
            replace(parentIndex, smallest);
            minHeapify(smallest);
        }
    }

我按照这个伪代码进行MAX-Heapify

Heapify (A, i)
l ? left [i]
r ? right [i]
if l ? heap-size [A] and A[l] > A[i]
then largest ? l
else largest ? i
if r ? …

我昨天问了一个问题,但不是很清楚所以这是一个更具体的问题.

我将我的minheap表示为数组.我认为我对minheaps有很好的理解,但我对其中的某个概念很模糊.Minheaps总是应该以最小的节点作为根.要删除值,将根设置为数组表示形式中的最后一个元素(叶节点),并减小数组的大小.然后使用siftDown/PercolateDown或任何您想要调用它的方式正确放置根节点.这是超级高效的.例如:

这里有29个取自最后一个元素,siftDown(1)将它放置:

1. 将29与15和38进行比较.交换29和15.
2. 将29与25和20进行比较.交换29和20.
3. 29比较30,29 <30因此我们完成了.

这一切都很好,但是如果在两个删除min的实例之间,其他一些数据会发生变化呢？例如:

在这里,然后:

1. 将29与15和38进行比较.交换29和15.
2. 将29与30和32进行比较.29 <30和29 <32因此我们完成了.

1是树中的最小值,但它没有被设置为min,15已经.这对我来说是个大问题.我正在尝试实现Dijkstras算法,我也试图使用我自己的数据结构而不触及java内置的类.

所以我的问题的一个更相关的例子是:

对于那些熟悉Dijkstras的人来说,99表示无穷远的暂定距离,其他数字表示接下来应该访问的图节点(距离最小的节点,在本例中为3).

解决方案是每次删除min时重建树,但这意味着minheap的功能会丢失,并且任何实现都会减慢到爬行速度.

抱歉,如果我不能理解这一点,但我已经坚持了几天,我真的需要一些帮助.

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

特别是，我正在使用来自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个最小的元素。在最大堆中，最小不是根，那么为什么更好使用呢？对于数组中的升序或降序排序也是如此。我看到大多数人使用最大堆来提升。