ساختمان داده ها صف اولویت دار

صف اولویت دار (Priority Queue) از جمله ساختمان داده های بسیار پرکاربرد است.

در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می شود. در این تکنیک مثل یک صف نانوایی داده ها به ترتیب ورود پشت سر هم در صف قرار می گیرند. بنابراین اولین داده ورودی اولین داده خروجی نیز خواهد بود.

اما در صف اولویتی برای هر داده اولویتی - نه لزوما منحصر بفرد - مشخص می شود. صف اولویت را می توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش ها از صفهای اولویت استفاده می کند.

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

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

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

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

1. پیاده سازی با استفاده از آرایه نامرتب:

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

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

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

2. پیاده سازی با استفاده از آرایه مرتب:

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

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

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

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

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

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

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

در یک درخت min-heap عنصری با کوچکترین کلید همواره در ریشه قرار دارد (چرا!؟). در نتیجه عمل حذف گره ریشه از درخت min-heap کوچکترین عنصر آن را به ما می دهد. این عمل بر اساس بحث های پیشین ما از مرتبه ( O ( log2n است. عمل درج در min-heap هم همانطور که می دانید از همین مرتبه است.

عملیات درج و حذف روی یک صف اولویتی که با استفاده از آرایه مرتب یا نامرتب ساخته شده باشد روی هم رفته از مرتبه ( O ( n است. اما در روش آرایه نیمه مرتب این مرتبه به ( O ( log2n کاهش می یابد. پس می توان گفت که روش درخت هیپ برای پیاده سازی صف اولویتی کارآیی بسیار بهتری دارد.

ساختمان داده ها صف اولویت دار

مطالب مشابه :

ساختمان داده در سی شارپ

ساختمان داده ها

اینم جزوه ساختمان داده ها

ساختمان داده ها صف اولویت دار

ساختمان داده‌ها

برنامه آموزش درس ساختمان داده ها (صلواتی) - رشته کامپیوتر - نرم افزار آموزش ساختمان داده