زمان کنونی: ۲۵ شهریور ۱۳۹۸, ۰۲:۴۶ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

ساخت درخت هیپ به روش جوانترین پدر

ارسال:
  

shadi پرسیده:

ساخت درخت هیپ به روش جوانترین پدر

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

و ما در الگوریتم پدر رو با اندیس j در نظر میگیره و چنین خطی در برنامه داریم:

۲*j=i
حالا سوال اصلی من.
اگر داریم از انتها آرایه رو میخونیم پس i درابتدا برابر n هست که طول ارایه هست و وقتی ضربدر ۲ هم بشه به عدد ۲n میرسیم. و اصلا نمیتونیم هیپ رو تظیم کنیم.

آیا دارم به شکل اشتباهی این الگوریتم رو تحلیل میکنم ؟؟!!

از کمکتون در طی یه مثال ممنون میشم

۱
ارسال:
  

mfXpert پاسخ داده:

RE: ساخت درخت هیپ به روش جوانترین پدر

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

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

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

ساخت درخت هیپ به روش جوانترین پدر

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

۰
ارسال:
  

shadi پاسخ داده:

ساخت درخت هیپ به روش جوانترین پدر

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

۲۰ ۱۰ ۸ ۳۰ ۹ ۱۲ ۶

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

۰
ارسال:
  

shadi پاسخ داده:

ساخت درخت هیپ به روش جوانترین پدر

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

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

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

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

۰
ارسال:
  

m@hboobe پاسخ داده:

ساخت درخت هیپ به روش جوانترین پدر

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

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

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

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

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

۰
ارسال:
  

mfXpert پاسخ داده:

ساخت درخت هیپ به روش جوانترین پدر

(۱۷ شهریور ۱۳۹۱ ۱۲:۱۷ ق.ظ)m@hboobe نوشته شده توسط:  
نقل قول: پ.ن‌: تو کتاب مقسمی نوشته که این الگوریتم از مرتبه (O(nlogn هستش.اما این یک مرتبه زمانی خوب برای این الگوریتم نیست.در اصل مرتبه‌ی زمانی این الگوریتم (O(n هستش

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

من خودم اینجور تحلیلش کردم که حلقه for ، تکرار n و حلقه while تکرار log n !! شما چطور تحلیلش کردید؟!Huh
تحلیل مرتبه زمانی این الگوریتم تو فصل heapsort کتاب CLRS اومده. بخونید تا دلیلشو بفهمید.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه یافتن پیمایش پس ترتیب یک درخت با داشتن پیمایش پیش ترتیب آن miss_samira ۲ ۲,۵۷۸ ۰۸ اسفند ۱۳۹۳ ۰۹:۵۶ ب.ظ
آخرین ارسال: shayesteb
Sad روش یادگیری پیچیدگی زمانی ؟ elhameli ۱۱ ۲۱,۲۵۱ ۰۲ آبان ۱۳۹۱ ۱۰:۱۶ ب.ظ
آخرین ارسال: javadem
  سوالاتی در مورد درخت Heap hejran_ha ۴ ۷,۸۳۵ ۱۵ مهر ۱۳۹۱ ۰۶:۰۴ ب.ظ
آخرین ارسال: hejran_ha
  با عناصر تکراری در درخت هافمن چه می کنید؟ bijibuji ۱۳ ۳,۶۵۳ ۰۸ تیر ۱۳۹۱ ۰۶:۲۵ ق.ظ
آخرین ارسال: Masoud05
  نکات - مفاهیم اولیه درخت Masoud05 ۵ ۸,۶۴۱ ۰۶ تیر ۱۳۹۱ ۰۱:۰۰ ب.ظ
آخرین ارسال: cormen
  نکات - درخت دودویی ویژه Masoud05 ۳ ۵,۹۵۲ ۱۰ اردیبهشت ۱۳۹۱ ۱۰:۵۴ ب.ظ
آخرین ارسال: Masoud05
  تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است netsupport ۵ ۲,۷۶۶ ۰۲ بهمن ۱۳۹۰ ۰۶:۰۱ ب.ظ
آخرین ارسال: fatima1537
  یک سوال از درخت Aurora ۱۲ ۴,۶۳۰ ۰۸ دى ۱۳۹۰ ۰۲:۰۲ ق.ظ
آخرین ارسال: Lantern
  سوال از درس ساختمان داده [درخت] Mostak ۷ ۶,۲۹۳ ۱۲ آذر ۱۳۹۰ ۱۲:۲۱ ب.ظ
آخرین ارسال: انرژی مثبت
  یه مشکل در محاسبه ارتفاع درخت bahar ۱۹ ۴,۳۱۴ ۰۳ بهمن ۱۳۸۹ ۰۷:۰۵ ب.ظ
آخرین ارسال: ف.ش

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close