// 第 8 周 – 优先队列：用无序数组的简单实现，以及内置的 PriorityQueue
// 运行：java PriorityQueueDemo.java
import java.util.ArrayList;
import java.util.PriorityQueue;

public class PriorityQueueDemo {

    record Task(String name, int priority) {
        public String toString() { return name + "(" + priority + ")"; }
    }

    // 无序数组：在末尾插入 O(1)，取出时查找最小的优先级 O(n)。
    // （用有序数组时正好相反：插入 O(n)，取出 O(1)。用堆时两者都是 O(log n) – 第 15 周。）
    static class SimplePQ {
        private final ArrayList<Task> items = new ArrayList<>();

        void insert(Task t) { items.add(t); }

        Task removeMin() {
            int min = 0;
            for (int i = 1; i < items.size(); i++)
                if (items.get(i).priority() < items.get(min).priority()) min = i;
            Task t = items.get(min);
            items.set(min, items.get(items.size() - 1)); // 把最后一个元素放到它的位置 – O(1)
            items.remove(items.size() - 1);
            return t;
        }

        boolean isEmpty() { return items.isEmpty(); }
    }

    public static void main(String[] args) {
        Task[] tasks = { new Task("e-mail", 3), new Task("server down", 1), new Task("coffee", 5),
                new Task("prepare lecture", 2), new Task("lunch", 4) };

        SimplePQ pq = new SimplePQ();
        for (Task t : tasks) pq.insert(t);
        System.out.print("SimplePQ order:      ");
        while (!pq.isEmpty()) System.out.print(pq.removeMin() + " ");
        System.out.println();

        // 内置：基于堆，插入和取出 O(log n)
        PriorityQueue<Task> jpq = new PriorityQueue<>((a, b) -> Integer.compare(a.priority(), b.priority()));
        for (Task t : tasks) jpq.offer(t);
        System.out.print("PriorityQueue order: ");
        while (!jpq.isEmpty()) System.out.print(jpq.poll() + " ");
        System.out.println();
    }
}