الگوریتمستان

یادداشت‌های یک معلم علاقه‌مند به نوشتن از آنچه آموخته و یاد می‌دهد
 

  

✤  درخت Heap

آنچه در این نوشته می‌خوانید:

درخت دودویی کامل

  [برگرد بالا]

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

  

به یک مثال دقت کنید:

  

درخت هیپ یا هرم یا کپه

  

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

  

نمایش درخت دودویی کامل

  [برگرد بالا]

نمایش با استفاده از لیست پیوندی و آرایه دو شکل مشهور نمایش درخت دودویی در ساختمان داده‌ها است. در حالت عادی انتخاب یکی از این دو روش برای نمایش بهینه و با مصرف حافظه کمتر بسته به چیدمان عناصر درخت دارد. به عنوان مثال، در درخت‌های مورب روش نمایش با آرایه بدترین بازدهی و بیشترین مصرف حافظه را دارد. اما در درخت دودویی کامل این روش در مقایسه با روش لیست پیوندی بسیار بهینه‌تر است.

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

  

نمایش درخت هیپ با استفاده از آرایه

  

در آرایه متناظر درخت دودویی کامل، از همه عناصر به صورت کامل استفاده شده و هیچ حافظه هرزی وجود ندارد (چرا؟). به همین خاطر این روش نمایش برای درخت کامل مناسب است.

فرض کنیم توابع Left ،Parent و Right شماره یک گره را گرفته و به ترتیب شماره گره والد، فرزند چپ و فرزند راست را برگرداند. در این صورت با توجه به شکل فوق:

  

\[ Parent(i) = \big[\frac{ i }{2} \big] \qquad , \qquad Left(i) = 2 i \qquad , \qquad Right(i) = 2 i + 1 \]

  

که منظور از [] جزء صحیح (کف) عدد است.

به عنوان مثال، در مورد گره شماره 3 می‌توان نوشت:

  

\[ Parent(3) = \big[\frac{3}{2} \big] = 1 \qquad , \qquad Left(3) = 2 \times 3 = 6 \qquad , \qquad Right(3) = 2 \times 3 + 1 = 7 \]

  

هرم ماکزیمم (مکس هیپ / max-heap)

  [برگرد بالا]

درخت دودویی کاملی است که مقدار هر گره بیشتر یا مساوی فرزندان خود است.

  

درخت max-heap

  

و نمایش آرایه‌ای:

  

نمایش آرایه‌ای درخت max-heap

  

هرم مینیمم (مین هیپ / min-heap)

  [برگرد بالا]

درخت دودویی کاملی است که مقدار هر گره کمتر یا مساوی فرزندان خود است.

  

درخت min-heap

  

و نمایش آرایه‌ای:

  

نمایش آرایه‌ای درخت min-heap

  

ساختن درخت Heap

  [برگرد بالا]

ساختن یک درخت heap در واقع وارد کردن متوالی گره‌ها در آن است. برای وارد کردن یک گره به درخت heap، طی دو مرحله به صورت زیر عمل می‌کنیم:

1- گره مفروض را در محلی از درخت که شرط کامل بودن آن به هم نخورد (بدون در نظر گرفتن شرط max-heap یا min-heap بودن) درج می‌کنیم.

2- اگر گره مذکور بر اساس موقعیت خود در درخت، شرط max-heap یا min-heap بودن را نقض نکند، نیاز به انجام کاری نیست و عملیات درج تمام شده است. در غیر اینصورت، با جابجا کردن گره با والد خود، درخت جدیدی حاصل می‌شود که باید مرحله 2 در مورد آن تکرار شود.

به عنوان مثال، فرض کنید یک درخت max-heap به فرم زیر داریم:

  

درخت max-heap

  

حال می‌خواهیم گرهی با مقدار 21 را به درخت اضافه کنیم. برای اینکار در مرحله اول گره مذکور را به محلی که شرط کامل بودن درخت نقض نشود وارد می‌کنیم. این محل سمت چپ‌ترین فضای آزاد آخرین سطح درخت است:

  

درج گره در max-heap

  

با درج این گره، شرط max-heap بودن نقض می‌شود. چرا که مقدار گره شماره 10 از والد خود یعنی گره شماره 5 بیشتر است. پس با توجه به دستورالعمل مرحله دوم، مقدار دو گره را جابجا می‌کنیم:

  

درج گره در max-heap

  

با این عمل، باز هم شرط max-heap بودن برآورده نمی‌شود. گره‌های شماره 5 و 2 این شرط را نقض کرده‌اند. پس باز هم با تکرار مرحله دوم مقدار این دو گره را با هم جابجا می‌کنیم:

  

درج گره در max-heap

  

حال شرط max-heap بودن برقرار بوده و عملیات درج گره تمام می‌شود.

با توجه به این مثال می‌توان مرحله دوم عملیات درج را اینگونه بیان کرد:

2- گره درج شده را با والدهای خود تا جایی که شرط max-heap یا min-heap بودن برقرار شود جابجا می‌کنیم.

  

برنامه‌نویسی درج گره در درخت heap

  [برگرد بالا]

در اینجا کد مربوط به درج گره در درخت max-heap را می‌آورم که با یک تغییر جزئی همین کد برای درخت min-heap هم قابل استفاده است.

همانطور که بحث شد، بهترین روش نمایش درخت heap استفاده از آرایه است. در مورد درخت max-heap اولیه فوق داریم:

  

نمایش آرایه‌ای درخت max-heap

  

با اضافه کردن گره 21 و طی کردن مراحل دوگانه درج گره:

  

مراحل درج گره در درخت max-heap

  

در قسمت قبلی رابطه ریاضی بین اندیس‌های والد و فرزند بیان شده است. بر اساس این رابطه و توضیحات فوق، تابع درج گره با مقدار v در یک درخت max-heap که در حال حاضر n عنصر (گره) دارد در زبان ++C به این صورت خواهد بود:

  

void push(int heap[], int &n, int v){

    int i, temp;

    heap[++n] = v;

    for(i = n ; i > 1 && heap[i] > heap[i / 2] ; i /= 2){

        temp = heap[i];

        heap[i] = heap[i / 2];

        heap[i / 2] = temp;

    }

}

  

تذکر 1: اندیس آرایه‌ها در زبان برنامه‌نویسی ++C از صفر شروع می‌شود. اما در اینجا برای راحتی کار و هماهنگ شدن با روش شماره‌گذاری درخت دودویی کامل، از اولین خانه - یعنی خانه شماره صفر - برای نمایش درخت heap استفاده نشده است.

تذکر 2: در این تابع پارامتر n به صورت مرجع تعریف شده است که مختص زبان برنامه‌نویسی ++C بوده و در زبان C وجود ندارد. متغیرهای مرجع در یک نوشته به طور کامل توضیح داده شده است.

نکته: روش درج گره جدید در درخت heap در ظاهر شباهت‌هایی به درج گره جدید در درخت جستجوی دودویی (Binary Search Tree) دارد. اما این دو اختلاف‌های مشخصی دارند:

  • در درخت جستجوی دودویی برای یافتن محل مناسب گره، از ریشه به سمت برگ، اما در درخت هیپ، از برگ به سمت ریشه حرکت می‌کنیم.
  • در درخت جستجوی دودویی گره‌ها را برای یافتن مکان مناسب گره جدید بدون هیچگونه عمل جابجایی پیمایش می‌کنیم؛ و تنها زمانی که محل مورد نظر یافت شد عمل درج انجام می‌شود. اما در درخت هیپ، گره از همان ابتدا درج شده و سپس با جابجایی با والدهای خود، محل مناسب آن پیدا می‌شود.

نکته: با توجه به قطعه کد بالا، مرتبه اجرایی عمل درج در درخت heap از مرتبه $O(log\;n)$ است.

  

حذف گره از درخت Heap

  [برگرد بالا]

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

برای حذف گره ریشه درخت دو مرحله زیر را اجرا می‌کنیم:

1- گره ریشه را حذف و سمت راست‌ترین برگ سطح آخر را جایگزین آن می‌کنیم.

2- در صورتی که گره درج شده جدید شرط heap بودن را نقض نکند عملیات حذف تمام می‌شود. در غیر اینصورت این گره با فرزند مناسب جایگزین شده و این مرحله برای درخت جدید مجددا اجرا می‌شود.

با اجرای مرحله اول و جایگزین کردن آخرین گره آخرین سطح درخت، شرط کامل بودن درخت پایدار می‌ماند. اما عموما شرط heap بودن نقض می‌شود. در مرحله دوم، گره تازه وارد را با یکی از فرزندان خود جایگزین می‌کنیم، تا به شرط heap بودن نزدیک شویم. اما کدام فرزند؟ پاسخ را با یک مثال مشخص می‌کنم.

فرض کنید قصد داریم گره ریشه درخت min-heap زیر را حذف کنیم:

  

درخت min-heap

  

مرحله اول را اجرا کرده و گره شماره 10 را جایگزین ریشه می‌کنیم:

  

حذف گره ریشه درخت min-heap

  

شرط درخت کامل بودن همچنان برقرار است. اما درخت فعلی min-heap نیست. چرا که ریشه از هر دو فرزند خود بزرگتر است. حال مطابق مرحله دوم باید یکی از فرزندان را با والد جابجا کنیم.

اگر فرزند چپ با مقدار 8 را انتخاب کنیم:

  

انتخاب فرزند نا مناسب!!!

  

در این حالت، علاوه بر بحث مکان درست گره شماره 2 با مقدار 20، مشکل دیگری هم داریم: گره شماره 1 و 3 هم شرط min-heap را نقض می‌کنند.

اگر فرزند راست را انتخاب می‌کردیم:

  

انتخاب فرزند مناسب!!!

  

در این حالت لااقل گره‌های شماره 1 و 2 مشکلی ندارند و تنها دغدغه ما محل درست گره شماره 3 خواهد بود. پس نتیجه اینکه: در درخت min-heap، فرزندی را جایگزین والد می‌کنیم که مقدار کوچکتری داشته باشد. این مسئله در مورد max-heap به صورت عکس است. یعنی فرزندی را در درخت max-heap جایگزین می‌کنیم که مقدار بیشتری دارد.

اما هنوز گره شماره 3 شرط min-heap بودن را نقض می‌کند. پس با تکرار مرحله دوم و با توجه به نتیجه‌گیری فوق، این گره را با گره شماره 6 جابجا می‌کنیم:

  

جابجایی گره با فرزند خود برای یافتن مکان مناسب

  

به این ترتیب شرط min-heap بودن نیز برقرار شده و عملیات حذف گره به اتمام می‌رسد.

  

برنامه‌نویسی حذف گره از درخت heap

  [برگرد بالا]

این عملیات برای درخت فوق در نمایش آرایه‌ای به فرم زیر خواهد شد:

  

نمایش آرایه‌ای عملیت حذف گره از درخت heap

  

بر اساس روابط ریاضی بین شماره اندیس گره‌های والد و فرزند، تابع pop برای حذف گره ریشه به این ترتیب خواهد بود:

  

int pop(int heap[], int &n){

    int i = 1, result, temp, min;

    result = heap[1];

    heap[1] = heap[n--];

    while(2 * i <= n){

        min = 2 * i;

        if(min + 1 <= n && heap[min + 1] < heap[min])

            min++;

        if(heap[i] <= heap[min])

            break;

        temp = heap[i];

        heap[i] = heap[min];

        heap[min] = temp;

        i = min;

    }

    return result;

}

  

توجه داشته باشید که تابع pop درخت heap به فرم آرایه و تعداد عناصر آن را دریافت کرده و ضمن حذف گره ریشه، مقدار آن را باز می‌گرداند.

  

نکته: با توجه به قطعه کد بالا، مرتبه اجرایی عمل حذف گره از درخت heap از مرتبه $O(log\;n)$ است.

مسعود اقدسی فام

مسعود اقدسی فام هستم.

دانش‌آموخته علوم کامپیوتر و فعال حوزه‌های برنامه‌نویسی پایتون، علم داده و یادگیری ماشین

algs.ir/sp1n6wu     اشتراک‌گذاری در LinkedIn     اشتراک‌گذاری در Twitter     ارسال با Telegram
نوشته‌ها از این دست
       ✦   لیست پیوندی
       ✦   صف اولویت‌دار
آخرین نوشته‌ها
نوشته‌های پرمخاطب
  • 1
  • 2
  • 3
  • 4
  • 5

نام: *  

پست الکترونیک (محرمانه):

متن پیام: *  

01 02 06 07 08 09 10 11 12 13 14

• رامین
۲۲ تیر ۱۳۸۷، ساعت ۱۵:۴۸

سلام

داخل حلقه

می توان یک کمی بیشتر توضیح به من بدهید که چه موقه i/=2 صورت می گیرد ؟

مسعود اقدسی فام
۲۲ تیر ۱۳۸۷، ساعت ۲۲:۲۱

رامبن جان ما برای درج در درخت هیپ از آخرین سطح شروع می کنیم و با هر بار اجرای حلقه ما یه سطح بالاتر می ریم. همونطور هم که می دونی و در این مجموعه مقالات هم بهش اشاره شده والد گرهی با شماره i شماره ای برابر با خارج قسمت i بر 2 رو داره که در زبان ++C به صورت i/2 نمایش داده می شه.

• setare
۲۹ تیر ۱۳۸۷، ساعت ۱۳:۵۲

man barnameye hazfo ezafe az max heap ro mikham . mamnun misham age komakam konid

• setare
۲۹ تیر ۱۳۸۷، ساعت ۱۴:۰۱

man be bar nameee ehtiyaj daram ke n adade tasadofi ro begire va un ro  be max heap ezafe kone bad ertefae max heap ro peyda kone                                                               kheili furiye khahesh mikonam komakam konid

مسعود اقدسی فام
۲۹ تیر ۱۳۸۷، ساعت ۱۹:۰۲

ستاره جان بر اساس نوشته های این قسمت و قسمت سوم شما خیلی راحت می تونی برنامه دلخواهت رو بنویسی.

مسعود اقدسی فام
۲۹ تیر ۱۳۸۷، ساعت ۱۹:۰۲

ستاره خانم به قسمت دوم و سوم مقاله مراجعه کنید.

• مريم
۹ دی ۱۳۸۷، ساعت ۲۱:۰۲

لطفا الگوريتم حذف از max heapرا براي من بنويسيد

مسعود اقدسی فام
۱۲ دی ۱۳۸۷، ساعت ۲۱:۰۴

مریم خانم، در قسمت سوم این مجموعه مطالب به حذف گره max heap اشاره شده.

• مجید
۱ بهمن ۱۳۸۷، ساعت ۱۲:۱۵

خدا قوت مرد

موفق و پیروز باشید .

• مجید
۱ بهمن ۱۳۸۷، ساعت ۱۲:۵۲

مرسی

فوق العاده کمکم کرد

مسعود اقدسی فام
۱ بهمن ۱۳۸۷، ساعت ۲۰:۳۳

مجید خان، خوشحالم از اینکه این مطلب تونسته کمکی بهتون بکنه.

مسعود اقدسی فام
۱ بهمن ۱۳۸۷، ساعت ۲۰:۳۵

ممنون مجید جان از محبتت.

• میلاد
۹ بهمن ۱۳۸۷، ساعت ۰۴:۱۵

مطالب این سایت خلاصه اما خیلی مفید هستند با موضوعاتی جالب و پرطرفدار....متشکرم

مسعود اقدسی فام
۹ بهمن ۱۳۸۷، ساعت ۲۲:۲۲

از شما هم ممنونم میلاد عزیز. لطف دارید.

• عاطفه
۱۴ اسفند ۱۳۸۷، ساعت ۲۱:۳۷

سلام از این مطالب را روی سایت میزارین ممنون

اگر میشه به صورت یک ÷ک کامل در یک فایل قرار دهید.

• 437
۷ اردیبهشت ۱۳۸۹، ساعت ۱۰:۵۲

سلام حال شما؟

از این که با سما وسایتتون آشنا شدم خوشحالم

مطالبتون کامل و آموزنده بود... می خواستم خواهش کنم اگه براتون امکان داره برنامه ی درخت heap رو به زبان c# برام mail کنید

از لطفتون سباسگزارم06

0505

• mozhde
۳۰ خرداد ۱۳۸۹، ساعت ۲۳:۲۰

یک برنامه نمایش درخت max ,min  دارم خواهش میکنم کمکم کنید

• ادریس
۵ تیر ۱۳۸۹، ساعت ۱۶:۱۵

13040506060606

• Reza
۱۷ آبان ۱۳۸۹، ساعت ۰۸:۲۹

من دنبال الگوریتمی می گردم که یک درخت heap بگیره و مشخص کنه این درخت heap هست یانه ؟ در صورت امکان به ایمیل ام ارسال بفرمائید .

• arefeh
۱ بهمن ۱۳۸۹، ساعت ۱۶:۰۹

12

فردا امتحان ساختمان داده دارم مطالبتون خیلی به دردم خورد.مرسی13

• سید
۳۱ مرداد ۱۳۹۱، ساعت ۲۱:۰۶

سلام

یه سئوال داشتم؟

اگه بعد حذف و جایگزینی، موقع انتخاب گره سمت چپ یا راست هر دو تا گره مقدار یکسانی داشتن اون موقع باید چیکار کرد؟

ممنون میشم بفرستید به ایمیلم

۳۱ مرداد ۱۳۹۱، ساعت ۲۲:۱۵
• مسعود اقدسی فام

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

اگه قوانین رو می‌خونید متوجه می‌شدید که امکان ارسال جواب به ایمیل وجود نداره.

دوستان لطفا دقت کنید.

• محمد
۱ بهمن ۱۳۹۱، ساعت ۱۰:۴۰

عالی بود

واسه کنکور بهش نیاز داشتم08

• مریم
۲۴ اردیبهشت ۱۳۹۲، ساعت ۱۰:۵۹

با سلام حذف یک عنصر از درخت مکس هیپ میخواستم

• moein
۱۰ آذر ۱۳۹۲، ساعت ۱۰:۴۴

kheili mamnon babate matalebe arzeshmandi ke mizarin...06

• الهه
۲ تیر ۱۳۹۴، ساعت ۱۳:۰۱

مطلبتون عالی بود.ممنون.

• asiye
۲۶ اردیبهشت ۱۳۹۵، ساعت ۱۶:۰۱

خیلی خوب بود,ممنون

• sara
۱۲ شهریور ۱۳۹۶، ساعت ۱۲:۳۶

ممنون خیلی کاربردی بود

• محمد ساعی
۴ تیر ۱۳۹۷، ساعت ۱۱:۲۲

بسیار واضح و عالی و کاربردی !

خیلی ممنون خیلی بدرد خورد

• بنیامین
۷ تیر ۱۳۹۷، ساعت ۲۳:۲۷

سلام و بابت توضیاحات ممنون ، من دانشجوی ارشد کامپیوتر هستم و تا قبل از اینکه درگیر امتحان الگوریتم پیشرفته بشم اصلا از وجود چنین درختی قافل بودم . اولین بار که به گوشم خورد (امروز) فکر کردم الگوریتم فیبوناچی هست . تا اینکه تحقیق کردم و فهمیدم چی به چیه.

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

توی ادامه تحصیل اشتباه نکنید دوستان ، موفق باشید

• ijji
۸ فروردین ۱۳۹۸، ساعت ۱۰:۵۸

0404040404040404

• Hadis
۳۰ آذر ۱۳۹۸، ساعت ۱۴:۴۸

سلام اگه گسی میتونه توبرنامه نویسی کمکم کنه

برنامه ای بنویسید که یک عدد ازورودی دریافت کرده و max heapراهم بسازد

• خرم
۲۳ آبان ۱۳۹۹، ساعت ۱۴:۱۵

0102030405060708091011121314 کص خل هستید به والله