خبرگزاری آیصد (جدیدترین و جذاب ترین اخبار ایران و جهان)

نشر توسط:admin Views 40 تاریخ : 2 خرداد 1395

مرتب سازی توده ای  یا کپه(Heap Sort):

برای بررسی این نوع از مرتب سازی ابتدا باید با درختheap آشنا شویم.

درخت Heap:یک درخت دودویی تقریباً کامل است،درخت Max Heap وMin Heap

درخت max heap:در این درخت هر نود یا گره از فرزندانش بزرگتر یا مساویست.

درخت Min heap:در این درخت هر نود یا گره از فرزندانش کوچکتر یا مساوست.

در مرتب سازی توده ای داده ها را در یک درخت heap min قرار داده  هر بار مقدار موجود در ریشه ی درخت را برداشته و آخرین گره قرار داده شده در درخت را جایگزین آن می کنیم.با این کار آرایش درخت heap به هم خورده و باید دوباره درخت heap را به روز کنیم.این کار را(برداشتن اعداد) آنقدر انجام می دهیم تا همه ی داده ها یکی یکی به جای ریشه قرار بگیرند.این گونه داده ها از بزرگ به کوچک از درخت heap خارج شده و در یک حافظه قرار می گیرند.  

توجه:در درخت heap max یافتن بیشترین مقدار و در درخت min heap یافتن کمترین مقدار بسیار آسان است.

برای پیاده سازی درخت heap  آرایه بهترین ساختمان داده است.چرا که در درخت heap شما نیاز دارید که بارها درخت را بالا به پایین یا پایین به بالا پیمایش کنید.نتیجاً در آرایه این کار راحتر از ساختمان داده ای همچون لینک لیست است.

در این صورت داده ها به ترتیب در آرایه قرار می گیرند.مسلماً اولین خانه ی آرایه مقدار ریشه را داراست.فرزند سمت چپ و سمت راست به ترتیب در خانه هایی با ایندکس2i و2i+1 قرار می گیرند.

خانه ی صفرم آرایه را خالی بگذارید تا رابطه ی بین ایندکس ها به هم نخورد.در این صورت ایجاد درخت heap آسان می شود.

توجه : شکل بالا یک درخت heap min است.که نحوه ی قرارگیری داده ها در آرایه را نشان می دهد.نحوه ی مرتب سازی را نمایش نمی دهد.

بررسی مرتبه ی زمانی این الگوریتم در بهترین و بدترین حالت:

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

بررسی مرتبه زمانی:

فرض کنید یک درخت max heap داریم.مسلماً بزرگترین عدد در ریشه قرار گرفته.آن عدد را برمی داریم و آخرین نود را جایگزین آن می کنیم.حال باید دوباره درخت خود را heap کنیم. بدترین حالت زمانی رخ می دهد که طی مقایسه ی عدد قرار گرفته در ریشه با سایر نودها،عدد(ریشه) در پایین ترین سطح درخت قرار بگیرد.پس اگر ارتفاع درخت1-[(log(n+1] باشد،تعداد مقایسه های انجام شده logn است.نتیجاً برای nنود تعداد کل مقایسه ها nlogn است.

توجه:مبنای لگاریتم دو است.

مرتبه ی زمانی:

(θ(nlogn

heapsort.zip">دانلود