پرش به محتویات

هیپ تصادفی (Randomized Heap)

هیپ تصادفی یه نوع هیپ خیلی باحاله که با کمک گرفتن از شانس و تصادف، کاری می‌کنه که همه‌ی عملیات‌هاش توی زمان لگاریتمیِ مورد انتظار (expected logarithmic time) انجام بشن.

خب، بیا اول ببینیم هیپ کمینه (min heap) چیه. هیپ کمینه یه درخت دودوییه که توش مقدار هر گره (node)، از مقدار بچه‌هاش کوچیکتر یا مساویه. خیلی ساده! نتیجه‌اش اینه که کوچیک‌ترین مقدار کل درخت، همیشه تو ریشه (root) پیدا میشه.

هیپ بیشینه (max heap) هم دقیقا همینه، فقط برعکس: کافیه هرجا گفتیم «کمتر»، تو جاش بگی «بیشتر».

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

  • اضافه کردن یه مقدار جدید
  • پیدا کردن کوچیک‌ترین مقدار
  • حذف کردن کوچیک‌ترین مقدار
  • ادغام دوتا هیپ (بدون اینکه مقادیر تکراری رو حذف کنیم)
  • حذف یه عنصر دلخواه (البته اگه جاش رو توی درخت بدونیم)

خبر خوب اینه که هیپ تصادفی می‌تونه همه‌ی این کارها رو با یه پیاده‌سازی خیلی ساده و سرراست، در زمان مورد انتظار $O(\log n)$ انجام بده.

ساختار داده

بریم سراغ ساختار داد‌ه‌اش. می‌تونیم ساختار هیپ دودویی رو خیلی راحت اینطوری تعریف کنیم:

```cpp file=randomized_heap_structure struct Tree { int value; Tree * l = nullptr; Tree * r = nullptr; }; 

همونطور که می‌بینی، توی هر گره یه `value` ذخیره می‌کنیم. به علاوه، دوتا اشاره‌گر (pointer) هم داریم به بچه‌های چپ و راستش، که اگه اون بچه وجود نداشته باشه، مقدارشون `null` میشه.

## عملیات

اینجاش جالبه! خیلی راحت میشه فهمید که همه‌ی اون عملیات‌ها رو میشه به یه عملیات اصلی و کلیدی خلاصه کرد: **ادغام (merge)** کردن دو تا هیپ توی یه هیپ.

بذار ببینیم چطوری:

-   **اضافه کردن یه مقدار جدید؟** انگار داری خودِ هیپ رو با یه هیپ جدید که فقط همین یه مقدار رو داره، ادغام می‌کنی.
-   **پیدا کردن کمینه؟** این که کاری نداره! کمینه همیشه مقدار توی ریشه است.
-   **حذف کمینه؟** کافیه بچه‌های چپ و راستِ ریشه رو با هم ادغام کنی و هیپ جدید حاصل میشه.
-   **حذف یه عنصر دلخواه؟** اینم شبیه قبلیه. بچه‌های اون گره رو با هم ادغام می‌کنی و خود گره رو با نتیجه‌ی این ادغام جایگزین می‌کنی.

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

خب، حالا چطوری دوتا هیپ $T_1$ و $T_2$ رو با هم ادغام کنیم؟
واضحه که ریشه‌ی هر کدوم از این هیپ‌ها، کوچیک‌ترین مقدارِ همون هیپ رو داره. پس، ریشه‌ی هیپِ حاصل هم باید کوچیک‌ترین مقدار بین این دو تا ریشه باشه.
پس خیلی راحت دو تا ریشه رو مقایسه می‌کنیم و اونی که کوچیکتره رو به عنوان ریشه‌ی جدید انتخاب می‌کنیم.
حالا باید بچه‌های اون گره‌ای که انتخاب شد رو با هیپِ باقی‌مونده (اون یکی هیپ) قاطی کنیم. چطوری؟ یکی از بچه‌ها رو انتخاب می‌کنیم و اون رو با هیپِ باقی‌مونده ادغام می‌کنیم.
اینجوری، دوباره به همون مسئله‌ی ادغام دو تا هیپ می‌رسیم. این فرآیند بازگشتی هم بالاخره یه جایی تموم میشه (تعداد مراحلش از مجموع ارتفاع دو تا هیپ بیشتر نمیشه).

خب، برای اینکه به طور میانگین به همون پیچیدگی لگاریتمی خفنه برسیم، باید یه راهی برای انتخاب «یکی از دو فرزند» پیدا کنیم که باعث بشه میانگین طول مسیرها لگاریتمی بشه.
حدس زدنش سخت نیست که قراره این تصمیم رو **کاملاً شانسی** بگیریم!
بنابراین، پیاده‌سازی تابع ادغام این شکلی میشه:

```cpp file=randomized_heap_merge
Tree* merge(Tree* t1, Tree* t2) {
    if (!t1 || !t2)
        return t1 ? t1 : t2;
    if (t2->value < t1->value)
        swap(t1, t2);
    if (rand() & 1)
        swap(t1->l, t1->r);
    t1->l = merge(t1->l, t2);
    return t1;
}

توی این کد، اول چک می‌کنیم ببینیم آیا یکی از هیپ‌ها خالیه یا نه؛ اگه خالی بود، که خب ادغامی در کار نیست و اون یکی هیپ رو برمی‌گردونیم. در غیر این صورت، کاری می‌کنیم که t1 همیشه اون هیپی باشه که ریشه‌ش کوچیکتره (اگه لازم باشه t1 و t2 رو جابجا می‌کنیم). اینجاست که جادوی تصادفی‌سازی اتفاق میفته: ما می‌خوایم بچه چپِ t1 رو با t2 ادغام کنیم، پس با احتمال ۵۰-۵۰ (با استفاده از rand() & 1) بچه‌های چپ و راست t1 رو با هم جابجا می‌کنیم و بعدش فراخوانی بازگشتی ادغام رو انجام میدیم.

پیچیدگی

برای تحلیل پیچیدگی، یه متغیر تصادفی به اسم $h(T)$ تعریف می‌کنیم. این متغیر نشون‌دهنده‌ی طول یه مسیر تصادفی از ریشه تا یه برگه (منظور از طول، تعداد یال‌هاست). واضحه که الگوریتم merge ما توی $O(h(T_1) + h(T_2))$ مرحله تموم میشه. پس اگه بخوایم پیچیدگی رو بفهمیم، باید همین متغیر $h(T)$ رو تحلیل کنیم.

مقدار مورد انتظار

مقدار مورد انتظار (Expected Value) $h(T)$ رو میشه با لگاریتم تعداد گره‌های توی هیپ از بالا کران‌دار کرد (upper bound). یعنی:

$$\mathbf{E} h(T) \le \log(n+1)$$

اثباتش هم خیلی ساده‌ است و با استقرا انجام میشه. فرض کن $L$ و $R$ زیردرخت‌های چپ و راست ریشه‌ی $T$ باشن و تعداد گره‌هاشون هم $n_L$ و $n_R$ باشه ($n = n_L + n_R + 1$).

اینم ادامه‌ی گام استقرایی اثبات:

$$\begin{align} \mathbf{E} h(T) &= 1 + \frac{\mathbf{E} h(L) + \mathbf{E} h(R)}{2} \le 1 + \frac{\log(n_L + 1) \log(n_R + 1)}{2} \\\\ &= 1 + \log\sqrt{(n_L + 1)(n_R + 1)} = \log 2\sqrt{(n_L + 1)(n_R + 1)} \\\\ &\le \log \frac{2\left((n_L + 1) + (n_R + 1)\right)}{2} = \log(n_L + n_R + 2) = \log(n+1) \end{align}$$ (اون قسمتی که از $\le$ استفاده کردیم، از نامساوی معروف میانگین حسابی-هندسی یا AM-GM میاد).

فراتر رفتن از مقدار مورد انتظار

خب، مقدار میانگین رو درآوردیم، ولی این هنوز کافی نیست. چرا؟ چون مقدار مورد انتظار چیزی در مورد بدترین حالت به ما نمیگه. هنوز این احتمال وجود داره که برای یه درخت خاص، مسیرهای از ریشه به برگ به طور متوسط خیلی طولانی‌تر از $\log(n+1)$ بشن.

بیا ثابت کنیم که احتمال اینکه از این میانگین خیلی دور بشیم، واقعا خیلی کمه:

$$P\{h(T) > (c+1) \log n\} < \frac{1}{n^c}$$

این فرمول برای هر ثابت مثبت $c$ برقراره.

برای اثبات، $P$ رو بگیر مجموعه‌ی همه‌ی اون مسیرهایی از ریشه به برگ که طولشون از $(c+1) \log n$ بیشتره. یادت باشه که احتمال اینکه یه مسیر خاص $p$ با طول $|p|$ به عنوان مسیر تصادفی انتخاب بشه، دقیقاً $2^{-|p|}$ هست. پس می‌تونیم بنویسیم:

$$P\{h(T) > (c+1) \log n\} = \sum_{p \in P} 2^{-|p|} < \sum_{p \in P} 2^{-(c+1) \log n} = |P| n^{-(c+1)} \le n^{-c}$$

پیچیدگی الگوریتم

پس، نتیجه‌ی نهایی اینه: الگوریتم merge و در نتیجه، بقیه‌ی عملیات‌ها که باهاش تعریف میشن، به طور میانگین توی زمان $O(\log n)$ انجام میشن.

حتی از این بهتر! برای هر عدد مثبت $\epsilon$ که فکرشو بکنی، میشه یه عدد مثبت $c$ پیدا کرد، طوری که احتمال اینکه عملیاتمون بیشتر از $c \log n$ طول بکشه، از $n^{-\epsilon}$ هم کمتر باشه. (این جمله آخر یه جورایی داره رفتار الگوریتم توی بدترین حالت رو توصیف می‌کنه و بهمون اطمینان میده که خیلی بعیده بدشانسی بیاریم).