سلام
دوستان من ساخت درخت هیپ به روش جوانترین پدر رو از کتاب مقسمی خوندم‌ام چندین و چند مشکل برام پیش اومده
در کتاب گفته شده که اول کلیه‌ی مقادیر گره‌ها وارد یه آرایه میشه. منظور اینه که بدون مرتب سازی این اتفاق میوفته؟؟ یعنی فقط مقادیر از ورودی خونده شده؟؟؟
اگر اینطوره و اونها وارد یک آرایه میشن، در ادامه کتاب گفته حالا از پایین درخ (انتهای ارایه) شروع می کنیم و هر پدر و فزندانشون رو به شکل هیپ تنظیم میکنیم و تاکید کرده این کارور از انتهای آرایه به سمت ابتدا انجام میدیم.
و ما در الگوریتم پدر رو با اندیس j در نظر میگیره و چنین خطی در برنامه داریم:
۲*j=i
حالا سوال اصلی من.
اگر داریم از انتها آرایه رو میخونیم پس i درابتدا برابر n هست که طول ارایه هست و وقتی ضربدر ۲ هم بشه به عدد ۲n میرسیم. و اصلا نمیتونیم هیپ رو تظیم کنیم.
آیا دارم به شکل اشتباهی این الگوریتم رو تحلیل میکنم ؟؟!!
از کمکتون در طی یه مثال ممنون میشم
در مورد سوال اول اینکه: اصلا لازم نیست هیچ مرتب سازی یا کار خاصی روی اعداد ورودی انجام بشه.داده‌ها رو به همون ترتیب که می خونیم در آرایه قرار می دیم.
در مورد سوال دوم اینکه: متغیر j شماره اندیس فرزند چپ گره i رو نگه می داره یعنی i، و نه j، در هر لحظه اندیس گره پدر رو نگه می داره.
نمیدونم چرا اینقدر این الگوریت بریا من گنگ و نامفهومه. شاید برای اینکه حس میکنم باید از انتهای آرایه شروع به تنظیم درختم کنم.
در واقع نمیتونم تعدادی عدد رو برای خودم مثال بزنم و روند الگوریتم رو روش اجرا کنم.
مثلا فکر کنید از چپ به راست اعداد رو از وروی میخونیم و وارد ارایه می کنیم.
۲۰ ۱۰ ۸ ۳۰ ۹ ۱۲ ۶
حالا ما یه آرایه به شکل بالا داریم که اخرینش عدد ۲۰ هیت و در مکان ۷ ارایه‌ی ما قرار داره.
برای تبدیل این گروه به یه هیپ حداکثر باید چی کار کرد. طبق این الگوریتم؟؟ i و j اینجا به کدوم خونه‌ها اشاره دارن؟؟
روند کاری این الگوریتم خیلی ساده و سر راسته.داخل زیربرنامه‌ی heap یه حلقه وجود داره که از آخرین گره‌ی پدر(یعنی پایین ترین و سمت راست ترین پدر) شروع میکنه به درست کردنه هیپ.داخل حلقه از فراخوانی زیربرنامه‌ی adjust به صورت (adjust(A,i,n استفاده می شه.با فراخوانی زیربرنامه ajdust ،در هر بار اجرای حلقه، زیر درخت با ریشه‌ی i به هیپ تبدیل میشه و این عملیات اونقدر تکرار میشه تا به گره‌ی ریشه برسیم.
تو آرایه ای که شما مثال زدی در اولین اجرای زیربرنامه adjust، متغیر i دارای مقدار ۳ و j دارای مقدار ۶ خواهد بود.پس از اجرای زیربرنامه adjust، آرایه به صورت زیر در میاد:
۹ ۱۰ ۸ ۳۰ ۲۰ ۱۲ ۶
در اجرای بعدی حلقه i مقدار ۲ داره و j مقدار ۴ داره و پس از اجرای زیربرنامه adjust، آرایه به صورت زیر در می یاد:
۹ ۱۰ ۸ ۱۲ ۲۰ ۳۰ ۶
و در اجرای آخر حلقه هم مقدار i برابر با ۱ و مقدار j برابر با ۲ خواهد بود که بعد از فراخوانی زیربرنامه adjust، آرایه به صورت زیر در می یاد:
۹ ۱۰ ۸ ۶ ۲۰ ۱۲ ۳۰
اگر درخت آخرین آرایه ای که نوشتم رو رسم کنید می بینید که نشون دهنده‌ی یک مکس هیپ هستش.
پ.ن: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش
بی نهایت از راهنماییتون ممنونم.
خیلی خیلی ممنون
اینقدر فهمیدن این الگوریتم برام شیرین بود که نمیدونم چطوری ازتون تشکر کنم.
من خیلی اشتباه تحلیلش میکردم.
از وقت و زمانی که برای پاسخ دادن گذاشتید خیلی ممنونم
داشتم حسابی سر این الگوریتم فسفر میسوزوندم که یاد مانشت افتادم که حلاله مشکلات
عالی بود ممنون برای توضیح خوبی که دادید.
نقل قول: پ.ن: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش
اما متوجه این استدلال نمیشم!
من خودم اینجور تحلیلش کردم که حلقه for ، تکرار n و حلقه while تکرار log n !! شما چطور تحلیلش کردید؟!
(۱۷ شهریور ۱۳۹۱ ۱۲:۱۷ ق.ظ)m@hboobe نوشته شده توسط:تحلیل مرتبه زمانی این الگوریتم تو فصل heapsort کتاب CLRS اومده. بخونید تا دلیلشو بفهمید.نقل قول: پ.ن: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش
اما متوجه این استدلال نمیشم!
من خودم اینجور تحلیلش کردم که حلقه for ، تکرار n و حلقه while تکرار log n !! شما چطور تحلیلش کردید؟!