为什么 PriorityQueue peek() return 的最大值是错误的？

Question

我正在使用 PriorityQueue 获取最大整数，但我不明白为什么第一种方法 returns 是正确的最大整数，而第二种方法不是。第二种方法尝试更新目标项目的大数字；但是当我在调用更新方法后尝试 peek() 方法时，它仍然打印出旧的最大数量而不是更新后的新最大数量。

这是我的代码：

void add(String name, int number) {
    Item item = new Item(name, number, allItems.size());
    allItems.add(item);
    hashMap.put(name, item);
}

void update(String name, int number) {
    Item item = hashMap.get(name);

    // EDITED: 
    allItems.remove(item);

    item.setNumber(item.getNumber() + number);
    allItems.add(item);
    hashMap.put(name, item);    
}

EDITED：似乎只有当我从 allItems 中删除目标项目时它才有效（请参阅更新方法中的 EDITED）。为什么会这样？

class Item implements Comparable<Item>{
        private String name;
        private int number;
        private int arrived;

        public Item(String name, int number, int arrived) {
            this.name = name;
            this.number = number;
            this.arrived = arrived;
        }

        @Override
        public int compareTo(Item o) {

            int x = this.getNumber();
            int y = o.getNumber();

            if (y > x) return 1;
            if (y < x) return -1;


            if (this.arrived > o.arrived) return 1;
            if (this.arrived < o.arrived) return -1;

            return 0;
        }

    }

Answer 1

很可能，您对 `Comparable` 的实施不正确。

您的 Comparable 实现是 PriorityQueue 用来了解如何根据字段值对项目进行排序的。您必须以 DECREASING 顺序实施 Comparable。如果 other 项目更大，你希望它 return -1，如果 this 项目更大；在您的代码中，您正在做相反的事情。换句话说，确保您的 Item class 定义如下所示：

public class Item implements Comparable<Item> {
  private int number;
  private int arrived;

  // the rest of your code

  public int compareTo(Item other) {
    int numberCompare = Integer.compare(other.number, this.number);
    if (numberCompare == 0) {
      return Integer.compare(other.arrived, this.arrived);
    } else {
      return numberCompare;
    }
  }
}

如果不想更改 Item 的 class 定义，也可以使用 PriorityQueue(int initialCapacity, Comparator comparator)。

根据 Javadoc for PriorityQueue:

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).

为什么 PriorityQueue peek() return 的最大值是错误的？

Why does PriorityQueue peek() return the wrong maximum value?

java

priority-queue

很可能，您对 `Comparable` 的实施不正确。

为什么 PriorityQueue peek() return 的最大值是错误的？

Why does PriorityQueue peek() return the wrong maximum value?

java

priority-queue

很可能，您对 Comparable 的实施不正确。

很可能，您对 `Comparable` 的实施不正确。