صف اولویت جاوا: یک صف کلاسیک نیست

در این مقاله یک صف اولویت، کلاس جاوا را یاد می گیریم که رابط Queue را پیاده سازی می کند. یک برنامه نویس از رابط صف معمولی چه می داند؟ اول از همه، این رابط مبتنی بر اصل FIFO یا "اول در اولین خروج" است. این یک صف معمولی را به معنای رایج آن یادآوری می کند. می خواهید از مک درایو قهوه بگیرید؟ اگر ماشین شما اولین نفری است که نزدیک پنجره است، قهوه خود را قبل از راننده بعدی می خورید.

اعلان رابط صف

public interface Queue<E> extends Collection<E>

صف اولویت چیست؟

صف اولویت چیست؟ اول از همه، کلاسی است که در صورت وارد کردن یک عنصر از پشت و حذف یک عنصر از سر، رابط Queue را پیاده سازی می کند. با این حال در داخل یک صف معمولی نیست. ترتیب عناصر صف اولویت جاوا به اولویت عناصر بستگی دارد. عنصر با بالاترین اولویت به سر صف منتقل می شود. اگر بالاترین رتبه را حذف کنید (سرویس کنید)، عنصر دوم به سمت سر می رود تا قهوه اش را بگیرد. اولویت چگونه تعیین می شود؟ طبق مستندات، عناصر صف اولویت بر اساس ترتیب طبیعی آنها یا توسط مقایسه کننده ای که در زمان ساخت صف ارائه می شود، بسته به سازنده ای که استفاده می شود، مرتب می شوند. یک صف اولویت بر اساس یک پشته حداقل اولویت. یعنی در مورد عناصر صف اعداد اولین عنصر صف حداقل این اعداد خواهد بود. اغلب پس از خواندن این تعریف، دانش آموزان تازه کار شروع به فکر می کنند که صف اولویت به معنای خطی مرتب شده است. یعنی اگر مثلاً از صفی استفاده کنیم که عناصر آن اعداد طبیعی هستند، اولین عنصر کوچکترین و آخرین عنصر بزرگترین خواهد بود. این کاملا درست نیست. برای اینکه بفهمید صف اولویت واقعاً چگونه کار می کند و چه چیزی را ارائه می دهد، باید بفهمید که پشته چگونه کار می کند. ساختار داخلی صف اولویت را با استفاده از مثالی کمی بعد در نظر می گیریم. حال بیایید به ویژگی های بیرونی آن بپردازیم.

سازندگان کلاس PriorityQueue و اعلان

کلاس PriorityQueue 6 روش مختلف برای ساخت یک صف اولویت در جاوا ارائه می دهد.

• PriorityQueue () - صف خالی با ظرفیت اولیه پیش فرض (11) که عناصر خود را بر اساس ترتیب طبیعی آنها مرتب می کند.
• PriorityQueue (Collection c) - صف خالی حاوی عناصر موجود در مجموعه مشخص شده.
• PriorityQueue (int initialCapacity) - صف خالی با ظرفیت اولیه مشخص شده که عناصر خود را بر اساس ترتیب طبیعی آنها مرتب می کند.
• PriorityQueue(int initialCapacity، Comparator Comparator) - صف خالی با ظرفیت اولیه مشخص شده که عناصر خود را مطابق با مقایسه کننده مشخص شده مرتب می کند.
• PriorityQueue(PriorityQueue c) - صف خالی حاوی عناصر در صف اولویت مشخص شده.
• PriorityQueue (SortedSet c) - صف خالی حاوی عناصر موجود در مجموعه مرتب شده مشخص شده.

صف اولویت در جاوا به روش زیر اعلام می شود:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

ایجاد PriorityQueue

بیایید یک صف اولویتی از اعداد صحیح ایجاد کنیم. اجرای صف اولویت، کد جاوا:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

ما یک صف اولویت بدون آرگومان ایجاد کرده ایم. در این حالت، سر صف اولویت حداقل تعداد صف است. اگر سر را بردارید، کوچکترین عنصر بعدی این مکان را خواهد گرفت. بنابراین می توانید عناصر را به ترتیب صعودی از صف حذف کنید. در صورت لزوم می توانید اصل سفارش را با استفاده از رابط مقایسه تغییر دهید.

روش های صف اولویت جاوا

کلاس جاوا PriorityQueue روش های مهمی برای افزودن، حذف و بررسی عناصر دارد.

عناصر را در صف اولویت قرار دهید

• add(object) boolean عنصر مشخص شده را در صف اولویت قرار می دهد. در صورت موفقیت واقعی برمی گردد. اگر صف پر باشد، متد یک استثنا ایجاد می کند.
• پیشنهاد (object) boolean عنصر مشخص شده را در این صف اولویت قرار می دهد. اگر صف پر باشد، متد false را برمی گرداند.

می توانید از هر دو عملیات اضافه کردن استفاده کنید، برای اکثر موارد تفاوتی وجود ندارد. در اینجا یک مثال کوچک از شروع و اضافه کردن عناصر به صف اولویت آورده شده است.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

خروجی این است:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

ترتیب المان ها عجیب به نظر می رسد، بعداً توضیح خواهیم داد.

بازیابی و حذف عناصر از صف اولویت

• حذف(شیء) بولی یک نمونه از عنصر مشخص شده را در صورت وجود از این صف حذف می کند.
• Object poll() سر این صف را بازیابی و حذف می کند. اگر صف خالی باشد، null برمی‌گرداند.
• void clear() تمام عناصر را از صف اولویت حذف می کند.
• عنصر شی () سر این صف را بدون حذف آن بازیابی می کند. اگر صف خالی باشد NoSuchElementException را پرتاب می کند .
• Object peek () سر صف را بدون حذف آن بازیابی می کند. اگر صف خالی باشد، null برمی‌گرداند.

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

خروجی:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

همانطور که می بینید، تلاش برای چاپ سر صف خالی با استفاده از متد () element منجر به NoSuchElementexception می شود .

مقایسه کننده صف اولویت

• Comparator comparator() مقایسه کننده ای را برمی گرداند که برای مرتب کردن عناصر در صف استفاده شده است. اگر صف بر اساس ترتیب طبیعی عناصر آن مرتب شده باشد، صفر برمی‌گرداند.

صف اولویت جاوا، مثال با مقایسه کننده

ما از ترتیب طبیعی (صعودی) در مثال های کد بالا استفاده کردیم، اما گاهی اوقات باید آن را تغییر دهیم. در اینجا مثال صف اولویت جاوا است، جایی که ما کلاس مقایسه کننده داخلی خود را ایجاد می کنیم که رابط مقایسه کننده را پیاده سازی می کند. مقایسه کننده ما عناصر را از بزرگترین به کوچکترین مرتب می کند.

import java.util.PriorityQueue;
import java.util.Comparator;
 
class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}
 
class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

خروجی:

the head of Queue = 5
5
4
3
2
1

سر صف اکنون عنصر حداقل نیست، بلکه حداکثر است و ترتیب به معکوس تغییر یافت.

تکرار روی PriorityQueue با استفاده از تکرارکننده

ProrityQueue بخشی از چارچوب مجموعه است و رابط Iterable<> را پیاده سازی می کند . برای تکرار روی عناصر یک صف اولویت، می توانید از متد iterator() استفاده کنید . به عنوان مثال:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;
 
class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

خروجی:

1 2 4 5 3 

روش های PriorityQueue بیشتر

• اگر صف حاوی عنصر o باشد، boolean contain(Object o) true برمی گرداند.
• int size() تعداد عناصر موجود در این صف را برمی گرداند.
• Object[] toArray() یک آرایه حاوی تمام عناصر این صف را برمی گرداند.

به عنوان مثال:

import java.util.PriorityQueue;
import java.util.Queue;
 
public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }
 
       System.out.println("our queue: " + priorityQueue);
 
       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));
 
       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

خروجی:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

تعریف PriorityQueue جاوا 8

اگر اسناد priorityqueue java 8 را باز کنید، تعریف بعدی را در آنجا خواهید یافت: یک صف اولویت نامحدود بر اساس یک پشته اولویت. عناصر صف اولویت بر اساس ترتیب طبیعی آنها یا توسط مقایسه کننده ای که در زمان ساخت صف ارائه می شود، بسته به سازنده ای که استفاده می شود، مرتب می شوند. صف اولویتی اجازه عناصر تهی را نمی دهد. صف اولویت‌بندی متکی به ترتیب طبیعی نیز اجازه درج اشیاء غیرقابل مقایسه را نمی‌دهد (انجام این کار ممکن است منجر به ClassCastException شود). Heap یک کلمه بسیار مهم در اینجا است. ویژگی های ترتیب عناصر صف اولویت را توضیح می دهد.

اصل کار PriorityQueue: Binary Heap

بیایید با یک مثال شروع کنیم. بیایید دو شی ایجاد کنیم که رابط Queue را پیاده سازی می کنند. یکی از آنها LinkedList، دومی PriorityQueue است. هر دوی آنها دارای 5 عنصر عدد صحیح (1،2،3،4 و 5) هستند و ما شروع به قرار دادن عناصر در صف های خود از بزرگترین تا کوچکتر می کنیم. بنابراین، اولی 5 می آید، سپس 4، 3، 2 و آخرین مورد 1 خواهد بود. سپس هر دو لیست را چاپ کنید تا ترتیب را بررسی کنید.

   Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
       System.out.println("PriorityQueue: " + priorityQueue)

نتیجه کار این کدها به صورت زیر است:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

خوب، ترتیب لیست پیوندی قابل پیش بینی و قابل درک است. طبق اصل FIFO سفارش داده شده است. ما با 5 شروع کردیم، بنابراین این عنصر اولین عنصر در ردیف است، سپس 4 می شود و غیره. در مورد ترتیب صف های اولویت دار چه می توانیم بگوییم؟ Docs گفت که عناصر صف اولویت بر اساس ترتیب طبیعی آنها یا توسط یک مقایسه کننده ارائه شده در زمان ساخت صف مرتب می شوند. با این حال به نظر نمی رسد این ترتیب در معنای مرتب سازی خطی "طبیعی" باشد. ما ترجیح می دهیم انتظار [1، 2، 3، 4، 5] را داشته باشیم، نه [1، 2، 4، 5، 3]. برای درک اینکه چرا ترتیب بازیابی مثل قبل است، باید آن صف اولویت را بر اساس یک پشته به خاطر بیاوریم. پشته چیست؟ این یک ساختار داده مبتنی بر درخت باینری است . خاصیت اصلی پشته: اولویت هر یک از والدین از اولویت های فرزندانش بیشتر است. اجازه دهید به شما یادآوری کنم که اگر هر یک از والدین بیش از دو فرزند نداشته باشند، درخت یک باینری کامل نامیده می شود و پر کردن سطوح از بالا به پایین (از همان سطح - از چپ به راست) انجام می شود. هیپ دودویی هر بار که عناصری از آن اضافه یا حذف می شوند، خود را دوباره سازمان می دهد. در مورد min-heap، کوچکترین عنصر بدون توجه به ترتیب درج به ریشه می رود. صف اولویت بر اساس این min-heap. یعنی در مورد عناصر صف اعداد اولین عنصر صف حداقل این اعداد خواهد بود. اگر ریشه را حذف کنید، کوچکترین بعدی تبدیل به روت می شود.

بیایید به مثال خود بپردازیم.

مرحله 1. ما '5' را در صف اولویت قرار می دهیم. ریشه می شود. مرحله 2. ما "4" را به صف اولویت اضافه می کنیم. 4 <5، بنابراین عنصر جدید باید بالاتر از عنصر قدیمی باشد. 4 تبدیل به ریشه می شود، 5 فرزند چپ آن است. اکنون ساختار داده در جاوا [4، 5] مرحله 3 است . ما '3' را اضافه می کنیم. موقتاً فرزند راست ریشه می شود (4). با این حال، 3 < 4، بنابراین ما باید آن را بالا ببریم. 3 و 4 را مبادله کنید. اکنون ساختاری داریم مانند [3، 5، 4] مرحله 4. "2" را اضافه می کنیم. می شود فرزند چپ 5. 2<5، پس آنها را مبادله کنید. 2 تبدیل به فرزند چپ 3، 2 < 3 می شود، بنابراین یک فرآیند مبادله دیگر. اکنون یک ساختار داریم [2،3،4،5] مرحله 5. "1" را اضافه می کنیم. از فرزند راست 3 به فرزند چپ 2 می آید و سپس به سمت ریشه می رود. ساختار داده نتیجه: [1،2،4،5،3] فرآیند حذف از یک ریشه شروع می‌شود و فرآیندهای معکوس را تحریک می‌کند. بنابراین، ابتدا 1 را به عنوان ریشه، سپس 2، 3، 4 و در نهایت 5 داریم. به همین دلیل است که از حذف عملیات poll() استفاده می کنیم.

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

ما در خروجی معنای خطی "مرتب" شده ایم:

1
2
3
4
5

بنابراین صف اولویت می تواند برای برخی از عملیات موثر باشد. برای درج و حذف هر عنصر زمان O(log N) طول می کشد و می توانید حداقل عنصر را در O(1) دریافت کنید. این مثال کامل است:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

درک این نکته مهم است که صف های اولویت بر پایه پشته های باینری هستند، بنابراین آنها عناصر را به ترتیب مرتب شده خطی نگه نمی دارند. هر راهی از ریشه تا برگ سفارش داده می شود، اما راه های مختلف از ریشه چنین نیست. این بدان معناست که می توانید عنصر حداقلی صف را خیلی سریع دریافت کنید.

آنچه باید در مورد صف اولویت بدانید فهرست مختصر

• صف اولویت به اشیاء NULL اجازه نمی دهد.
• شما می توانید فقط اشیاء قابل مقایسه را به PriorityQueue اضافه کنید.
• صف اولویت به عنوان یک پشته کوچک، نوعی درخت دودویی ساخته می شود. عنصر حداقل یک ریشه است. اشیاء صف اولویت به طور پیش فرض به ترتیب طبیعی مرتب می شوند.
• در صورت نیاز به سفارش سفارشی می توانید از Comparator استفاده کنید.
• PriorityQueue امن نیست، بنابراین بهتر است از PriorityBlockingQueue برای کار در یک محیط همزمان استفاده کنید.
• PriorityQueue زمان O(log(n)) را برای متدهای add و poll و O(1) را برای بدست آوردن حداقل عناصر فراهم می کند.