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

»    مسابقه‌ی برنامه‌نویسی CodeCup 2018

»    دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

»    مسئله‌ی انتخابات

درخت Heap - الگوریتمستان
الگوریتمستان
6514.485.00
  »  

       

آشنایی با درخت Heap (هیپ، هرم یا کپه) به عنوان یکی از ساختمان های داده پرکاربرد و بررسی روش ساخت، درج گره و حذف گره و ارائه‌ی کد نمونه به زبان برنامه‌نویسی ++C

http://www.aachp.ir آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «آشنایی با درخت Heap» تیر ماه 1387 از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان) منتشر شده بود.


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

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

  [بازگشت به فهرست]

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

      

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

      

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

      

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

      

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

  [بازگشت به فهرست]

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

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

      

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

      

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

    فرض کنیم توابع 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])
10             break;
11         temp = heap[i];
12         heap[i] = heap[min];
13         heap[min] = temp;
14         i = min;
15     }
16     return result;
17 }

      

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

      

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


نوشته‌های مرتبط
        معرفی انواع ظرف‌ها (نگهدارنده‌ها - containers) در زبان برنامه‌نویسی ++C
        آشنایی با درخت جستجوی دودویی (Binary Search Tree) و عملیات جستجو و درج و حذف گره
        معرفی فایل سرآیند algorithm از کتابخانه قالب استاندارد زبان برنامه‌نویسی ++C به همراه نمونه کد
        آشنایی با صف اولویتی (Priority Queue)، کاربردها و نحوه‌ی پیاده‌سازی آن
        معرفی الگوریتم جستجوی اول سطح (BFS) برای پیمایش گراف و کاربردهای آن به همراه قطعه کد به زبان برنامه‌نویسی ++C
        بررسی مفهوم و روش پیاده‌سازی لیست پیوندی و توابع مرتبط آن به زبان برنامه‌نویسی ++C
        آشنایی با روش مرتب‌سازی هرمی (Heap Sort)
پیوند کوتاه صفحه دسته‌بندی
امتیاز نوشته
  • 1
  • 2
  • 3
  • 4
  • 5
ارسال پیام

نام: *  

پست الکترونیک:

وبگاه:

متن پیام: *

right 01 02 03 04 05 06 07 08 09 10 11 12 13 14 left

 


» asiye

یکشنبه، ۲۶ اردیبهشت ماه ۱۳۹۵، ساعت ۱۶:۰۱
خیلی خوب بود,ممنون

» الهه

سه‌شنبه، ۲ تیر ماه ۱۳۹۴، ساعت ۱۳:۰۱
مطلبتون عالی بود.ممنون.

» moein

یکشنبه، ۱۰ آذر ماه ۱۳۹۲، ساعت ۱۰:۴۴
kheili mamnon babate matalebe arzeshmandi ke mizarin...06

» مریم

سه‌شنبه، ۲۴ اردیبهشت ماه ۱۳۹۲، ساعت ۱۰:۵۹
با سلام حذف یک عنصر از درخت مکس هیپ میخواستم

» محمد

یکشنبه، ۱ بهمن ماه ۱۳۹۱، ساعت ۱۰:۴۰
عالی بود
واسه کنکور بهش نیاز داشتم08

» سید

سه‌شنبه، ۳۱ مرداد ماه ۱۳۹۱، ساعت ۲۱:۰۶
سلام
یه سئوال داشتم؟
اگه بعد حذف و جایگزینی، موقع انتخاب گره سمت چپ یا راست هر دو تا گره مقدار یکسانی داشتن اون موقع باید چیکار کرد؟
ممنون میشم بفرستید به ایمیلم


سه‌شنبه، ۳۱ مرداد ماه ۱۳۹۱، ساعت ۲۲:۱۵
مسعود:
فرقی نمی‌کنه کدوم یکی باشه. البته اگه اطلاعاتی در مورد فاصله تا عمق هر گره در دسترس باشه، بهتره با گرهی جایگزین بشه که تا عمق فاصله‌ی کمتری داره.
اگه قوانین رو می‌خونید متوجه می‌شدید که امکان ارسال جواب به ایمیل وجود نداره.

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

» arefeh

جمعه، ۱ بهمن ماه ۱۳۸۹، ساعت ۱۶:۰۹
12
فردا امتحان ساختمان داده دارم مطالبتون خیلی به دردم خورد.مرسی13

» Reza

دوشنبه، ۱۷ آبان ماه ۱۳۸۹، ساعت ۰۸:۲۹
من دنبال الگوریتمی می گردم که یک درخت heap بگیره و مشخص کنه این درخت heap هست یانه ؟ در صورت امکان به ایمیل ام ارسال بفرمائید .

» ادریس

شنبه، ۵ تیر ماه ۱۳۸۹، ساعت ۱۶:۱۵
13040506060606

» mozhde

یکشنبه، ۳۰ خرداد ماه ۱۳۸۹، ساعت ۲۳:۲۰
یک برنامه نمایش درخت max ,min  دارم خواهش میکنم کمکم کنید

» 437

سه‌شنبه، ۷ اردیبهشت ماه ۱۳۸۹، ساعت ۱۰:۵۲
سلام حال شما؟
از این که با سما وسایتتون آشنا شدم خوشحالم
مطالبتون کامل و آموزنده بود... می خواستم خواهش کنم اگه براتون امکان داره برنامه ی درخت heap رو به زبان c# برام mail کنید
از لطفتون سباسگزارم06

0505