صف اولویتدار
صف اولویتدار (به انگلیسی: Priority Queue) از جمله ساختمانهای داده بسیار پرکاربرد است.
در صف عادی از روش خروج به ترتیب ورود (FIFO) استفاده میشود. در این تکنیک مثل یک صف نانوایی دادهها به ترتیب ورود پشت سر هم در صف قرار میگیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود.
اما در صف اولویتدار برای هر داده اولویتی - نه لزوما منحصر بفرد - مشخص میشود. صف اولویت را میتوان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستمعامل کامپیوتر هم برای مدیریت پردازشها از صفهای اولویت استفاده میکند. در این نوع داده ساختار، ۳ دستور زیر وجود دارد:
۱.درج همراه با در نظر گرفتن اولویت (به انگلیسی: InsertWithPriority)
۲.حذف عنصر با بالاترین الویت و برگرداندن آن (به انگلیسی: GetNext)
۳.پیدا کردن عنصر با بالاترین اولویت (به انگلیسی: PeekAtNext)
محتویات |
شباهت با صف معمولی (بدون اولویت)[ویرایش]
صف الویت دار همانند صف معمولی است با این تفاوت که در هنگام خروج، عنصری که بالاترین الویت را دارد، از لیستمان خارج میگردد. صف معمولی حالت خاصی از صف الویت دار است که در آن عنصری که در اول لیست است، بالاترین الویت را داراست.
ساختن درخت Heap[ویرایش]
ساختن یک درخت heap در واقع وارد کردن متوالی گرهها در آن است. برای وارد کردن یک گره به درخت heap، طی دو مرحله به صورت زیر عمل میکنیم:
1- گره مفروض را در محلی از درخت که شرط کامل بودن آن به هم نخورد (بدون در نظر گرفتن شرط max-heap یا min-heap بودن) درج میکنیم.
2- اگر گره مذکور بر اساس موقعیت خود در درخت، شرط max-heap یا min-heap بودن را نقض نکند، نیاز به انجام کاری نیست و عملیات درج تمام شده است. در غیر اینصورت، با جابجا کردن گره با والد خود، درخت جدیدی حاصل میشود که باید مرحله 2 در مورد آن تکرار شود.
پیادهسازی صف اولویتدار[ویرایش]
برای پیاده سازی صف اولویتدار عموما از آرایه استفاده میشود. ما در اینجا سه روش مختلف را شرح میدهیم.
پیاده سازی با استفاده از آرایه نامرتب[ویرایش]
در این روش زمانی که دادهای وارد صف میشود همچون صف عادی در انتهای آن قرار میگیرد. به عنوان نمونه دادههای مثال زمانبندی 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ویکیپدیای انگلیسی
