صف اولویتدار
صف اولویتدار (به انگلیسی: Priority Queue) از جمله ساختمان‌های داده بسیار پرکاربرد است.
در صف عادی از روش خروج به ترتیب ورود (FIFO) استفاده می‌شود. در این تکنیک مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند؛ بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود.
اما در صف اولویتدار برای هر داده اولویتی - نه لزوماً منحصربه‌فرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم‌عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت استفاده می‌کند.
عملیات‌ها
[ویرایش]صف‌های اولویت حداقل از ۲ عملیات زیر پشتیبانی می‌کنند:[۱]
- درج همراه با در نظر گرفتن اولویت (به انگلیسی: insert_with_priority)
- حذف عنصر با بالاترین اولویت و برگرداندن آن (به انگلیسی: pull_highest_priority_element)
عملیات زیر هم با توجه به کاربردهای فراوانی که دارد اغلب اوقات پیاده‌سازی می‌شود:
پیدا کردن عنصر با بالاترین اولویت (به انگلیسی: PeekAtNext)
در پیاده‌سازی‌های پیشرفته تر مربوط به این ساختار عملیات‌های زیر نیز می‌توانند وجود داشته باشند:
- حذف عنصر با پایین‌ترین اولویت (به انگلیسی: pull_lowest_priority_element)
- پاکسازی صف (به انگلیسی: clear)
- ترکیب ۲ صف اولویت (به انگلیسی: merge)
- افزایش اولویت یک عنصر (به انگلیسی: increment_priority)
- و...
شباهت با صف معمولی (بدون اولویت)
[ویرایش]صف اولویت دار همانند صف معمولی است با این تفاوت که در هنگام خروج، عنصری که بالاترین اولویت را دارد، از لیستمان خارج می‌گردد.
صف معمولی حالت خاصی از صف اولویتدار است که در آن اولویت عناصر به‌ترتیب اضافه شدنشان کاهش پیدا می‌کند پس عنصری که در اول لیست است، بالاترین اولویت را داراست.
ساختن درخت Heap
[ویرایش]ساختن یک درخت heap در واقع وارد کردن متوالی گره‌ها در آن است. برای وارد کردن یک گره به درخت heap، طی دو مرحله به صورت زیر عمل می‌کنیم:
۱- گره مفروض را در محلی از درخت که شرط کامل بودن آن به هم نخورد (بدون در نظر گرفتن شرط max-heap یا min-heap بودن) درج می‌کنیم.
۲- اگر گره مذکور بر اساس موقعیت خود در درخت، شرط max-heap یا min-heap بودن را نقض نکند، نیاز به انجام کاری نیست و عملیات درج تمام شده‌است. در غیر اینصورت، با جابجا کردن گره با والد خود، درخت جدیدی حاصل می‌شود که باید مرحله ۲ در مورد آن تکرار شود.
پیاده‌سازی صف اولویتدار
[ویرایش]برای پیاده‌سازی صف اولویتدار عموماً از آرایه استفاده می‌شود. ما در اینجا سه روش مختلف را شرح می‌دهیم.
پیاده‌سازی با استفاده از آرایه نامرتب
[ویرایش]در این روش زمانی که داده‌ای وارد صف می‌شود همچون صف عادی در انتهای آن قرار می‌گیرد. به عنوان نمونه داده‌های مثال زمانبندی CPU به صورت زیر در آرایه قرار می‌گیرند:
شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶
الویت: ۴ ۲ ۱ ۳ ۵ ۴
درج و حذف یک عنصر در این روش، از نظر زمانی به ترتیب (۱)O و (O(n است.
توجه داشته باشید که هر عنصر آرایه ساختمانی مرکب از دو عنصر شماره پردازش و اولویت آن است. هر پردازش جدید به انتهای صف اضافه می‌شود، که از مرتبه (O (۱ است.
اما زمانی که قرار است پردازشی از آن خارج شود باید تک تک عناصر بررسی شوند، تا پردازشی با بیشترین اولویت انتخاب شود. این فرایند از مرتبه (O (n است.
پیاده‌سازی با استفاده از آرایه مرتب
[ویرایش]در این روش بر خلاف روش قبلی آرایه بر اساس اولویت‌ها مرتب شده‌است.
شماره پردازش:۵ ۶ ۱ ۷ ۴ ۲ ۳
الویت:۵ ۴ ۴ ۳ ۳ ۲ ۱
شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶ ۷
الویت:۴ ۲ ۱ ۳ ۵ ۴ ۳
زمانی که داده‌ای وارد صف می‌شود، بر اساس اولویت خود در محل مناسب قرار می‌گیرد.
در این حالت پردازش با بیشترین اولویت همواره در انتهای صف قرار دارد و هزینه استخراج آن (O (۱ است. این مسئله در مقایسه با آرایه نامرتب یک برتری است. اما در این روش هزینه درج (O(n است که در مقایسه با روش قبلی اصلاً بهینه نیست.
در کل می‌توان گفت روش آرایه مرتب و نامرتب هم ارز یکدیگر بوده و از لحاظ عملکرد تفاوت چندانی با هم ندارند.
درج و حذف یک عنصر در این روش، از نظر زمانی به ترتیب (O(n و (۱)O است.
پیاده‌سازی با استفاده از آرایه نیمه مرتب (درخت heap)
[ویرایش]در این درخت heap، داده‌ها را بر اساس اولویت آن‌ها در یک درخت مکس-هیپ همانند شکل وارد می‌کنیم.
اعداد داخل گره‌ها اولویت و اعداد خارجی شماره پردازش هستند. درخت فوق در نمایش آرایه‌ای به صورت شکل نشان داده شده، خواهد شد.
در یک درخت min-heap عنصری با کوچکترین کلید همواره در ریشه قرار دارد (چرا!؟). در نتیجه عمل حذف گره ریشه از درخت min-heap کوچکترین عنصر آن را به ما می‌دهد. این عمل از مرتبه (O (logn است. عمل درج در min-heap هم همان‌طور که می‌دانید از همین مرتبه‌است.
مقایسه ۳ روش پیاده‌سازی صف اولویتدار
[ویرایش]عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد روی هم رفته از مرتبه (O (n است. اما در روش آرایه نیمه مرتب این مرتبه به (O (logn کاهش می‌یابد. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارایی بسیار بهتری دارد.
ارتباط صف اولویتدار با الگوریتم‌های مرتب‌سازی
[ویرایش]هنگامی که عناصر را در یک صف اولویتدار که با استفاده از آرایه مرتب پیاده‌سازی شده است، درج کنیم و پس از آن یکی یکی آن‌ها را از لیست حذف کنیم؛ عناصر به صورت مرتب شده قرار می‌گیرند. این روشی است که در چندین الگوریتم مرتب‌سازی به کار می‌رود:
- مرتب‌سازی انبوه(به انگلیسی: مرتب‌سازی هرمی): اگر صف اولویت دار به شیوهٔ آرایه نیمه مرتب پیاده‌سازی شده باشد.
- مرتب‌سازی انتخابی(به انگلیسی: SelectionSort): اگر صف اولویت دار به شیوهٔ آرایه نامرتب پیاده‌سازی شده باشد.
- مرتب‌سازی درجی(به انگلیسی: InsertionSort): صف اولویت دار به شیوهٔ آرایه مرتب شده پیاده‌سازی شده باشد.
پیوند به بیرون
[ویرایش]- Descriptions by Lee Killough
- Survey of known priority queue structures by Stefan Xenos
- UC Berkeley - Computer Science 61B - Lecture 24: Priority Queues (video) - introduction to priority queues using binary heap
- Double-Ended Priority Queues by Sartaj Sahni
منابع
[ویرایش]http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html
http://en.wikipedia.org/wiki/Priority_queueویکی‌پدیای انگلیسی