روند کاری این الگوریتم خیلی ساده و سر راسته.داخل زیربرنامه‌ی heap یه حلقه وجود داره که از آخرین گره‌ی پدر(یعنی پایین ترین و سمت راست ترین پدر) شروع میکنه به درست کردنه هیپ.داخل حلقه از فراخوانی زیربرنامه‌ی adjust به صورت (adjust(A,i,n استفاده می شه.با فراخوانی زیربرنامه ajdust ،در هر بار اجرای حلقه‌، زیر درخت با ریشه‌ی i به هیپ تبدیل میشه و این عملیات اونقدر تکرار میشه تا به گره‌ی ریشه برسیم.

تو آرایه ای که شما مثال زدی در اولین اجرای زیربرنامه adjust‌، متغیر i دارای مقدار ۳ و j دارای مقدار ۶ خواهد بود.پس از اجرای زیربرنامه adjust‌، آرایه به صورت زیر در میاد:
۹ ۱۰ ۸ ۳۰ ۲۰ ۱۲ ۶
در اجرای بعدی حلقه i مقدار ۲ داره و j مقدار ۴ داره و پس از اجرای زیربرنامه adjust‌، آرایه به صورت زیر در می یاد:
۹ ۱۰ ۸ ۱۲ ۲۰ ۳۰ ۶
و در اجرای آخر حلقه هم مقدار i برابر با ۱ و مقدار j برابر با ۲ خواهد بود که بعد از فراخوانی زیربرنامه adjust‌، آرایه به صورت زیر در می یاد:
۹ ۱۰ ۸ ۶ ۲۰ ۱۲ ۳۰

اگر درخت آخرین آرایه ای که نوشتم رو رسم کنید می بینید که نشون دهنده‌ی یک مکس هیپ هستش.

پ.ن‌: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش

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

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

۲۰ ۱۰ ۸ ۳۰ ۹ ۱۲ ۶

حالا ما یه آرایه به شکل بالا داریم که اخرینش عدد ۲۰ هیت و در مکان ۷ ارایه‌ی ما قرار داره.
برای تبدیل این گروه به یه هیپ حداکثر باید چی کار کرد. طبق این الگوریتم؟؟ i و j اینجا به کدوم خونه‌ها اشاره دارن؟؟

بی نهایت از راهنماییتون ممنونم.

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

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

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

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

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

نقل قول: پ.ن‌: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش

اما متوجه این استدلال نمیشم!

من خودم اینجور تحلیلش کردم که حلقه for ، تکرار n و حلقه while تکرار log n !! شما چطور تحلیلش کردید؟!

(۱۷ شهریور ۱۳۹۱ ۱۲:۱۷ ق.ظ)m@hboobe نوشته شده توسط:  

نقل قول: پ.ن‌: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش

اما متوجه این استدلال نمیشم!

من خودم اینجور تحلیلش کردم که حلقه for ، تکرار n و حلقه while تکرار log n !! شما چطور تحلیلش کردید؟!

تحلیل مرتبه زمانی این الگوریتم تو فصل heapsort کتاب CLRS اومده. بخونید تا دلیلشو بفهمید.