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

        #ساختمان داده #صف 

صف اولویت‌دار (یا صف اولویتی - 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
نوشته‌ها از این دست
       ✦   لیست پیوندی
آخرین نوشته‌ها
       ✦   الگوریتم آنلاین
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

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

متن پیام: *  

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

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

عالییییی

تشکر فراوان