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

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

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

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

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

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

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

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

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

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

ادغام

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

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