Java优先队列自定义比较器

Question

在我的优先队列中，有两种类型的客户：VIP和普通。我想先为VIP服务，然后为普通客户服务。

如果CustomerID < 100，则被视为VIP。

如果顾客是VIP，则他排在队列的VIP部分的末尾。

如果顾客是普通顾客，则他排在整个队列的末尾。

换句话说，我想按照布尔VIP值进行排序，同时保留顾客进来的顺序。

这是我的Order类。

public class Order implements Comparable<Order> {
    private final int customerID;
    private final int amount;
    private final boolean vip_status;

    public Order(int customerID, int amount) { 
        this.customerID = customerID;
        this.amount = amount;
        this.vip_status = customerID < 100 ? true : false;

    }

    @Override
    public int compareTo(Order o) {
        if (vip_status && !o.vip_status) {
            return -1;
        }
        if (!vip_status && o.vip_status)
            return 1;
        return 0;
    }

    public int getCustomerID() {
        return customerID;
    }

    public int getAmount() {
        return amount;
    }

    public boolean isVip_status() {
        return vip_status;
    }
}

这是我填充队列的尝试：

import java.util.PriorityQueue;

public class MyPriorityQueue {
    public static void main(String[] args) {
        PriorityQueue<Order> queue = new PriorityQueue<>();
        Order o1 = new Order(1, 50);
        Order o2 = new Order(5, 30);
        Order o3 = new Order(4, 10);
        Order o4 = new Order(150, 5);
        Order o5 = new Order(2, 5);
        Order o6 = new Order(200, 5);

        queue.add(o1);
        queue.add(o2);
        queue.add(o3);
        queue.add(o4);
        queue.add(o5);
        queue.add(o6);

        while(!queue.isEmpty()){
            Order s = queue.poll();
            System.out.printf("VIP Status: %s CustomerID: %s Amount: %s%n", 
                        s.isVip_status(), s.getCustomerID(), s.getAmount());
        }
    }
}

我得到的结果（是错误的）：

VIP Status: true CustomerID: 1 Amount: 50
VIP Status: true CustomerID: 5 Amount: 30
VIP Status: true CustomerID: 2 Amount: 5
VIP Status: true CustomerID: 4 Amount: 10
VIP Status: false CustomerID: 150 Amount: 5
VIP Status: false CustomerID: 200 Amount: 5

这就是我所期望看到的结果（客户ID 2和4应该按照他们的顺序排列）：

VIP Status: true CustomerID: 1 Amount: 50
VIP Status: true CustomerID: 5 Amount: 30
VIP Status: true CustomerID: 4 Amount: 10
VIP Status: true CustomerID: 2 Amount: 5
VIP Status: false CustomerID: 150 Amount: 5
VIP Status: false CustomerID: 200 Amount: 5

更新：我不想按照除"VIP"之外的任何其他列进行排序。我也不想添加"date"，因为这感觉像是一个hack，而不是真正理解Java的工作原理。

- Vladimir S.

---

将最后一个返回语句从 return 0; 更改为 return Integer.compare(amount, o.amount);。 - Hovercraft Full Of Eels

@HovercraftFullOfEels OP希望顺序是插入队列的顺序，数量似乎只是无关紧要的数据。 - RealSkeptic

@RealSkeptic：你确定吗？看一下上面的预期结果。他似乎想要按金额进行二次排序。 - Hovercraft Full Of Eels

这只是一个小建议，但你按照 VIP 状态进行排序可能不应该是类的自然顺序。它应该在 Comparator 中实现。通常，自然顺序应该考虑所有变量，就像通过 equals 方法一样。可以参考 Comparable 文档以获取更详细的解释。 - Radiodef

我不想添加"date"，因为这感觉像是一个hack。通常订单都有日期，所以这并不是一个hack。另外请参考这里，其中显示了PriorityBlockingQueue的一段摘录，官方推荐类似这样的做法。 - Radiodef

Answer 1

看起来 Java 自带的 PriorityQueue 类在比较两个相等的项时会随意重新排序。这并不是 “Java 的工作方式”，而只是由某个 Java 运行时自带的类的一些特殊行为。

因此，以下方法可能有效：

1.引入一个新的 OrderPlacement 类，其中包含 a）Order 和 b）int 优先级。 2.在你的 PriorityQueue 中添加 OrderPlacement 对象，而不是 Order 对象。 3.当你创建一个新的 OrderPlacement 对象时，通过递增计数器发出一个新的优先级。

然后，您的 OrderPlacement 对象可以具有如下所示的 compareTo() 方法：

@Override
public int compareTo( OrderPlacement o ) 
{
    int d = -Boolean.compare( order.vip_status, o.order.vip_status );
    if( d != 0 )
        return d;
    return Integer.compare( priority, o.priority );
}

- Mike Nakis

---

如果你反转顺序(return -Boolean.compare(...)，那么它会更接近你所需要的。但还不够。这就是为什么我修改了我的答案。 - Mike Nakis

看起来你是对的，关于“如果它们相等，Java可以自由地重新排序项目”。你能在你的答案中强调一下吗？ - Vladimir S.

JavaDocs中甚至有一个例子建议使用这种方法（不是针对PriorityQueue，而是针对相关的PriorityBlockingQueue（使用一个静态的final AtomicLong作为计数器）。 - Hulk

Answer 2

如果您必须使用优先队列来完成操作，下面的代码将解决您的问题。请注意，我使用静态计数器来维护具有相同VIP状态的元素的正确顺序，因为在优先队列中，相等元素以随机顺序维护。这是因为优先队列使用最小/最大堆数据结构，它只关心将最小/最大元素放置在堆的顶部，并不关心相同元素的顺序。

import java.util.PriorityQueue;

public class Order implements Comparable<Order> {
  private final int customerID;
  private final int amount;
  private final int vip_status;
  private final int score;
  private static int counter = 0;

  public Order(int customerID, int amount) {
    this.customerID = customerID;
    this.amount = amount;
    this.vip_status = customerID < 100 ? 0 : 1;
    this.score = counter++;
  }

  @Override
  public String toString() {
    return customerID + " : " + amount + " : " + vip_status;
  }

  @Override
  public int compareTo(Order o) {
    int status = ((Integer) this.vip_status).compareTo(o.vip_status);
    status = status == 0 ? ((Integer) this.score).compareTo(o.score) : status;
    return status;
  }

  public static void main(String[] args) {
    Order o1 = new Order(1000, 100);
    Order o2 = new Order(500, 100);
    Order o3 = new Order(99, 100);
    Order o4 = new Order(10, 100);
    Order o5 = new Order(200, 100);
    Order o6 = new Order(1, 100);

    PriorityQueue<Order> orderQueue = new PriorityQueue<>();
    orderQueue.offer(o1);
    orderQueue.offer(o2);
    orderQueue.offer(o3);
    orderQueue.offer(o4);
    orderQueue.offer(o5);
    orderQueue.offer(o6);

    System.out.println(orderQueue.poll());
    System.out.println(orderQueue.poll());
    System.out.println(orderQueue.poll());
    System.out.println(orderQueue.poll());
    System.out.println(orderQueue.poll());
    System.out.println(orderQueue.poll());
  }
}

`

样例输出：

99 : 100 : 0
10 : 100 : 0
1 : 100 : 0
1000 : 100 : 1
500 : 100 : 1
200 : 100 : 1

注意：您需要知道分数可能最终达到Integer.MAX_VALUE

- Nilesh Rajani

---

将一个额外的字段引入到Order中仅仅为了记住它在队列中的顺序，会污染Order的设计，这是个不好的想法。如果你想要同时将Order添加到两个不同的队列中，并且每个队列中有不同的位置，那该怎么办呢？ 这就是我在答案中建议使用额外类的原因。 - Mike Nakis