صف اولویت‌دار

آشنایی با صف اولویتی (Priority Queue)، کاربردها و نحوه پیاده‌سازی آن
جستجو:  

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده ورودی، اولین داده خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

به عنوان مثال، فرض کنید پردازش‌های زیر در انتظار اختصاص CPU به خود هستند:

  

جدول درخواست پردازنده

  

صف انتظار CPU یک صف اولویت‌دار است. در نتیجه CPU در اولین فرصت ممکن ابتدا پردازش شماره 3 را انجام می‌دهد. سپس پردازش شماره 2 و ...

تذکر: روش‌های زمان‌بندی CPU جهت انجام پردازش‌های مختلف یکی از بحث‌های جذاب و در عین حال مهم مبحث سیستم عامل است. بررسی تمامی روش‌های زمان‌بندی و مزایا و معایب آنها خارج از بحث فعلی ما است.

برای پیاده‌سازی صف اولویتی عموما از آرایه استفاده می‌شود. من در اینجا سه روش مختلف را شرح می‌دهم.

  

پیاده‌سازی با استفاده از آرایه نامرتب

  [برگرد بالا]

در این روش زمانی که داده‌ای وارد صف می‌شود، همچون صف عادی در انتهای آن قرار می‌گیرد. به عنوان نمونه، داده‌های مثال زمان‌بندی CPU به صورت زیر در آرایه قرار می‌گیرند:

  

\استفاده از آرایه نامرتب برای پیاده سازی صف اولویتی

  

هر عنصر آرایه ساختمانی مرکب از دو عنصر شماره پردازش و اولویت آن است. هر پردازش جدید به انتهای صف اضافه می‌شود که از مرتبه $ O(1)$ است:

  

درج عنصر جدید در صف اولویت‌دار

  

اما زمانی که قرار است پردازشی از آن خارج شود، باید تک تک عناصر بررسی شوند، تا پردازشی با بیشترین اولویت انتخاب شود. این فرآیند از مرتبه $ O(n)$ است.

  

پیاده‌سازی با استفاده از آرایه مرتب

  [برگرد بالا]

در این روش بر خلاف روش قبل، آرایه بر اساس اولویت‌ها مرتب شده است.

  

پیاده‌سازی صف اولویتی با استفاده از آرایه مرتب

  

زمانی که داده‌ای وارد صف می‌شود، بر اساس اولویت خود در محل مناسب قرار می‌گیرد:

  

درج داده در صف اولویتی

  

در این حالت پردازش با بیشترین اولویت همواره در انتهای صف قرار دارد و هزینه استخراج آن $ O(1)$ است. این مسئله در مقایسه با آرایه نامرتب یک برتری است. اما در این روش هزینه درج $ O(n)$ است که در مقایسه با روش قبلی بدتر است.

در کل می‌توان گفت روش آرایه مرتب و نامرتب هم‌ارز یکدیگر بوده و از لحاظ عملکرد تفاوت چندانی با هم ندارند.

  

پیاده‌سازی با استفاده از آرایه نیمه‌مرتب (درخت heap)

  [برگرد بالا]

در این روش داده‌ها بر اساس اولویت آنها در یک درخت min-heap وارد می‌شوند:

  

پیاده‌سازی صف اولویتی با استفاده از درخت heap

  

اعداد داخل گره‌ها اولویت و اعداد خارجی شماره پردازش هستند. درخت فوق در نمایش آرایه‌ای به این صورت خواهد شد:

  

نمایش صف اولویت‌دار با استفاده از آرایه نیمه‌مرتب

  

در یک درخت min-heap عنصری با کوچکترین کلید همواره در ریشه قرار دارد. در نتیجه عمل حذف گره ریشه از درخت min-heap، کوچکترین عنصر آن را به ما می‌دهد. این عمل بر اساس بحث‌های پیشین از مرتبه $ O(log\; n)$ است. عمل درج نیز در min-heap از همین مرتبه است.

عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد، روی هم رفته از مرتبه اجرایی $n$ هستند. اما در روش آرایه نیمه‌مرتب این مرتبه به $log\; n$ کاهش میابد. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارآیی بسیار بهتری دارد.


تا کنون ۳۶ امتیاز ثبت شده
نوشته لایک نداشت؟
 
به اشتراک گذاری نوشته

algs.ir/spocw9c

اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram


نام: *  

پست الکترونیک (محرمانه):

پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• parastoo
۹ مرداد ۱۳۸۷، ساعت ۲۱:۱۲

salam mishe mano to yahoo add konid soal dashtam azaton

• راحله
۵ شهریور ۱۳۸۷، ساعت ۲۳:۰۹

سلام جرا نمی تونیم کپی بگیریم ا ز صفحات تا بعد که وقت داشتیم بخونیم من یک دانشجوی ترم3 کامپوترم که تازه راهم می خوام از شما کمک بگیرم ببینم چیکار کنم برای اینکه برنامه نویسیم قوی شه نمی دونم اصلا وارد برنامهدنویسی شم یا نه شبکه را دوست دارم لطفا مرا راهنماییکنید با کمال سپاس

مسعود اقدسی فام
۶ شهریور ۱۳۸۷، ساعت ۱۶:۵۰

اینکه چرا نمی شه کپی گرفت رو نمی دونم! من بارها این کار رو انجام دادم. ظاهرا که مشکلی وجود نداره. صفحه رو به صورت کامل ذخیره می کنید؟ یا از انتخاب متن و Copy & Paste استفاده می کنید؟

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

• asal
۱۶ دی ۱۳۸۷، ساعت ۲۳:۵۱

سلام.خسته نبلاشيد.من يه برنامه مي خوام كه يه عبارت به صورتprefix و post  و infix با پرانتز گذاري از ورودي دريافت و ان را به معادلش در 2 نوع ديگر تبديل كنيد.(براي هر كدام يك تابع ميخواد در كل ميشه 6 تابع )

• asal
۲۱ دی ۱۳۸۷، ساعت ۲۱:۲۲

سلام.چرا جوابمو نميديد؟

مسعود اقدسی فام
۲۱ دی ۱۳۸۷، ساعت ۲۱:۳۲

عسل خانم به تذکراتی که در مورد پیام های ارسالی خوانندگان داده شده توجه کنید.

• زهراعارفيان
۱۵ اردیبهشت ۱۳۸۸، ساعت ۰۷:۴۶

با سلام پياده سازي stackو saff را با ليست پيوندي مي خواستم.

• مرتضی کاظمی
۲۵ دی ۱۳۸۹، ساعت ۰۹:۰۹

با سلام:خواهشمندم به این سوال من پاسخ دهید .....با کمال تشکر

سوال:  N نفر با وزنهایW1,W2,….Wn در یک طرف رودخانه ایستاده اند و می خواهند به طرف دیگر بروند ، برای این منظور قایقی در اختیار دارند که حداکثر وزنی که می تواند تحمل کند برابر w  است ، بنابراین ممکن است لازم باشد چندمرتبه این قایق به طرف دیگررودخانه برود و برگردد تا تمامی افراد منتقل شوند،درضمن نباید قایق خالی برگردد و حداقل یکنفربا قایق برگردد. برنامه ای بنویسید که چگونه می توان با حداقل تعداد حرکت همه افراد را به سمت دیگر منتقل کرد.

۲۵ دی ۱۳۸۹، ساعت ۱۷:۲۳
• مسعود اقدسی فام

الگوریتم حریصانه‌ای که در هر حال حاضر به ذهن من می‌رسه:

افراد بر حسب وزن مرتب می‌کنیم.

در هر مرحله قایق رو از کم‌وزن‌ترین افراد تا جایی که ظرفیت داشته باشه پر می‌کنیم.

در برگشت هم کم‌وزن‌ترین نفر موجود قایق رو برمی‌گردونه.

در این حالت در هر مرحله حداکثر نفرات ممکن سوار قایق می‌شن. در برگشت هم نفری بر می‌گرده که در سفر بعدی حداقل فضای ممکن رو می‌گیره.

• مهشید
۲۱ بهمن ۱۳۸۹، ساعت ۱۲:۲۵

سلام دوسته عزیز اگه ممکنه 3 سوال داشتم جواب بدید

1.فرض کنید می خواهیم یک صف را در محیطی که در ان 2 پشته به عنوان مثالS1وS2 وارد بسازیم توضیح دهید که چگونه می توان برای اجرای عملیات add g و del g  را پیاده سازی کرد؟

2.یک صف را بااستفاده از لیست پیوندی پیاده سازی کنید؟

3.برنامه ای بنویسید که تعدادی اسم را بگیرد و در یک لیست پیوندی چرخشی ذخیره کند و سپس یک عدد را از ورودی گرفته به نام step و از ابتدای لیست به اندازه step جلو برود و اسم افراد را از داخل لیست حذف کند این کار را انقدر ادامه دهید تا یک اسم باقی بماند؟

ممنونم میشم بهم جواب بدید اخه تا بد از ظهر اگه این سوالا رو جواب ندم این درسو افتادم07

مطالبتون حرف نداشت کلی به دردم خورد

• مسعود
۲۶ اردیبهشت ۱۳۹۰، ساعت ۱۲:۰۹

سلام باز مزاحمت شدم .کمکم کن.

با داشتن دو صف از رشته هایی که به طور صعودی قرار گرفته اند ، الگوریتمی برای انتقال کلیه رشته ها به صف سوم بیابید به طوریکه تمام رشته ها در صف سوم به طور صعودی قرار گرفته باشند.

06

• فرزاد کمالی فر
۱۶ دی ۱۳۹۱، ساعت ۲۲:۳۷

مرسی،مختصر و مفید.موفق باشید

• فرزاد کمالی فر
۱۶ دی ۱۳۹۱، ساعت ۲۲:۴۴

در جواب آقا مسعود با اجازه ی نویسنده ی عزیز مطالب،ما سه تا صف داریم دوتاشو که از قبل داشتیم و یکیش هم که قراره داده ها توش به صورت صعودی قرار بگیرند به طول مجموع دو صف قبلی میسازیم،حالا هرکدوم از صفهای ما باید روی خونه ی اولشون ی اشاره گر داشته باشند،حالا باید بین خونه ای که اشاره گرهای دوصف بهشون اشاره میکنن ماکس بگیریم و بریم عنصر بعدی...و  همینطور تا آخر...توجه کن که اگ یکی از صفها خالی شد باید صف بعدی رو کلا به تریب انتقال بدی توی صف سوم...

موفق باشی

• فرزاد کمالی فر
۱۶ دی ۱۳۹۱، ساعت ۲۲:۴۵

یادم رفت بگم ک  اینجوری میتونی بهترین هزینه رو هم داشته باشی03

• فاطمه
۲۸ دی ۱۳۹۱، ساعت ۰۹:۵۰

توضیحی درباره ساختارDeap و کاربردش میخواستم.

• میترا
۲۶ آبان ۱۳۹۳، ساعت ۱۰:۴۰

باسلام

میخواستم 1صف اولویت از طریق ارایه واسم پیاده سازی کنید.لطفا

• زهرا
۱۲ دی ۱۳۹۵، ساعت ۱۰:۵۰

08

• ذئ
۷ بهمن ۱۳۹۵، ساعت ۱۶:۰۶

07

• محمدامین
۱۰ دی ۱۴۰۰، ساعت ۲۰:۳۷

عالییییی

تشکر فراوان