// 8. hét – Prioritási sor: egyszerű megvalósítás rendezetlen tömbbel, és a beépített PriorityQueue
// Futtatás: 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 + ")"; }
    }

    // Rendezetlen tömb: betétel a végére O(1), kivételnél megkeressük a legkisebb prioritásút O(n).
    // (Rendezett tömbnél fordítva: betétel O(n), kivétel O(1). Kupaccal mindkettő O(log n) – 15. hét.)
    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)); // az utolsót a helyére – 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("szerver leállt", 1), new Task("kávé", 5),
                new Task("óra előkészítése", 2), new Task("ebéd", 4) };

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

        // Beépített: kupacon alapul, insert és remove 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 sorrend: ");
        while (!jpq.isEmpty()) System.out.print(jpq.poll() + " ");
        System.out.println();
    }
}