تالار گفتمان مانشت

سلام.
به منظور سورت صعودی یک ارایه از هیپ سورت استفاده نموده و ماکس هیپ میسازیم. در مورد زمان اجرا این الگوریتم کدام گزینه صحیح است؟؟
1- اگر آرایه از ابتدا به صورت صعودی مرتب باشد زمان مورد نیاز ( O(n است.
2- اگر آرایه از ابتدا به صورت نزولی مرتب باشد زمان مورد نیاز ( O(n است.
3- اگر آرایه از ابتدا به صورت نزولی مرتب باشد زمان مورد نیاز n^2logn است.
4- اگر آرایه از ابتدا به صورت صعودی مرتب باشد زمان مورد نیاز nlogn است.

--سوال اولم اینه که مگه برای مرتب کردن صعودی از مین هیپ استفاده نمیکردیم؟؟ چرا اینجا گفته ماکس هیپ؟!
--سوال دومم هم اینه که چرا گزینه 2 درست نیست؟ گزینه 4 رو میدونم درسته...

واسه گزینه 2:
در حالت عادی میدونیم که وقتی در هیپ درج میکنیم باید تا جای ممکن با پدرش تعویض کنیم تا هیپ باقی بمونه. هزینه درج 1 و هزینه مرتب کردن logn میشه و هزینه n بار درج (و در صورت نیاز جابجایی برای مرتب کردن) میشه nlogn
اما اینجا
میدونیم که یک آرایه نزولی، یک ماکس هیپه. خوب وقتی از اول مرتب شده رو داریم فقط کافیه هزینه درج رو بپردازیم نه هزینه مرتب کردن رو. که هزینه درج هر عنصر از یک آرایه مرتب نزولی در یک ماکس هیپ هم میشه( O(1
و برای درج n تا عنصر میشه ( O(n
درسته؟؟

شاید منظور سوال این بوده که که ابتدا صعودیش کنیم بعد بریزیمش توی ماکس هیپ که نزولی بشه.

Sent from my SM-T210R using Tapatalk

الگوریتم هیپ سورت از دو مرحله تشکیل شده :

الف) یک درخت هیپ از عناصر آرایه A بسازیم.
ب) عنصر ریشه H را به طور مکرر حذف کنیم.
شما در مورد گزینه 2 فقط مرحله الف رو در نظر گرفتید... البته اگه آرایه نزولی باشه با ( O(n میشه درخت ماکس هیپ رو ساخت اما موقع حذف کردن و بازسازی صعودی آرایه گزینه 2 فایده ای نداره و دوباره آرایه مثل اولش میشه.. به نظر من گزینه 2 اصلا به درد نمیخوره... شاید به همین خاطره که برای مرتب سازی صعودی از مین هیپ استفاده میکنن.

(02 دى 1392 07:38 ب.ظ)mhd3 نوشته شده توسط: [ -> ]--سوال اولم اینه که مگه برای مرتب کردن صعودی از مین هیپ استفاده نمیکردیم؟؟

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

در واقع تو این روش شما اعداد رو (مثلا) در خروجی چاپ نمی‌کنید بلکه اعداد به صورت مرتب در خود همون آرایه ورودی قرار می‌گیرن.

(02 دى 1392 11:11 ب.ظ)آنجلا نوشته شده توسط: [ -> ]الگوریتم هیپ سورت از دو مرحله تشکیل شده :

الف) یک درخت هیپ از عناصر آرایه A بسازیم.
ب) عنصر ریشه H را به طور مکرر حذف کنیم.
شما در مورد گزینه ۲ فقط مرحله الف رو در نظر گرفتید...

مرسی عزیزم.
خیلی لطف کردی.
آره، درست میگی. من اصلا به حذف توجه نکرده بودم.
ممنون

(03 دى 1392 12:11 ق.ظ)mfXpert نوشته شده توسط: [ -> ]

(02 دى 1392 07:38 ب.ظ)mhd3 نوشته شده توسط: [ -> ]--سوال اولم اینه که مگه برای مرتب کردن صعودی از مین هیپ استفاده نمیکردیم؟؟

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

در واقع تو این روش شما اعداد رو (مثلا) در خروجی چاپ نمی‌کنید بلکه اعداد به صورت مرتب در خود همون آرایه ورودی قرار می‌گیرن.

بله امتحان کردم.
خیلی ممنون.