Steve Jobs
28th January 2012, 11:06 PM
یکی از انواع روش‌های مرتب‌سازی، که یکی از ویژگی‌های آن، سریع‌تر بودن آن است، مرتب‌سازی از نوع هیپ (Heap) یا توده‌ای است. در این نوع مرتب‌سازی از روی داده‌ها یک درخت هیپ درست می‌کنیم كه نتیجه حاصل از پیمایش این درخت همان داده‌های اولیه ما به‌صورت مرتب شده است.
حال درخت هیپ چیست؟
درخت هیپ مانند یك درخت دودویی است که دو ویژگی منحصر‌به‌فرد دارد:
1ـ هر گره در درخت دارای یک اندیس است که مقدار ثابتی دارد و از پیش تعریف شده است. این اندیس‌ها از یک قاعده پیروی می‌کنند به این صورت که اندیس خانه سمت چپ دو برابر اندیس ریشه خود و اندیس خانه چپ دو برابر اندیس ریشه خود به‌علاوه یك است. همچنین اندیس ریشه در درخت هیپ همیشه برابر یك است.
2ـ ارتباط هر گره (نود) با ریشه خود ارتباط کوچک‌تر یا مساوی است، پس هیچ گرهی وجود ندارد که اطلاعاتش از ریشه‌اش بیشتر باشد.
حال که با درخت هیپ آشنا شدید باید آن را برای داده‌های ورودی مساله درست کنیم.
یک عنصر را به‌دلخواه انتخاب كرده و آن را به عنوان ریشه قرار می‌دهیم، سپس عناصر دیگر را طوری در درخت قرار می‌دهیم که ویژگی دوم درخت هیپ برقرار باشد. اگر هر گرهی مقدارش از ریشه بزرگ‌تر بود، مقدار آن نود را با ریشه خود عوض می‌کنیم. این کار را آنقدر ادامه می‌دهیم تا شرط دوم درخت هیپ برقرار باشد.
بگذارید این موضوع را با یک مثال توضیح دهیم. فرض کنید داده‌های زیر را داریم و می‌خواهیم آنها را به روش هیپ مرتب کنیم. نخست درخت هیپ را برای آنها رسم می‌کنیم:
53,42,35,65,75,15,25,37
ابتدا عدد 53 را به‌عنوان ریشه در نظر می‌گیریم. عدد 42 از ریشه کوچک‌تر است پس آن را به‌عنوان فرزند سمت چپ ریشه در نظر گرفته و در خانه‌ای با اندیس 2 قرار می‌دهیم و عدد 35 را در سمت راست ریشه در خانه‌ای با اندیس 3 جای می‌دهیم. حال عدد 65 را به‌عنوان فرزند چپ خانه‌ای با اندیس 2یعنی اندیس 4 قرار می‌دهیم. اما قرار دادن این عدد در این خانه شرط دوم درخت هیپ را نقض می‌کند، پس آن را در خانه‌ای با اندیس 2 یعنی ریشه خود جابه‌جا می‌کنیم. اما کماکان شرط دوم درخت هیپ نقض شده است پس آن را با ریشه خود یعنی ریشه درخت جابه‌جا می‌کنیم به این ترتیب ریشه درخت مقدار 65 فرزند چپ ریشه مقدار 53 و فرزند چپ آن هم مقدار 42 را دارد.
حالا نوبت به عنصر 75 می‌رسد. این عدد را در خانه‌ای با اندیس شماره 5 یعنی فرزند سمت راست عدد 53 قرار می‌دهیم اما این قرار دادن نیز باعث می‌شود شرط دوم درخت هیپ نقض شود پس آن‌را مانند عدد 65 آنقدر جابه‌جا می‌کنیم تا شرط دوم درخت هیپ برقرار شود. برای مابقی عناصر نیز به‌همین صورت عمل می‌كنیم.
اما نکته‌ای که باید توجه داشته باشید این است که درخت هیپ به‌صورت خطی پرمی‌شود یعنی ابتدا هر سطح از درخت پر می‌شود سپس سراغ سطح بعد می‌رویم. اگر بخواهیم این موضوع را با اندیس‌ها نشان دهیم این‌گونه است که خانه‌ها به ترتیب اندیس‌شان پر می‌شوند. مثلا اول خانه‌ای با اندیس یك سپس خانه‌ای با اندیس 2 و پس از آن خانه‌ای با اندیس 3 و ...
بسیار خب حال که درخت را ساختیم باید آن را پیمایش کنیم، اما چگونه؟
پیمایش کردن این درخت بسیار ساده است. نخست ریشه را با آخرین گره (گرهی با بیشترین اندیس مثلا اگر 10 تا داده ورودی داشته باشیم، گره 10ام آخرین گره به‌شمار می‌آید) و سپس آخرین گره که همان ریشه است را از درخت خارج می‌كنیم.
حالا شرط دوم درخت هیپ را برای درخت حاصل که تعداد گره‌‌های آن برابر تعداد داده‌های ورودی -1 است برقرار می‌کنیم و دوباره ریشه را با آخرین گره درخت حاصل جابه‌جا کرده و آخرین گره را از درخت خارج می‌كنیم و در فهرستی که برای خروجی مساله است، قرار می‌دهیم و دوباره درخت را پیمایش می‌کنیم. این کار را آنقدر ادامه می‌دهیم تا تمامی گره‌‌ها از درخت خارج شوند. فهرست حاصل از خارج شدن گره‌‌ها همان خروجی مساله یعنی مرتب شده داده‌های ورودی است.
پیچیدگی زمانی الگوریتم
این الگوریتم دارای دو مرحله است و پیچیدگی زمانی آن برابر حاصل زمانی‌است که درخت هیپ ساخته و پردازش می‌شود. پس هر بخش را جداگانه حساب می‌کنیم.
همان‌طور که گفته شد درخت هیپ یک درخت دودویی و نسبتا کامل است (ممکن است داده‌های مساله طوری نباشند که درخت هیپ حاصل درخت دودویی کامل شود) و عمق یک درخت دودویی برابر Log n در مبنای 2 و عمل قالب هم عمل جابه‌جایی است. در بدترین حالت عنصر ورودی باید تمام عمق یک درخت را طی کند تا به ریشه برسد، پس بدترین حالت برای ساختن یک درخت برابر nLog n در مبنای 2 است.
حال برای پردازش یک درخت پس از جابه‌جایی ریشه با آخرین گره، باید دوباره درخت مرتب شود. ریشه جدید که همان آخرین گره است حداکثر می‌تواند n Log n در مبنای 2 جابه‌جا شود و همین زمان هم باید صرف شود تا بزرگ‌ترین عنصر در درخت پیدا شود تا با ریشه عوض شود، یعنی در بدترین شرایط داریم 2n log n در مبنای 2.پس برای کل الگوریتم داریم 3n log n در مبنای 2 که می‌توان گفت مرتبه اجرایی این الگوریتم برابر n log n در مبنای 2است.
حال درخت هیپ چیست؟
درخت هیپ مانند یك درخت دودویی است که دو ویژگی منحصر‌به‌فرد دارد:
1ـ هر گره در درخت دارای یک اندیس است که مقدار ثابتی دارد و از پیش تعریف شده است. این اندیس‌ها از یک قاعده پیروی می‌کنند به این صورت که اندیس خانه سمت چپ دو برابر اندیس ریشه خود و اندیس خانه چپ دو برابر اندیس ریشه خود به‌علاوه یك است. همچنین اندیس ریشه در درخت هیپ همیشه برابر یك است.
2ـ ارتباط هر گره (نود) با ریشه خود ارتباط کوچک‌تر یا مساوی است، پس هیچ گرهی وجود ندارد که اطلاعاتش از ریشه‌اش بیشتر باشد.
حال که با درخت هیپ آشنا شدید باید آن را برای داده‌های ورودی مساله درست کنیم.
یک عنصر را به‌دلخواه انتخاب كرده و آن را به عنوان ریشه قرار می‌دهیم، سپس عناصر دیگر را طوری در درخت قرار می‌دهیم که ویژگی دوم درخت هیپ برقرار باشد. اگر هر گرهی مقدارش از ریشه بزرگ‌تر بود، مقدار آن نود را با ریشه خود عوض می‌کنیم. این کار را آنقدر ادامه می‌دهیم تا شرط دوم درخت هیپ برقرار باشد.
بگذارید این موضوع را با یک مثال توضیح دهیم. فرض کنید داده‌های زیر را داریم و می‌خواهیم آنها را به روش هیپ مرتب کنیم. نخست درخت هیپ را برای آنها رسم می‌کنیم:
53,42,35,65,75,15,25,37
ابتدا عدد 53 را به‌عنوان ریشه در نظر می‌گیریم. عدد 42 از ریشه کوچک‌تر است پس آن را به‌عنوان فرزند سمت چپ ریشه در نظر گرفته و در خانه‌ای با اندیس 2 قرار می‌دهیم و عدد 35 را در سمت راست ریشه در خانه‌ای با اندیس 3 جای می‌دهیم. حال عدد 65 را به‌عنوان فرزند چپ خانه‌ای با اندیس 2یعنی اندیس 4 قرار می‌دهیم. اما قرار دادن این عدد در این خانه شرط دوم درخت هیپ را نقض می‌کند، پس آن را در خانه‌ای با اندیس 2 یعنی ریشه خود جابه‌جا می‌کنیم. اما کماکان شرط دوم درخت هیپ نقض شده است پس آن را با ریشه خود یعنی ریشه درخت جابه‌جا می‌کنیم به این ترتیب ریشه درخت مقدار 65 فرزند چپ ریشه مقدار 53 و فرزند چپ آن هم مقدار 42 را دارد.
حالا نوبت به عنصر 75 می‌رسد. این عدد را در خانه‌ای با اندیس شماره 5 یعنی فرزند سمت راست عدد 53 قرار می‌دهیم اما این قرار دادن نیز باعث می‌شود شرط دوم درخت هیپ نقض شود پس آن‌را مانند عدد 65 آنقدر جابه‌جا می‌کنیم تا شرط دوم درخت هیپ برقرار شود. برای مابقی عناصر نیز به‌همین صورت عمل می‌كنیم.
اما نکته‌ای که باید توجه داشته باشید این است که درخت هیپ به‌صورت خطی پرمی‌شود یعنی ابتدا هر سطح از درخت پر می‌شود سپس سراغ سطح بعد می‌رویم. اگر بخواهیم این موضوع را با اندیس‌ها نشان دهیم این‌گونه است که خانه‌ها به ترتیب اندیس‌شان پر می‌شوند. مثلا اول خانه‌ای با اندیس یك سپس خانه‌ای با اندیس 2 و پس از آن خانه‌ای با اندیس 3 و ...
بسیار خب حال که درخت را ساختیم باید آن را پیمایش کنیم، اما چگونه؟
پیمایش کردن این درخت بسیار ساده است. نخست ریشه را با آخرین گره (گرهی با بیشترین اندیس مثلا اگر 10 تا داده ورودی داشته باشیم، گره 10ام آخرین گره به‌شمار می‌آید) و سپس آخرین گره که همان ریشه است را از درخت خارج می‌كنیم.
حالا شرط دوم درخت هیپ را برای درخت حاصل که تعداد گره‌‌های آن برابر تعداد داده‌های ورودی -1 است برقرار می‌کنیم و دوباره ریشه را با آخرین گره درخت حاصل جابه‌جا کرده و آخرین گره را از درخت خارج می‌كنیم و در فهرستی که برای خروجی مساله است، قرار می‌دهیم و دوباره درخت را پیمایش می‌کنیم. این کار را آنقدر ادامه می‌دهیم تا تمامی گره‌‌ها از درخت خارج شوند. فهرست حاصل از خارج شدن گره‌‌ها همان خروجی مساله یعنی مرتب شده داده‌های ورودی است.
پیچیدگی زمانی الگوریتم
این الگوریتم دارای دو مرحله است و پیچیدگی زمانی آن برابر حاصل زمانی‌است که درخت هیپ ساخته و پردازش می‌شود. پس هر بخش را جداگانه حساب می‌کنیم.
همان‌طور که گفته شد درخت هیپ یک درخت دودویی و نسبتا کامل است (ممکن است داده‌های مساله طوری نباشند که درخت هیپ حاصل درخت دودویی کامل شود) و عمق یک درخت دودویی برابر Log n در مبنای 2 و عمل قالب هم عمل جابه‌جایی است. در بدترین حالت عنصر ورودی باید تمام عمق یک درخت را طی کند تا به ریشه برسد، پس بدترین حالت برای ساختن یک درخت برابر nLog n در مبنای 2 است.
حال برای پردازش یک درخت پس از جابه‌جایی ریشه با آخرین گره، باید دوباره درخت مرتب شود. ریشه جدید که همان آخرین گره است حداکثر می‌تواند n Log n در مبنای 2 جابه‌جا شود و همین زمان هم باید صرف شود تا بزرگ‌ترین عنصر در درخت پیدا شود تا با ریشه عوض شود، یعنی در بدترین شرایط داریم 2n log n در مبنای 2.پس برای کل الگوریتم داریم 3n log n در مبنای 2 که می‌توان گفت مرتبه اجرایی این الگوریتم برابر n log n در مبنای 2است.