صف اولویت‌دار - الگوریتمستان
الگوریتمستان
2313.745.00
  »  

       

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

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «صف اولویت دار» تیر ماه 1387 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


صف اولویت‌دار (یا صف اولویتی - 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$ کاهش می‌یابد. پس می‌توان گفت که روش درخت هیپ برای پیاده‌سازی صف اولویتی کارآیی بسیار بهتری دارد.


این نوشته آخرین بار در تاریخ چهارشنبه، ۱۳ مرداد ماه ۱۳۹۵ مورد بازنویسی نگارشی قرار گرفته است.
نوشته‌های مرتبط
        معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C
        آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
        معرفی فایل سرآیند algorithm از کتابخانه قالب استاندارد زبان برنامه‌نویسی ++C به همراه نمونه کد
        آشنایی با درخت Heap (هیپ، هرم یا کپه) به عنوان یکی از ساختمان های داده پرکاربرد و بررسی روش ساخت، درج گره و حذف گره و ارائه‌ی کد نمونه به زبان برنامه‌نویسی ++C
        معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        بررسی مفهوم و روش پیاده‌سازی لیست پیوندی و توابع مرتبط آن به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

 


» مرتضی کاظمی

شنبه، ۲۵ دی ماه ۱۳۸۹، ساعت ۰۹:۰۹
با سلام:خواهشمندم به این سوال من پاسخ دهید .....با کمال تشکر

سوال:  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