کالکشن ها در جاوا: استفاده از صف اولویتی (PriorityQueue)

کالکشن ها در جاوا: استفاده از صف اولویتی (PriorityQueue)

معرفی صف اولویتی (PriorityQueue)

در موضوع صف (Queue) گفتیم اولین عنصری که به صف اضافه میکنیم، اولین عنصریه که میتونیم صدا بزنیم یا حذف کنیم و صف first-in-first-out است.

در جاوا یک پیاده سازی از صف داریم به نام صف اولویتی (PriorityQueue)؛ در Queue عناصر به ترتیبی که اضافه میشن، در صف قرار میگیرن؛ اما در PriorityQueue عناصر بر اساس مقایسه ای که باهمدیگه میشن در صف قرار می گیرن و این مقایسه به طور پیشفرض با Comparable انجام میشه اما میتونیم با استفاده از اینترفیس Comparator عناصر رو اونطوری که میخوایم باهم مقایسه کنیم.

استفاده از صف اولویتی (PriorityQueue)

صف اولویتی (PriorityQueue) یک کلاس است و میتونیم مستقیم ازش استفاده کنیم؛ اینترفیس Queue در کلاس PriorityQueue پیاده‌سازی شده است؛ در UML زیر سلسله مراتب ارث‌بری صف اولویتی (PriorityQueue) شرح داده شده است.

سلسله مراتب ارث‌بری صف اولویتی (PriorityQueue) در جاوا
سلسله مراتب ارث‌بری صف اولویتی (PriorityQueue) در جاوا

در نمودار UML زیر کانستراکتور (سازنده) های کلاس PriorityQueue با توضیحاتشون آورده شده است.

java.util.PriorityQueue
+PriorityQueue() یک نمونه از PriorityQueue ایجاد میکنه.
+PriorityQueue(initialCapacity: int) یک نمونه از PriorityQueue با ظرفیت اولیه ایجاد میکنه.
+PriorityQueue(c: Collection<? extends E>) یک نمونه از PriorityQueue ایجاد میکنه و عناصر کالکشن c رو بهش اضافه می کنه.
+PriorityQueue(comparator: Comparator<? super E>) یک نمونه از PriorityQueue ایجاد میکنه و عناصر رو بر اساس مقایسه در Comparator در صف قرار میده.

دوتا String با Comparable به صورت پیشفرض بر اساس اولین حروف مقایسه میشن؛ در مثال زیر میخوایم اسم ها رو بر اساس حروف الفبا در PriorityQueue قرار بدیم.

PriorityQueue<String> priorityQueue = new PriorityQueue<>();
priorityQueue.offer("Tehran");
priorityQueue.offer("Arak");
priorityQueue.offer("Shiraz");
priorityQueue.offer("Qazvin");
priorityQueue.offer("Mashhad");
priorityQueue.offer("Qom");
priorityQueue.offer("Zanjan");
priorityQueue.offer("Zahedan");

while(!priorityQueue.isEmpty())
    System.out.print(priorityQueue.poll() + " ");
        

در مثال زیر میخوایم عناصر String رو بر اساس طولشون در PriorityQueue قرار بدیم.

PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<>() {
    @Override
    public int compare(String o1, String o2) {
        if (o1.length() > o2.length())
            return 1;
        else if (o1.length() < o2.length())
            return -1;
        else 
            return 0;
    }
});

priorityQueue.offer("Tehran");
priorityQueue.offer("Arak");
priorityQueue.offer("Shiraz");
priorityQueue.offer("Qazvin");
priorityQueue.offer("Mashhad");
priorityQueue.offer("Qom");
priorityQueue.offer("Zanjan");
priorityQueue.offer("Zahedan");

while (!priorityQueue.isEmpty())
    System.out.print(priorityQueue.poll() + " ");
        

در مثال بالا برای آشنایی با اینترفیس Comparator به طور کامل پیادش کردیم؛ اینترفیس Comparator یک اینترفیس با یک متد است بنابراین میتونیم به صورت عبارت لامبدا پیادش کنیم.

PriorityQueue<String> priorityQueue = new PriorityQueue<>((o1, o2) -> {
    if (o1.length() > o2.length())
        return 1;
    else if (o1.length() < o2.length())
        return -1;
    else return 0;
});
        

در مثال زیر میخوایم اعداد رو از بزرگ به کوچک داخل PriorityQueue قرار بدیم.

PriorityQueue<Integer> priorityQueue2 = new PriorityQueue<>(Comparator.reverseOrder());
priorityQueue2.offer(42);
priorityQueue2.offer(54);
priorityQueue2.offer(32);
priorityQueue2.offer(71);
priorityQueue2.offer(12);
priorityQueue2.offer(25);
priorityQueue2.offer(62);

while (!priorityQueue2.isEmpty())
    System.out.print(priorityQueue2.poll() + " ");
        

در مثال زیر میخوایم اجرای کار ها توسط سیستم عامل رو شبیه سازی کنیم.

public class TaskManagerDemo {

    public static void main(String[] args) {

        PriorityQueue<Task> tasks = new PriorityQueue<>();

        tasks.offer(new Task(Task.Priority.HIGH, "Power Off");
        tasks.offer(new Task(Task.Priority.HIGH, "Delete File"));
        tasks.offer(new Task(Task.Priority.LOW, "Play Music"));
        tasks.offer(new Task(Task.Priority.MEDIUM, "Run Text Editor"));
        tasks.offer(new Task(Task.Priority.LOW, "Close Browser"));

        while (!tasks.isEmpty())
            tasks.poll().run();

    }

    private static class Task implements Comparable<Task> {

        private final Priority priority;
        private final String name;

        public Task(Priority priority, String name) {
            this.priority = priority;
            this.name = name;
        }

        public Priority getPriority() {
            return priority;
        }

        public void run() {
            System.out.printf("Running task: %-20s" + " Priority Number: %1d\n", name, priority.getPriorityNumber());
        }

        @Override
        public int compareTo(Task t) {
            return Integer.compare(priority.getPriorityNumber(), t.getPriority().getPriorityNumber());
        }

        enum Priority {
            HIGH(1), MEDIUM(2), LOW(3);

            private final int priorityNumber;

            Priority(int priorityNumber) {
                this.priorityNumber = priorityNumber;
            }

            public int getPriorityNumber() {
                return priorityNumber;
            }
        }
    }
}
        

بررسی پیچیدگی زمان در صف اولویتی (PriorityQueue)

در جدول زیر پیچیدگی زمان (Time Complexity) متد های حذف، اضافه و صدا زدن عنصر در PriorityQueue آورده شده است.

PriorityQueue
متد پیچیدگی زمان (TimeComplexity)
offer(E) / add(E) O(logn)
poll(): E / remove(): E O(logn)
peek(): E O(1)

خلاصه

  • در صف اولویتی (PriorityQueue) عناصر بر اساس مقایسه باهمدیگه قرار میگیرن.
  • برای مقایسه ی عناصر در صف اولویتی از اینترفیس Comparable یا Comparator استفاده میکنیم.
  • پیچیدگی زمان برای حذف و اضافه کردن عنصر در PriorityQueue برابر با O(logn) است و برای صدا زدن عناصر O(1) است.

بازخورد و دیدگاه‌ ها

اولین نفری باشید که در این صفحه نظر می‌دهید

notifications برای اطلاع از جدیدترین مطالب و پست های مرتبط، عضو کانال تلگرام ما بشید.

arrow_drop_up
کپی شد!