پشتهها و صفهای اولویتدار
صف اولویتدار یک نوع داده انتزاعی است که همیشه عنصر با بالاترین (یا پایینترین) اولویت را بازمیگرداند؛ پشتهها ساختارهای درختی استانداردی هستند که این نوع داده را با عملیات درج و استخراج کمینه کارآمد پیادهسازی میکنند.
Definition
صف اولویتدار یک نوع داده انتزاعی است که از درج عناصر با اولویتها و استخراج عنصر با بالاترین اولویت پشتیبانی میکند؛ پشته یک ساختار داده مبتنی بر درخت است که ویژگی پشته را برآورده میکند — کلید هر گره به طور سازگار نسبت به فرزندانش مرتب شده است — و یک صف اولویتدار را به طور کارآمد پیادهسازی میکند.
Scope
این موضوع به ADT صف اولویتدار و پیادهسازیهای پشتهای آن میپردازد: پشته دودویی و نمایش آرایهای آن، ویژگی پشته و عملیات بالا بردن/پایین آوردن، مرتبسازی پشتهای (heapsort)، و پشتههای ادغامپذیر پیشرفته مانند پشتههای دوجملهای (binomial) و فیبوناچی (Fibonacci) که هزینههای کاهش کلید و ادغام را بهبود میبخشند. این مبحث به الگوریتمهای گراف (دایکسترا، پریم) و شبیهسازی رویدادمحور که به صفهای اولویتدار متکی هستند، مرتبط است.
Core questions
- چه عملیاتی ADT صف اولویتدار را تعریف میکنند و چگونه یک پشته آنها را پیادهسازی میکند؟
- چگونه ویژگی پشته امکان یافتن کمینه را در زمان ثابت و درج/استخراج را در زمان لگاریتمی فراهم میکند؟
- چگونه یک پشته دودویی به طور فشرده در یک آرایه ذخیره میشود و چگونه در زمان خطی ساخته میشود؟
- چگونه مرتبسازی پشتهای از یک پشته برای مرتبسازی درجا در زمان O(n log n) استفاده میکند؟
- چه زمانی پشتههای ادغامپذیر مانند پشتههای فیبوناچی الگوریتمهایی را که اغلب کلیدها را کاهش میدهند، بهبود میبخشند؟
Key concepts
- ADT صف اولویتدار
- ویژگی پشته
- پشته دودویی
- نمایش پشته مبتنی بر آرایه
- بالا بردن و پایین آوردن
- ساخت پشته در زمان خطی
- مرتبسازی پشتهای
- پشتههای فیبوناچی و دوجملهای
Key theories
- ویژگی پشته و نمایش آرایه
- یک پشته دودویی یک درخت دودویی تقریباً کامل است که در آن کلید هر گره بر کلید فرزندانش غالب است؛ میتوان آن را در یک آرایه با نمایهگذاری ضمنی والد-فرزند ذخیره کرد که درج و استخراج را در زمان O(log n) و یافتن کمینه را در زمان O(1) فراهم میکند.
- کارایی سرشکنشده پشتههای فیبوناچی
- پشتههای فیبوناچی از کاهش کلید در زمان سرشکنشده O(1) و استخراج کمینه در زمان سرشکنشده O(log n) پشتیبانی میکنند که زمان اجرای مجانبی الگوریتمهایی مانند دایکسترا و پریم را که بسیاری از کاهش کلیدها را انجام میدهند، بهبود میبخشد.
Clinical relevance
صفهای اولویتدار زیرساختهای ضروری هستند: آنها وظایف آماده را در زمانبندیهای سیستمعامل مرتب میکنند، رویدادها را در شبیهسازی رویداد گسسته مدیریت میکنند، جستجوی بهترین-اول و A* را هدایت میکنند، و مرز را در الگوریتمهای دایکسترا و پریم فراهم میکنند. مرتبسازی پشتهای یک مرتبسازی درجا با پیچیدگی زمانی O(n log n) و کرانهای تضمینشده در بدترین حالت ارائه میدهد.
History
جی. دبلیو. جی. ویلیامز پشته دودویی و مرتبسازی پشتهای را در سال 1964 معرفی کرد، و رابرت فلوید مدت کوتاهی پس از آن رویه ساخت پشته با زمان خطی را ارائه داد. پشتههای دوجملهای (وویلمین، 1978) و پشتههای فیبوناچی (فردمن و تارژان، 1987) ادغام کارآمد و کاهش کلید سرشکنشده را اضافه کردند که زمان اجرای الگوریتمهای گراف کلاسیک را بهبود بخشید.
Key figures
- J. W. J. Williams
- Robert W. Floyd
- Michael Fredman
- Robert Tarjan
Related topics
Seminal works
- williams1964
- fredman1987
- cormen2009
Frequently asked questions
- چرا یک پشته دودویی را در آرایه ذخیره میکنیم به جای استفاده از اشارهگرها؟
- یک پشته دودویی یک درخت دودویی تقریباً کامل است، بنابراین گرههای آن به طور منظم به شاخصهای متوالی آرایه نگاشت میشوند: گرهای در شاخص i فرزندانی در 2i و 2i+1 دارد. این کار از سربار اشارهگر جلوگیری میکند، رفتار حافظه نهان (cache) را بهبود میبخشد و پیمایش را به محاسبات ساده ریاضی تبدیل میکند.
- چه زمانی پشتههای فیبوناچی ارزش پیچیدگی خود را دارند؟
- پشتههای فیبوناچی کاهش کلید را در زمان سرشکنشده O(1) ارائه میدهند که زمان اجرای مجانبی الگوریتمهایی مانند کوتاهترین مسیرهای دایکسترا را در گرافهای متراکم بهبود میبخشد. در عمل، عوامل ثابت بزرگ آنها به این معنی است که پشتههای دودویی سادهتر اغلب سریعتر هستند، بنابراین آنها عمدتاً برای کرانهای نظری و موارد تخصصی اهمیت دارند.