الگوی صف اولویت‌دار (Priority Queue) یک الگوی مهم است که برای حل مسائلی که شامل پیدا کردن مقادیر بزرگ‌ترین یا کوچک‌ترین هستند، به کار می‌رود.
در اینجا توضیحات عمیقی در مورد این ساختار داده و پیاده‌سازی متداول آن، یعنی هیپ‌ها (Heaps)، ارائه شده است:
۱. هدف اصلی صف اولویت‌دار
هر زمان که با مسائلی مواجه شدید که عبارت‌هایی مانند “بالاترین K” (Top K)، “K کوچک‌ترین” (K smallest)، یا “K بزرگ‌ترین” (K largest) در عنوان یا توضیحات آن‌ها وجود دارد، همیشه باید از یک صف اولویت‌دار استفاده کنید.
۲. پیاده‌سازی با هیپ‌ها (Heaps)
متداول‌ترین پیاده‌سازی صف‌های اولویت‌دار، ساختار داده‌ای به نام هیپ (Heap) است.
- تعریف هیپ: هیپ نوع خاصی از درخت است که در آن عناصر به شیوه مشخصی سازماندهی می‌شوند.
- مزیت کارایی: دلیل کارایی هیپ‌ها این است که شما همیشه می‌دانید بزرگ‌ترین یا کوچک‌ترین مقدار کجاست: در ریشه (Root).
۳. انواع هیپ‌ها
دو نوع اصلی از هیپ‌ها وجود دارد که برای مدیریت اولویت‌ها استفاده می‌شوند:
| نوع هیپ | تعریف | ویژگی کلیدی |
|---|---|---|
| هیپ مین (Min Heap) | کوچک‌ترین مقدار همیشه در بالا (ریشه) قرار دارد، و هر والد کوچک‌تر از فرزندان خود است. | اجازه دسترسی سریع به کوچک‌ترین عنصر را می‌دهد. |
| هیپ مکس (Max Heap) | بزرگ‌ترین مقدار همیشه در ریشه قرار دارد، و هر والد بزرگ‌تر از فرزندان خود است. | اجازه دسترسی سریع به بزرگ‌ترین عنصر را می‌دهد. |
۴. چگونگی استفاده از هیپ‌ها (اصل متضاد)
چیزی که اغلب ضد شهودی (counterintuitive) است، نحوه استفاده از هیپ‌ها برای یافتن مقادیر K است:
- برای یافتن K بزرگ‌ترین مقادیر، از هیپ مین استفاده می‌کنیم.
- برای یافتن K کوچک‌ترین مقادیر، از هیپ مکس استفاده می‌کنیم.
توضیح دلیل (مثال K کوچک‌ترین):
فرض کنید می‌خواهید سه (K=3) کوچک‌ترین مقدار را در لیستی از هفت عدد پیدا کنید.
- ساخت هیپ: یک هیپ مکس با اندازه ۳ ایجاد می‌کنید.
- پر کردن هیپ: سه مقدار اول (مثلاً ۳، ۶ و ۱) را به هیپ مکس اضافه می‌کنید تا پر شود. (در یک هیپ مکس، بزرگ‌ترین مقدار در ریشه قرار می‌گیرد.)
- بررسی مقدار جدید: هنگامی که به مقدار چهارم برخورد می‌کنید، می‌خواهید بدانید آیا این مقدار باید به مجموعه K کوچک‌ترین اضافه شود یا خیر.
- مقایسه: چون ما به دنبال کوچک‌ترین مقادیر هستیم، تنها چیزی که باید بدانیم این است که آیا مقدار جدید از بزرگ‌ترین مقدار قبلی ما (که همان ریشه هیپ مکس است) کوچک‌تر است.
- عملیات: اگر مقدار جدید کوچک‌تر باشد، مقدار ریشه (بزرگ‌ترین مقدار فعلی در هیپ) را حذف می‌کنیم و مقدار جدید را اضافه می‌نماییم.
این روند تضمین می‌کند که هیپ مکس همیشه شامل K کوچک‌ترین مقداری است که تا آن لحظه دیده‌ایم. منطق مشابه و معکوسی برای استفاده از هیپ مین برای یافتن K بزرگ‌ترین مقادیر به کار می‌رود.
۵. کارایی عملیات هیپ
هیپ‌ها به دلیل کارایی عملیات خود، انتخابی عالی هستند:
- دسترسی به عنصر ماکس/مین: هیپ‌ها امکان دسترسی کارآمد به کوچک‌ترین یا بزرگ‌ترین عنصر (در ریشه) را در زمان $O(1)$ فراهم می‌کنند.
- ورود/حذف عنصر: درج یا حذف عناصر در هیپ‌ها تنها $O(\log n)$ زمان می‌برد.
این کارایی بسیار بهتر از این است که مجبور باشید هر عنصر در یک لیست را پیمایش کنید.
صف اولویت‌دار (پیاده‌سازی شده با هیپ) مانند یک نگهبان امنیتی است که به او گفته شده است فقط K فرد مهم (کوچک‌ترین یا بزرگ‌ترین) را نگه دارد. نگهبان برای اطمینان از اینکه تنها مهم‌ترین افراد را نگه داشته است، به سرعت (در زمان ثابت) می‌تواند تشخیص دهد که آیا فرد جدیدی که می‌آید مهم‌تر از بی‌اهمیت‌ترین فرد فعلی در داخل مجموعه است یا خیر، و اگر چنین باشد، فرد بی‌اهمیت را خارج و فرد مهم جدید را جایگزین می‌کند.