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

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

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

درخت‌های دو جمله‌ای از مرتبه 0 تا 3: هر درخت دارای زیر درخت‌هایی از تمام درخت‌های دو جمله‌ای با مرتبه کمتر از خود است. به طور مثال درخت مرتبه 3 دارای 3 زیر درخت با مرتبه‌های 3، 2و1(که به ترتیب با رنگ‌های آبی، سبز و قرمز مشخص شده‌اند).

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

• یک درخت دو جمله‌ای از درجه ۰ از یک رأس تشکیل می‌شود
• یک درخت دو جمله‌ای از درجه 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}$ در نتیجه یک پشته دو جمله‌ای با ۱۳ عنصر از سه درخت دوجمله‌ای با مرتبه‌های ۰، ۲ و ۳ تشکیل شده‌است(همانند شکل).

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

پیاده‌سازی

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

ادغام

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

function mergeTree(p, q)
    if p.root <= q.root
        return p.addSubTree(q)
    else
        return q.addSubTree(p)

برای ادغام دو درخت دوجمله‌ای، نخست کلید ریشه‌ها را مقایسه می‌کنیم. چون 7>3، درخت سیاه در سمت چپ(دارای کلید ریشه 7) به عنوان زیر درخت به درخت خاکستری(با کلید ریشه 3) الحاق می‌شود. نتیجه یک درخت از مرتبه 3 است.

منابع

Wikipedia contributors, «Binomial heap,» Wikipedia, The Free Encyclopedia, http://en.wikipedia.org/w/index.php?title=Binomial_heap&oldid=290139444 (accessed May 15, 2009).