按优先级和时间进行多字段排序的队列

Question

意图

实现一个任务队列，排序基于 1) 优先级和 2) 时间，特别是任务创建或时间戳（未插入队列）的时间，优先考虑时间戳较早的任务。

尝试过

这是我目前得到的；比我想象的要简单得多，因为它需要的不仅仅是一个 PriorityQueue。在比较器中，如果两个优先级相等，则在 Task.time 上进行另一个比较，否则，只根据 Task.priority.

进行比较

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

public class QueueWithPriorityAndTimeSort {
   enum TaskPriority {
      High, Medium, Low
   }

   class Task implements Comparable<Task> {   
      long time;
      TaskPriority priority;

      Task(TaskPriority p, long t) {      
         time = t;
         priority = p;
      }

      public int compareTo(Task task2) {
         return priority.compareTo(task2.priority);
      }
   }

   class HighPriorityWithTimeComparator implements Comparator<Task> {
      public int compare(Task task1, Task task2) {
         int compareResult = task1.compareTo(task2);
         if( compareResult == 0){           
            //same priority, now compare on time
            if( task2.time < task1.time)
               compareResult = 1;
            else 
               compareResult = -1;
         }                          
         return compareResult;
      }
   }

   public void buildAndTestQueue(){
      PriorityQueue<Task> queue = 
            new PriorityQueue<Task>(3, new HighPriorityWithTimeComparator());
      queue.add(new Task(TaskPriority.High, 9));
      queue.add(new Task(TaskPriority.Low, 7));
      queue.add(new Task(TaskPriority.Low, 3));
      queue.add(new Task(TaskPriority.High, 2));
      queue.add(new Task(TaskPriority.Medium, 5));
      queue.add(new Task(TaskPriority.Medium, 4));
      queue.add(new Task(TaskPriority.High, 6));
      queue.add(new Task(TaskPriority.High, 8));
      queue.add(new Task(TaskPriority.Low, 15));
      queue.add(new Task(TaskPriority.Low, 10));

      Task m = null;
      while ((m = queue.poll()) != null)
         System.out.println(
            String.format("Priority: %s, %d", m.priority, m.time));     
   }

   public static void main(String args[]) {
      QueueWithPriorityAndTimeSort queueTest = 
         new QueueWithPriorityAndTimeSort();
      queueTest.buildAndTestQueue();
   }
}

问题

这是一种有效的方法吗？我不相信添加的比较器逻辑会改变时间复杂度；除此之外，我没有看到任何明显的问题。

Answer 1

我的回答将解决您发表的以下评论：

Separating these concerns allows sorting based on specific needs for increased flexibility

有更好的方法来分离关注点并使您的代码更加灵活，这样您就可以在不更改代码的情况下更改排序策略。听起来很令人兴奋？

让我们首先定义一个 Comparator 来比较优先级：

class HighPriorityComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            return task1.priority.compareTo(task2.priority);
        }
    }

让我们定义一个 Comparator 来比较时间：

class TimeComparator implements Comparator<Task> {
        public int compare(Task task1, Task task2) {
            int compareResult = 0;
            if (task2.time < task1.time)
                compareResult = 1;
            else
                compareResult = -1;

            return compareResult;
        }
    }

现在是最精彩的部分。让我们定义一个比较器，它允许您混合和匹配比较逻辑。

class MixAndMatchComparator implements Comparator<Task> {

        List<Comparator<Task>> comparators;

        public MixAndMatchComparator(List<Comparator<Task>> comparators) {
            this.comparators=comparators;
        }

        @Override
        public int compare(Task o1, Task o2) {
            int compareResult = 0;
            for(Comparator<Task> comparator : comparators) {
                if(comparator.compare(o1, o2)!=0) {
                    return comparator.compare(o1, o2);
                }
            }
            return compareResult;
        }

    }

现在让我们按优先级排序，如果优先级相等，则按时间排序：

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on priority            
comparators.add(new HighPriorityComparator());
//then on time
comparators.add(new TimeComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);

等等！你改变主意了吗？您现在想要按时间排序，如果时间相等，则按优先级排序？只需更改将竞争者添加到列表中的顺序即可：

List<Comparator<Task>> comparators = new ArrayList<Comparator<Task>>();
//first sort on time    
comparators.add(new TimeComparator());
//then on priority
comparators.add(new HighPriorityComparator());
MixAndMatchComparator orComparator = new MixAndMatchComparator(comparators);
PriorityQueue<Task> queue = new PriorityQueue<Task>(3, orComparator);

按优先级和时间进行多字段排序的队列

Queue with multi-field sorting on priority and time

java

queue

priority-queue

意图

尝试过

问题