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

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

ارسال:
  

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 اومده. بخونید تا دلیلشو بفهمید.



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۷ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  جزوه اسکن شده " سیستم های توزیع شده " دکتر پدرام arash691 ۸ ۱۴,۰۹۸ ۱۰ آذر ۱۴۰۱ ۰۲:۵۵ ق.ظ
آخرین ارسال: negarrah
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۸ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  دانلود وویس درس سیستم های توزیعی دکتر پدرام x86 ۴۴ ۳۹,۱۲۸ ۲۱ خرداد ۱۳۹۹ ۰۸:۳۱ ب.ظ
آخرین ارسال: محسن افضلی
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  تعداد روش های نوشتن عدد n ss311 ۲ ۲,۹۵۴ ۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ
آخرین ارسال: ss311
  تعداد درخت فراگیر ss311 ۰ ۲,۰۵۷ ۰۶ بهمن ۱۳۹۸ ۰۵:۰۶ ب.ظ
آخرین ارسال: ss311

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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