ⓘ پشته‌های دوجمله‌ای. در علوم رایانه پشته‌های دوجمله‌ای داده‌ساختارهایی مشابه با پشته‌های دودویی هستند که قادر به پشتیبانی از عمل ادغام سریع دو Heap نیز هستند. که ..

                                     

ⓘ پشته‌های دوجمله‌ای

در علوم رایانه پشته‌های دوجمله‌ای داده‌ساختارهایی مشابه با پشته‌های دودویی هستند که قادر به پشتیبانی از عمل ادغام سریع دو Heap نیز هستند. که این عمل با استفاده این داده ساختار، از درخت دو جمله‌ای حاصل می‌شود.

                                     

1. درخت دو جمله‌ای

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

  • یک درخت دو جمله‌ای از درجه k ریشه‌ای دارد که فرزندان آن به ترتیب درخت‌های دو جمله‌ای از درجه‌های k-۱،. ،۲٬۱،۰ هستند
  • یک درخت دو جمله‌ای از درجه ۰ از یک رأس تشکیل می‌شود

یک درخت دو جمله‌ای از مرتبه k دارای ۲ k رأس، و ارتفاع k می‌باشد.

به خاطر ساختار خاص درخت دو جمله‌ای، می‌توان هر درخت از مرتبه k را از وصل کردن دو درخت از مرتبه k -۱ ساخت، به این ترتیب که ریشه یکی از این درخت‌ها را به عنوان چپ‌ترین فرزند به ریشه درخت دیگر وصل کرد. این ویژگی در انجام عمل ادغام روی Heapهای دو جمله‌ای اهمیت دارد که یکی از دلایل برتری آن‌ها بر Heapهای معمولی است.

                                     

2. ساختار پشته‌های دوجمله‌ای

یک Heap دو جمله‌ای با استفاده از مجموعه‌ای از درخت‌های دو جمله‌ای پیاده‌سازی می‌شود که دارای خصوصیات Heap دو جمله ای است:

  • هر یک از درخت‌های Heap دو جمله‌ای از خاصیت Minimum Heap پیروی می‌کنند. یعنی key هر رأس از key پدرش بزرگ تر است یا با آن مساوی است.
  • از هر درخت دو جمله‌ای با مرتبه خاص فقط یک یا صفر زیر درخت می‌تواند وجود داشته باشدشامل درخت مرتبه صفر.

خصوصیت اول تضمین می‌کند که ریشه هر درخت دارای کوچکترین کلید موجود در آن درخت است، که به تمام Heap تعمیم پیدا می‌کند.

خاصیت دوم نتیجه می‌دهد که هر Heap با n عنصر حد اکثر از log n + ۱ تشکیل شده‌است. در واقع تعداد و مرتبه هر یک از این درخت‌ها به‌طور منحصر به فرد توسط تعداد عناصر درخت n مشخص می‌شود: هر درخت دودویی متناظر است با رقم یک در نمایش دودویی n. برای مثال عدد ۱۳ در مبنای دو دارای نمایش ۱۱۰۱ می‌باشد، 2 3 + 2 + 2 0 {\displaystyle 2^{3}+2^{2}+2^{0}} در نتیجه یک پشته دو جمله‌ای با ۱۳ عنصر از سه درخت دوجمله‌ای با مرتبه‌های ۰، ۲ و ۳ تشکیل شده‌استهمانند شکل.

یک پشته دو جمله‌ای شامل ۱۳ عنصر نا مساوی

                                     

3. پیاده‌سازی

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

ادغام

همان طور که قبلاً نیز گفته شد مهم‌ترین عملیات در پشته‌های دو جمله‌ای، ادغام دو درخت دو جمله‌ای از یک مرتبه در دو پشته دو جمله‌ای می‌باشد. به این منظور از آنجایی که ریشه یک درخت کوچکترین عضو آن درخت می‌باشد با مقایسه کلید ریشه‌های دو درخت، کلیدی که کوچکتر است عضو مینیمم است به عنوان ریشه درخت جدید انتخاب می‌شود و ریشه دیگر زیر درخت آن می‌شود. این رویه پایه کامل کردن عملیات ادغام دو پشته دو جمله‌ای است.

function mergeTreep, q if p.root
                                     
  • پشته Binary heap ضعیف پشته هیپ دوجمله ای فیبوناچی پشته AF - پشته لئوناردو پشته 2 - 3 پشته نرم پشته جفت شدن پشته چپ پشته Treap Beap مورب پشته سه تایی پشته
  • شامل انبوهی از درخت ها است. این هیپ زمان اجرای سرشکن بهتری نسبت به هیپ دوجمله ای دارد. هیپ های فیبوناتچی توسط مایکل فردمن و رابرت تارجن در سال ایجاد