3

我正在寻找 Java 中 PQ 的一些实现，它允许按 PQ 顺序进行迭代 - 首先是顶部元素，接下来是下一个元素等。我尝试使用 TreeSet（它实现了 NavigableSet），但它会导致一个问题。就我而言：

  • 我正在为我的对象使用比较器
  • 由于某些外部操作而导致的优先级更改
  • 如果优先级发生变化，我知道哪个对象，但我不知道它是以前的优先级

结果到最后一点 - 当我想更新它的优先级时，我在 TreeSet 中找不到我的元素：/ 你碰巧知道：遵守这个的聪明方法吗？或者以“好”方式迭代的一些 PQ 实现？或者我应该创建一些链接数据结构，将对象与其在树中的位置相匹配？

更新：

  • 并发不是问题
  • 无法从 TreeSet 中删除对象，因为它的优先级已更改，因此 Comparator 将进行不同的评估，并且不会在此数据结构中找到对象。插入不是问题。
  • 我不能使用compareTo方法，因为此优先级不是比较这些对象的正确方法。这就是为什么我需要使用Comparator

可能的解决方案：

  • 创建PrioritizedObject将按优先级进行比较的类并保留我的对象
  • 使用地图：我的对象->PrioritizedObject
  • 保留PrioritizedObject一些NavigableSet

我会使用这张地图从NavigableSet. 如果我添加一些东西，当然会用新元素更新它。问题是我将不得不从中包装迭代器NavigableSet以使迭代器返回我的对象​​。

有没有更好的解决方案？

4

3 回答 3

0

如果并发不是问题，您需要做的就是在更新元素的优先级后立即重新排序树。如果我正确理解了这个问题，那么这个草图应该适合你。

示例元素：

public class Element implements Comparable<Element> {

private final Integer id;
private Integer priority;

public Element(Integer id, Integer priority) {
    this.id = id;
    this.priority = priority;
}

@Override
public String toString() {
    return "Element{" + "id=" + id + ", priority=" + priority + '}';
}

public Integer getPriority() {
    return priority;
}

public void setPriority(Integer priority) {
    this.priority = priority;
}

@Override
public int compareTo(Element o) {
    if (o == null) {
        throw new NullPointerException();
    }
    return priority.compareTo(o.priority);
}
}

草图：

public class Tree {

public static TreeSet<Element> priorityQueue = new TreeSet<Element>();

public static void dump(TreeSet<Element> in) {
    for (Element e : in) {
        System.out.println(e);
    }

}

public static void updatePriority(Element e, int newPriority) {
    if (priorityQueue.remove(e)) {
        e.setPriority(newPriority);
        priorityQueue.add(e);
    }
}

public static void main(String[] args) {

    int id;
    Element lastElement = null;
    for (int i = 0;i < 10 ; i++) {
        id = (int)(Math.random()*1000);
        priorityQueue.add(lastElement = new Element(id, id));
    }
    dump(priorityQueue);
    updatePriority(lastElement, 0);
    System.out.println("updating "+lastElement+ " priority to 0");
    dump(priorityQueue);

}
}

您可以通过从treeset中删除元素、设置新的优先级然后重新插入来更新元素。这种情况下更新操作的复杂性是2*O(log(n)) = O(log(n))

更新：

我能理解的最好的是：您有两个需要排序/索引的标准。当我遇到同样的问题时，我使用了这种方法，但这是一种非常有趣的方法，我强烈推荐阅读。

于 2013-04-03T09:09:32.873 回答
0

如果优先级发生变化，我知道哪个对象，但我不知道它是以前的优先级

你不需要知道它以前的优先级。您所要做的就是将其删除并重新插入。

于 2013-04-03T09:10:35.963 回答
0

我建议ConcurrentSkipListSet不要，TreeSet因为它是线程安全的。如果您知道优先级正在发生变化的对象，您可以调用remove(objToChange)，更改其优先级，然后将其重新添加到集合中。

equals向集合中添加其、hashcode和compareTo方法依赖于可变字段的任何对象时要非常小心。

编辑：我认为任何解决方案最终都会看起来像你的PrioritizedObject，这对我来说似乎很好。如果要遍历对象，请使用Map.keySet.

于 2013-04-03T09:06:22.890 回答