标签: priority-queue

我需要实现一个优先级队列,其中队列中项目的优先级可以更改,队列自行调整,以便始终以正确的顺序删除项目.我有一些关于如何实现这一点的想法,但我确信这是一个非常常见的数据结构,所以我希望我可以使用比我更聪明的人作为基础的实现.

任何人都可以告诉我这种类型的优先级队列的名称,所以我知道要搜索什么,或者更好的是,我指向一个实现？

我已经实现了一种压缩算法(使用霍夫曼编码),它使用节点的优先级队列(我定义的结构).现在,当我在linux或visual studio中运行代码时,一切正常.当我检查visual studio中的内存泄漏时,没有给出.

现在的问题是,当我使用valgrind分析我的程序时,它终止于信号11(sigsegv).遇到的第一个错误是方法delete min中的"无效读取大小4".之后的其他错误是:Adress是释放大小为453的块内的0字节,无效写入大小4,无效释放,删除或重新分配.

任何人都可以就我可能犯的错误给出建议吗？我一直在互联网上搜索几个小时,但找不到我做错了什么(特别是因为它在没有使用valgrind时才起作用).或者提示如何调试并找出导致读取错误的原因.

非常感谢!

这是代码,以防有人想要查看它,但我想这并不是那么容易潜入这个特定的代码.

我猜它与代码的优先级队列有关:

我做霍夫曼部分的部分 - >每次删除2个最小节点并将两者的总和作为一个节点添加.

while(queue->size > 1){
    node* n1 = delete_min(queue);
    node* n2 = delete_min(queue); // all the errors are encountered in this call
    node* temp = (node*) calloc(sizeof(node),1);
    temp->amount = n1->amount + n2->amount;
    insert_node(queue,temp);
    n1->parent = temp;
    n2->parent = temp;
    temp->left = n1;
    temp->right = n2;
}

以下是优先级队列的delete_min和insert_node方法:

void insert_node(priority_queue* p_queue, node* x){
    int i = p_queue->size;
    if(i == 0){
        p_queue->queue = (node**) malloc(sizeof(node*));
    }
    else{
        p_queue->queue = (node**) realloc(p_queue->queue,sizeof(node*)*(p_queue->size+1));
    } …

我正在尝试使用自定义比较函数在c ++中声明一个优先级队列...

所以,我声明队列如下:

std::priority_queue<int,std::vector<int>, compare> pq;

这是比较功能:

bool compare(int a, int b)
{
   return (a<b);
}

我很确定我之前没有类,以类似的方式做过这个,但是现在,这段代码没有编译,我得到了几个这样的错误:

type/value mismatch at argument 3 in template parameter list for 'template<class _Tp, class _Sequence, class _Compare> class std::priority_queue'

有没有办法创建一个类似于此但没有使用类的比较函数？

谢谢

我正在写一个有三个优先队列作为私人成员的班级.

class Foo {
...
...

private:
  // I am fine with using pointers instead if it helps.
  std::priority_queue<int> first;   // min heap.
  std::priority_queue<int> second;  // max heap.
  std::priority_queue<int> third;  // min heap.
};

现在我需要first并third以a min heaps和seconda 开始max heap.作为我班级功能的一部分,我需要做以下事情:

1. 移动second到first.理想情况下,这是通过最低的复制量来实现的.应该移动底层矢量.此外first,现在应该表现得像max heap.
2. 移动third到second.这意味着second现在应该表现得像min heap.
3. 由于third已将内容移至second,因此应为空.我想要分配一个新的底层向量或重用first's底层向量(它不再需要它.另外第三个现在应该是一个max heap.

我需要执行此循环(max - …

PriorityBlockingQueue是无限的,但我需要以某种方式约束它.实现这一目标的最佳方法是什么？

有关信息,有界PriorityBlockingQueue将用于a ThreadPoolExecutor.

注意:通过有界我不想抛出异常,如果发生这种情况,我想将对象放入队列中,然后根据其优先级值进行剪切.有什么好方法可以做这件事吗？

我正在使用priority_queue将vector作为底层容器.但是我希望堆的大小非常大.我知道动态矢量容量调整大小的问题.所以我正在寻找最初为priority_queue中的底层向量分配足够空间的方法.有什么建议可以实现这个目标吗？

谢谢

我需要知道二进制和二进制堆之间的主要区别,不管它们的结构差异,二元堆只能有两个子(树表示),二项堆可以有任意数量的子.

我实际上只是想知道组织二项式树结构的特别之处在于第一个孩子在一个节点上有第二个有两个第三个有四个等等吗？

如果我们使用一些普通的树而没有两个孩子的限制然后应用联合过程而只是让一个堆成为其他堆的左子？

我想知道为什么使用the创建一个最小堆priority_queue,std::greater应该使用？

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

对我来说,由于最小的值总是位于堆的顶部,所以应用的类应该是 std::less

更新: 另一方面,由于priority_queue(max heap)的默认行为是在顶部保持最大值,因此我认为std::greater应该用于最大堆创建而不是用于创建最小堆

我正在尝试编写一个利用最小优先级队列的算法,所以我在谷歌上环顾四周找到了PriorityQueue.看来,为了使用它,我需要告诉它我希望它如何优先排序,并且这样做的方法是使用比较器(我想比较我的"Node1"的特定数据字段)对象).更多的谷歌搜索提出了创建一个新比较器的想法,该比较器实现了比较器,但覆盖了比较方法.我正在尝试的是这个(以及它的其他变体):

import java.util.Comparator;

public class distComparator implements Comparator {

    @Override
    public int compare(Node1 x, Node1 y){
        if(x.dist<y.dist){
            return -1;
        }
        if(x.dist>y.dist){
            return 1;
        }
        return 0;
    }
}

编译器有几个理由抗议,其中一个原因是我没有超越比较器类(它说它是抽象的)

错误:distComparator不是抽象的,并且不会覆盖Comparator中的抽象方法compare(Object,Object)

我已将其切换为"比较(对象x,对象y)",它负责该问题.此时虽然编译器抱怨它无法在x或y中找到"dist"变量 - 这是有道理的,因为它们是我的Node1类的一部分,而不是Object类.

那应该怎么做呢？它Object显然应该有类型,但是如何将它引导到正确的变量？

我正在尝试使用优先级队列来实现dijkstra算法,但我无法理解它是如何工作的.我在网上阅读了很多指南,但我根本无法理解这个算法.

我的问题是:每个节点的优先级是什么？我认为它是最小值的传入边缘的权重,但我不确定.这是真的？

第二个问题,当我提取队列的根时,如果该节点不与没有一个被访问节点相邻,那么该如何工作？