در علوم رایانه پشته های دوجمله ای ( Binomial heaps ) داده ساختارهایی مشابه با پشته های دودویی هستند که قادر به پشتیبانی از عمل ادغام سریع دو Heap نیز هستند. که این عمل با استفاده این داده ساختار، از درخت دو جمله ای حاصل می شود.
یک پشته دو جمله ای با استفاده از مجموعه ای از درخت های دو جمله ای ساخته می شود ( همان گونه که پشته دودویی از درخت دودویی ساخته می شود ) . یک درخت دو جمله ای به صورت بازگشتی، همانند زیر تعریف می شود:
• یک درخت دو جمله ای از درجه ۰ از یک رأس تشکیل می شود
• یک درخت دو جمله ای از درجه k ریشه ای دارد که فرزندان آن به ترتیب درخت های دو جمله ای از درجه های k - ۱، . . . ، ۲٬۱، ۰ هستند
یک درخت دو جمله ای از مرتبه k دارای ۲k رأس، و ارتفاع k می باشد.
به خاطر ساختار خاص درخت دو جمله ای، می توان هر درخت از مرتبه k را از وصل کردن دو درخت از مرتبه k - ۱ ساخت، به این ترتیب که ریشه یکی از این درخت ها را به عنوان چپ ترین فرزند به ریشه درخت دیگر وصل کرد. این ویژگی در انجام عمل ادغام روی Heapهای دو جمله ای اهمیت دارد که یکی از دلایل برتری آن ها بر Heapهای معمولی است.
یک Heap دو جمله ای با استفاده از مجموعه ای از درخت های دو جمله ای پیاده سازی می شود که دارای خصوصیات Heap دو جمله ای است:
• هر یک از درخت های Heap دو جمله ای از خاصیت Minimum Heap پیروی می کنند. یعنی key هر رأس از key پدرش بزرگ تر است یا با آن مساوی است.
• از هر درخت دو جمله ای با مرتبه خاص فقط یک یا صفر زیر درخت می تواند وجود داشته باشد ( شامل درخت مرتبه صفر ) .
خصوصیت اول تضمین می کند که ریشه هر درخت دارای کوچکترین کلید موجود در آن درخت است، که به تمام Heap تعمیم پیدا می کند.
خاصیت دوم نتیجه می دهد که هر Heap با n عنصر حد اکثر از log n + ۱ تشکیل شده است. در واقع تعداد و مرتبه هر یک از این درخت ها به طور منحصر به فرد توسط تعداد عناصر درخت n مشخص می شود: هر درخت دودویی متناظر است با رقم یک در نمایش دودویی n. برای مثال عدد ۱۳ در مبنای دو دارای نمایش ۱۱۰۱ می باشد، 2 3 + 2 2 + 2 0 در نتیجه یک پشته دو جمله ای با ۱۳ عنصر از سه درخت دوجمله ای با مرتبه های ۰، ۲ و ۳ تشکیل شده است ( همانند شکل ) .
یک پشته دو جمله ای شامل ۱۳ عنصر نا مساوی
به این دلیل که انجام هر یک از عملیات نیاز به دسترسی تصادفی به ریشه های درخت های دودویی ندارد، ریشه درخت ها را می توان به ترتیب مرتبه در یک لیست پیوندی ( ) ذخیره کرد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفیک پشته دو جمله ای با استفاده از مجموعه ای از درخت های دو جمله ای ساخته می شود ( همان گونه که پشته دودویی از درخت دودویی ساخته می شود ) . یک درخت دو جمله ای به صورت بازگشتی، همانند زیر تعریف می شود:
• یک درخت دو جمله ای از درجه ۰ از یک رأس تشکیل می شود
• یک درخت دو جمله ای از درجه k ریشه ای دارد که فرزندان آن به ترتیب درخت های دو جمله ای از درجه های k - ۱، . . . ، ۲٬۱، ۰ هستند
یک درخت دو جمله ای از مرتبه k دارای ۲k رأس، و ارتفاع k می باشد.
به خاطر ساختار خاص درخت دو جمله ای، می توان هر درخت از مرتبه k را از وصل کردن دو درخت از مرتبه k - ۱ ساخت، به این ترتیب که ریشه یکی از این درخت ها را به عنوان چپ ترین فرزند به ریشه درخت دیگر وصل کرد. این ویژگی در انجام عمل ادغام روی Heapهای دو جمله ای اهمیت دارد که یکی از دلایل برتری آن ها بر Heapهای معمولی است.
یک Heap دو جمله ای با استفاده از مجموعه ای از درخت های دو جمله ای پیاده سازی می شود که دارای خصوصیات Heap دو جمله ای است:
• هر یک از درخت های Heap دو جمله ای از خاصیت Minimum Heap پیروی می کنند. یعنی key هر رأس از key پدرش بزرگ تر است یا با آن مساوی است.
• از هر درخت دو جمله ای با مرتبه خاص فقط یک یا صفر زیر درخت می تواند وجود داشته باشد ( شامل درخت مرتبه صفر ) .
خصوصیت اول تضمین می کند که ریشه هر درخت دارای کوچکترین کلید موجود در آن درخت است، که به تمام Heap تعمیم پیدا می کند.
خاصیت دوم نتیجه می دهد که هر Heap با n عنصر حد اکثر از log n + ۱ تشکیل شده است. در واقع تعداد و مرتبه هر یک از این درخت ها به طور منحصر به فرد توسط تعداد عناصر درخت n مشخص می شود: هر درخت دودویی متناظر است با رقم یک در نمایش دودویی n. برای مثال عدد ۱۳ در مبنای دو دارای نمایش ۱۱۰۱ می باشد، 2 3 + 2 2 + 2 0 در نتیجه یک پشته دو جمله ای با ۱۳ عنصر از سه درخت دوجمله ای با مرتبه های ۰، ۲ و ۳ تشکیل شده است ( همانند شکل ) .
یک پشته دو جمله ای شامل ۱۳ عنصر نا مساوی
به این دلیل که انجام هر یک از عملیات نیاز به دسترسی تصادفی به ریشه های درخت های دودویی ندارد، ریشه درخت ها را می توان به ترتیب مرتبه در یک لیست پیوندی ( ) ذخیره کرد.
wiki: پشته های دوجمله ای