为一系列具有较高优先级的元素和其他具有较低优先级的元素排序优先级队列

Question

我有一个包含以下字段的实体 class：id、orderNo。每个实体必须存储在 java 优先级队列中。元素 id 在 1 - 3000 之间的具有更高的优先级，必须存储在 id > 3000 的元素之上的 orderNo 的升序。元素 ids > 3000的按照orderNo升序存储在更高优先级的元素（ID 为 1 - 3000）。

例如：

(1st insertion to queue: id=4000 orderNo=1) 
(2nd insertion to queue: id=5000 orderNo=2) 
(3rd insertion to queue: id=100  orderNo=3)
(4th insertion to queue: id=50   orderNo=4)

预期排序顺序：

(id=100  orderNo=3) 
(id=50   orderNo=4) 
(id=4000 orderNo=1) 
(id=5000 orderNo=2)

订单实体class：

public class OrderEntity implements Comparable<OrderEntity> {
    private int id;
    private int getOrderNo;

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public int getOrderNo() {
        return getOrderNo;
    }

    public void setOrderNo(int getOrderNo) {
        this.getOrderNo = getOrderNo;
    }

    @Override
    public int compareTo(OrderEntity arg0) {
        if ((this.getId() >= 1 && this.getId() <= 3000) && (arg0.getId() >= 1 && arg0.getId() <= 3000)) {
            if (this.getOrderNo() > arg0.getOrderNo()) {
                return 1;
            } else {
                return 0;
            }
        } else if ((this.getId() <= 3000) && (arg0.getId() > 3000)) {
            return 1;
        } else if ((this.getId() > 3000) && (arg0.getId() <= 3000)) {
            return 1;
        } else if ((this.getId() > 3000) && (arg0.getId() > 3000)) {
            if (this.getOrderNo() > arg0.getOrderNo()) {
                return 1;
            } else {
                return 0;
            }
        } else {
            return 0;
        }
    }
}

订单处理器class:

public class OrderProcessor {
    private static int count;
    static Queue<OrderEntity> pq = new PriorityQueue<>();

    public String createOrder(int id) {
        OrderEntity orderEntity = new OrderEntity();
        orderEntity.setId(id);
        count = count + 1;
        orderEntity.setOrderNo(count);
        pq.add(orderEntity);

        String res = "";
        for (OrderEntity rd : pq) {
            res = res + rd.getId() + " " + rd.getOrderNo() + "\n";
        }
        return res.trim();
    }
}

Answer 1

在这种情况下，对象的自然顺序与您的特殊要求不同，最好不要使用 Comparable，因为它将来可能有其他用途。因此，剩下的解决方案是使用 Comparator，它非常适合您的问题，因为您的 OrderEntity class 不会依赖于此特殊比较。以下是显示解决方案的示例代码：

import java.util.Comparator;
import java.util.PriorityQueue;

public class OrderProcessor {
    public static void main(String[] args) {
        PriorityQueue<OrderEntity> q = new PriorityQueue<>(new OrderEntityComparator());
        q.add(new OrderEntity(4000, 1));
        q.add(new OrderEntity(5000, 2));
        q.add(new OrderEntity(100, 3));
        q.add(new OrderEntity(50, 4));

        while(!q.isEmpty())
            System.out.println(q.poll());
    }

    public static class OrderEntityComparator implements Comparator<OrderEntity> {

        @Override
        public int compare(OrderEntity o1, OrderEntity o2) {
            if(o1.getId() <= 3000 && o2.getId() <= 3000)
                return Integer.compare(o1.getOrderNo(), o2.getOrderNo());
            if(o1.getId() > 3000 && o2.getId() > 3000)
                return Integer.compare(o1.getOrderNo(), o2.getOrderNo());
            if(o1.getId() <= 3000 && o2.getId() > 3000)
                return -1;
            return 1;
        }
    }

    public static class OrderEntity {
        private int id;
        private int orderNo;

        public OrderEntity(int id, int orderNo) {
            this.id = id;
            this.orderNo = orderNo;
        }

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public int getOrderNo() {
            return orderNo;
        }

        public void setOrderNo(int orderNo) {
            this.orderNo = orderNo;
        }

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

已编辑：

如果您不想通过调用 poll 方法删除元素，您必须对数组或列表中的元素进行排序，如下所示：

    OrderEntity[] a = new OrderEntity[q.size()];
    q.toArray(a);
    Arrays.sort(a, new OrderEntityComparator());

    for(OrderEntity entity : a)
        System.out.println(entity);

事实上，在这种情况下，您不需要使用 PriorityQueue，只需对列表或数组进行简单排序即可。

Answer 2

这是一个使用 Java 8 的解决方案，不需要任何复杂的比较器实现。我运行它反对你提供的两个例子。诀窍是要意识到有 2 组 id，<= 3000 和以上。如果你能以某种方式规范化这两个组中的数字，那么你可以简单地使用规范化 ID 的自然排序，然后按订单号自然排序。

public class Main {
    private static Comparator<OrderEntity> orderEntityComparator =
        Comparator.<OrderEntity, Integer>comparing(OrderEntity::getId,
                comparingInt(id -> id / 3000)
        )
                .thenComparingInt(OrderEntity::getOrderNo);

    public static void main(String[] args) {
        PriorityQueue<OrderEntity> queue = new PriorityQueue<>(orderEntityComparator);
        queue.add(new OrderEntity(4000, 1));
        queue.add(new OrderEntity(5000, 2));
        queue.add(new OrderEntity(100, 3));
        queue.add(new OrderEntity(50, 4));

        // 100, 50, 4000, 5000

        queue.clear();

        queue.add(new OrderEntity(100, 1));
        queue.add(new OrderEntity(200, 2));
        queue.add(new OrderEntity(4000, 3));
        queue.add(new OrderEntity(300, 4));

        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
        // 100, 200, 300, 4000
    }

    static class OrderEntity {
        private int id;
        private int orderNo;

        public OrderEntity(int id, int orderNo) {
            this.id = id;
            this.orderNo = orderNo;
        }

        public int getId() {
            return id;
        }

        public int getOrderNo() {
            return orderNo;
        }

        @Override
        public String toString() {
            return String.format("(id=%d, orderNo=%d)", id, orderNo);
        }
    }
}

为一系列具有较高优先级的元素和其他具有较低优先级的元素排序优先级队列

Sorting priority queue for a range of elements with higher priority and other elements with lower priority

java

sorting

priority-queue

comparable

comparator