在 Java 中修改 PriorityQueue 中的项目

Modifying an item in a PriorityQueue in Java

提问人:curiousengineer 提问时间:10/18/2023 最后编辑:Chaosfirecuriousengineer 更新时间:10/18/2023 访问量:57

问:

假设我有一个自定义类,如下所示

class Emp {
   String name;
   Integer id;
}

我决定在 java 中使用 PriorityQueue 来插入 Emp 的元素,并在类的字段上提供自定义比较器。idmax-heap

我理解并将保持堆属性完好无损。现在我的问题是,如果我想修改 的实例的值,我该怎么做?即使我维护一个 HashMap 来查找我想要随时修改的对象,即使我这样做,它也会破坏堆属性。不是吗?popofferidEmp

实现这一目标的最佳方法是什么?我也不能从堆中随机删除元素并重新插入?

我应该只用一个吗?TreeMap

java 数据结构 优先级队列

评论

4赞 David Conrad 10/18/2023
您必须从 PriorityQueue 中删除该实例,对其进行修改,然后再次添加。使用 TreeMap 无济于事。同样的问题也适用,需要相同的解决方案。这些数据结构不希望它们包含的数据即时更改。
1赞 David Conrad 10/18/2023
您可以使用 remove(Object o) 从堆中删除元素,但时间复杂度是线性的,O(n)。所以,不是很好。
0赞 curiousengineer 10/18/2023
如果我使用 TreeMap,我相信它可能比堆更好,因为树状图中的删除比在 PQ 中查找节点并删除它更快
0赞 David Conrad 10/18/2023
这可能是真的,是的。在 TreeMap 中查找要删除的项目会更快。
1赞 dan1st 10/18/2023
@AbdulAlimShakir 我不认为 JDK 包含一个名为 .那是来自图书馆吗?IndexedPriorityQueue

答: 暂无答案