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

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

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

یک هیپ کمینه (min heap) یک درخت دودویی است که در آن مقدار هر رأس کمتر یا مساوی مقادیر فرزندانش است. بنابراین، کمترین مقدار درخت همیشه در رأس ریشه قرار دارد.

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

عملیات پیش‌فرض یک هیپ عبارتند از:

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

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

ساختار داده

می‌توانیم بلافاصله ساختار هیپ دودویی را توصیف کنیم:

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

در هر رأس یک مقدار ذخیره می‌کنیم.
علاوه بر آن، اشاره‌گرهایی به فرزندان چپ و راست داریم که اگر فرزند مربوطه وجود نداشته باشد، به `null` اشاره می‌کنند.

## عملیات

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

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

فرض کنید دو هیپ $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 ادغام کنیم، بنابراین به طور تصادفی فرزندان t1 را جابجا کرده و سپس عمل ادغام را انجام می‌دهیم.

پیچیدگی

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

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

فرض می‌کنیم که مقدار مورد انتظار $h(T)$ را می‌توان با لگاریتم تعداد رئوس در هیپ از بالا تخمین زد:

$$\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}$$

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

البته ما هنوز راضی نیستیم. مقدار مورد انتظار $h(T)$ چیزی در مورد بدترین حالت نمی‌گوید. هنوز ممکن است برای یک درخت خاص، مسیرها از ریشه به رئوس به طور متوسط بسیار بیشتر از $\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}$ است (این موضوع به نوعی رفتار الگوریتم در بدترین حالت را توصیف می‌کند).