آموزش برنامه نویسی

PriorityQueue

کلاس PriorityQueue یک صف اولویت را با استفاده از ساختمان داده Min-Heap پیاده سازی می کند ، لذا در کاربرد هایی که نیاز داریم به صورت پیوسته به عنصر کمینه دستیابی داشته باشیم مفید واقع می شود ، برای نمونه می توان به پیاده سازی الگوریتم مرتب سازی Heap Sort اشاره کرد. به صورت پیش فرض این کلاس از ترتیب طبیعی (الفبایی) پیروی می کند مگر آنکه در سازنده آن از یک Comparator اختصاصی برای تعریف نوع خاصی از ترتیب استفاده کنیم. به دلیل استفاده از ساختار Min-Heap بیشتر عملیات این کلاس مانند offer ، poll و … در زمانی لگاریتمی یا حتی ثابت انجام می شوند ، به عبارت دیگر این عملیات بسیار سریع انجام می شوند. این کلاس از طریق مسیر java.util.PriorityQueue قابل دستیابی است.

برای ساخت شی جدید از این کلاس می توانیم از یکی از سازنده های زیر استفاده کنیم :

PriorityQueue()

یک صف اولویت خالی ایجاد می کند.

PriorityQueue(Collection c)

یک صف اولویت جدید ایجاد می کند و اعضای کالکشن c را به آن اضافه می کند.

PriorityQueue(int capacity)

یک صف اولویت جدید ایجاد می کند ، چون کلاس PriorityQueue به صورت Min Heap پیاده سازی می شود برای ابتدای کار یک آرایه برای آن در نظر گرفته می شود که پارامتر capacity اندازه این آرایه را مشخص می کند البته در عین کار ممکن است اندازه آرایه افزایش یابد.

PriorityQueue(int capacity,Comparator cmp)

مشابه سازنده قبلی است با این تفاوت که در اینجا برای مقایسه اشیای داخل صف اولویت از یک Comparator اختصاصی استفاده می کنیم.

PriorityQueue(PriorityQueue other)

یک صف اولویت جدید ایجاد می کند و اعضای یک صف اولویت دیگر را به آن اضافه می کند.

PriorityQueue(SortedSet ss)

یک صف اولویت جدید ایجاد می کند و اعضای یک مجموعه مرتب را به آن اضافه می کند. متد های مهم کلاس PriorityQueue در جدول زیر آمده اند :

ابتدا با یک مثال ساده با PriorityQueue آشنا می شویم.

   1: import java.util.PriorityQueue;
   2: 
   3: public class PriorityQueueDemo 
   4: {
   5:     public static void main(String[] args) 
   6:     {
   7:         PriorityQueue priorityqueue = new PriorityQueue();
   8: 
   9:         priorityqueue.add(1);
  10:         priorityqueue.add(10);
  11:         priorityqueue.add(2);
  12:         priorityqueue.add(9);
  13:         priorityqueue.add(5);
  14: 
  15:         System.out.println(priorityqueue);
  16: 
  17:         System.out.println(priorityqueue.peek());
  18: 
  19:         System.out.println(priorityqueue);
  20: 
  21:         System.out.println(priorityqueue.poll());
  22: 
  23:         System.out.println(priorityqueue);
  24:     }
  25: }

[1, 5, 2, 10, 9]
1
[1, 5, 2, 10, 9]
1
[2, 5, 9, 10]

در کد بالا ابتدا یک PriorityQueue ایجاد می کنیم و سپس اعضایی را به آن اضافه می کنیم و در نهایت آن را چاپ می کنیم(15-7). مشاهده می کنیم که اعضای داخل آن دارای نظم قابل تشخیصی نیستند فقط عنصر ابتدای لیست کمینه است. سپس با استفاده از متد ()peek کوچکترین عنصر را به دست آورده و چاپ می کنیم و سپس لیست را چاپ می کنیم(19-17). مشاهده می کنیم که استفاده از متد ()peek تغییری در صف اولویت ایجاد نمی کند. سپس با استفاده از متد ()poll کوچکترین عنصر را به دست آورده، آن را چاپ می کنیم و بعد از آن کل لیست را چاپ می کنیم. مشاهده می کنیم که متد ()poll عنصر کمینه را از لیست حذف کرده است و در لیست جدید مجدداً کوچکترین عنصر در ابتدای لیست قرار دارد.

مرتب سازی Heap Sort

در این مثال به سادگی الگوریتم مرتب سازی Heap Sort را با استفاده از PriorityQueue پیاده سازی می کنیم.

import java.util.LinkedList;
import java.util.PriorityQueue;

public class PriorityQueueDemo 
{
    public static void main(String[] args) 
    {
        PriorityQueue priorityqueue = new PriorityQueue();
        LinkedList result = new LinkedList();

        priorityqueue.add(1);
        priorityqueue.add(10);
        priorityqueue.add(2);
        priorityqueue.add(9);
        priorityqueue.add(5);
        priorityqueue.add(18);

        while (!priorityqueue.isEmpty())
        {
            result.add(priorityqueue.poll());
        }

        System.out.println(result);
    }
}

[1, 2, 5, 9, 10, 18]

در کد بالا ابتدا یک PriorityQueue و یک LinkedList خالی ایجاد می کنیم ، سپس اعضای نامرتبی را به PriorityQueue اضافه می کنیم . در ادامه در داخل یک حلقه while تا زمانی که PriorityQueue خالی نشده است عنصر کمینه آن را حذف می کنیم و به LinkedList اضافه می کنیم لذا در هر مرحله کوچکترین عضو از صف اولویت خارج شده و به لیست پیوندی اضافه می شود و در نتیجه لیست پیوندی در نهایت مرتب خواهد بود.

ترتیب معکوس

اگر بخواهیم صف اولویت به صورت معکوس نگه داری شود یعنی عنصر ابتدای لیست بزرگترین آیتم آن باشد (به عبارتی به صورت Max Heap پیاده سازی شود) می توانیم از ()Collections.reverseOrder به عنوان Comparator اختصاصی استفاده کنیم. در این صورت متد های ()peek و ()poll عنصر بیشینه را بر می گرداند. مثال قبل را با این نکته بازنویسی می کنیم :

import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class PriorityQueueDemo 
{
    public static void main(String[] args) 
    {
        PriorityQueue priorityqueue = new PriorityQueue(Collections.reverseOrder());
        LinkedList result = new LinkedList();

        priorityqueue.add(1);
        priorityqueue.add(10);
        priorityqueue.add(2);
        priorityqueue.add(9);
        priorityqueue.add(5);
        priorityqueue.add(18);

        while (!priorityqueue.isEmpty()) 
        {
            result.add(priorityqueue.poll());
        }

        System.out.println(result);
    }
}

[18, 10, 9, 5, 2, 1]