موضوع مقاله: صف اولویت‌دار | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # صف اولویت‌دار | مقدمه: در این تکنیک مثل یک صف نانوایی داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند؛ بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود. | ## بخش 1: صف اولویت‌دار | اما در صف اولویت‌دار برای هر داده اولویتی - نه لزوماً منحصربه‌فرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. عملیات‌ها صف‌های اولویت حداقل از ۲ عملیات زیر پشتیبانی می‌کنند: درج همراه با در نظر گرفتن اولویت حذف عنصر با بالاترین اولویت و برگرداندن آن عملیات زیر هم با توجه به کاربردهای فراوانی که دارد اغلب اوقات پیاده‌سازی می‌شود: پیدا کردن عنصر با بالاترین اولویت در پیاده‌سازی‌های پیشرفته تر مربوط به این ساختار عملیات‌های زیر نیز می‌توانند وجود داشته باشند: حذف عنصر با پایین‌ترین اولویت پاکسازی صف ترکیب ۲ صف اولویت افزایش اولویت یک عنصر و... شباهت با صف معمولی (بدون اولویت) صف اولویت دار همانند صف معمولی است با این تفاوت که در هنگام خروج، عنصری که بالاترین اولویت را دارد، از لیستمان خارج می‌گردد. صف معمولی حالت خاصی از صف اولویت‌دار است که در آن اولویت عناصر به‌ترتیب اضافه شدنشان کاهش پیدا می‌کند پس عنصری که در اول لیست است، بالاترین اولویت را داراست. در غیر اینصورت، با جابجا کردن گره با والد خود، درخت جدیدی حاصل می‌شود که باید مرحله ۲ در مورد آن تکرار شود. پیاده‌سازی صف اولویت‌دار برای پیاده‌سازی صف اولویت‌دار عموماً از آرایه استفاده می‌شود. | ## بخش 2: صف اولویت‌دار | پیاده‌سازی با استفاده از آرایه نامرتب در این روش زمانی که داده‌ای وارد صف می‌شود همچون صف عادی در انتهای آن قرار می‌گیرد. به عنوان نمونه داده‌های مثال زمانبندی CPU به صورت زیر در آرایه قرار می‌گیرند: شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶ الویت: ۴ ۲ ۱ ۳ ۵ ۴ درج و حذف یک عنصر در این روش، از نظر زمانی به ترتیب (۱)O و (O(n است. توجه داشته باشید که هر عنصر آرایه ساختمانی مرکب از دو عنصر شماره پردازش و اولویت آن است. اما زمانی که قرار است پردازشی از آن خارج شود باید تک تک عناصر بررسی شوند، تا پردازشی با بیشترین اولویت انتخاب شود. پیاده‌سازی با استفاده از آرایه مرتب در این روش بر خلاف روش قبلی آرایه بر اساس اولویت‌ها مرتب شده‌است. شماره پردازش:۵ ۶ ۱ ۷ ۴ ۲ ۳ الویت:۵ ۴ ۴ ۳ ۳ ۲ ۱ شماره پردازش: ۱ ۲ ۳ ۴ ۵ ۶ ۷ الویت:۴ ۲ ۱ ۳ ۵ ۴ ۳ زمانی که داده‌ای وارد صف می‌شود، بر اساس اولویت خود در محل مناسب قرار می‌گیرد. در این حالت پردازش با بیشترین اولویت همواره در انتهای صف قرار دارد و هزینه استخراج آن (O (۱ است. | ## بخش 3: صف اولویت‌دار | در کل می‌توان گفت روش آرایه مرتب و نامرتب هم ارز یکدیگر بوده و از لحاظ عملکرد تفاوت چندانی با هم ندارند. پیاده‌سازی با استفاده از آرایه نیمه مرتب (درخت heap) در این درخت heap، داده‌ها را بر اساس اولویت آن‌ها در یک درخت مکس-هیپ همانند شکل وارد می‌کنیم. مقایسه ۳ روش پیاده‌سازی صف اولویت‌دار عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد روی هم رفته از مرتبه (O (n است. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارایی بسیار بهتری دارد. ارتباط صف اولویت‌‌دار با الگوریتم‌های مرتب‌سازی هنگامی که عناصر را در یک صف اولویت‌دار که با استفاده از آرایه مرتب پیاده‌سازی شده است، درج کنیم و پس از آن یکی یکی آن‌ها را از لیست حذف کنیم؛ عناصر به صورت مرتب شده قرار می‌گیرند. | ## جمع‌بندی | این روشی است که در چندین الگوریتم مرتب‌سازی به کار می‌رود: مرتب‌سازی انبوه: اگر صف اولویت دار به شیوهٔ آرایه نیمه مرتب پیاده‌سازی شده باشد.