Heap¶
Heap یا پشته به دو دسته min heap و max heap تقسیم می شود. در min heap یا پشته کمترین مقدار هر راس از بچه هاش کوچک تر است و در max heap یا پشته بیشترین هر راس از بچه هاش بزرگتر است. در heap برگ ها یا در دو طبقه آخر قرار دارند.
(Insertion) اضافه کردن¶
مراحل اضافه کردن x در min heap به شکل زیر است( در max heap مراحل مشابه است) :
- x را در آخرین طبقه به یکی از راس های طبقه یکی مانده به آخر که هنوز دو بچه ندارد وصل میکنیم و اگر چنین راسی وجود نداشت یک طبقه جدید اضافه می کنیم و x را به یکی از راس های طبقه بالایش وصل می کنیم.
- حال x را با پدرش مقایسه می کنیم و اگر مقدارش از پدرش کمتر بود جاشون رو عوض میکنم. این مرحله را تا جایی ادامه می دهیم تا یا x ریشه شود یا از مقدار پدرش بزرگ تر باشد.
(Deletion) حذف کردن¶
مراحل حذف کردن در min heap به شکل زیر است( در max heap مراحل مشابه است) :
- مقدار ریشه را با مقدار یکی از برگ های طبقه آخر عوض می کنیم و آن برگ را حذف می کنیم. در این مرحله مقدار ریشه عوض شده است بنابراین باید چک کنیم که شرایط min heap را داشته باشد،فرض کنید y مقدار کمتر بین بچه های ریشه باشد، اگر ریشه از y بزرگ تر بود جای y و ریشه را عوض میکنیم و حال این مرحله را برای زیر درختی که ریشه در آن قرار دارد انجام می دهیم.
این کتاب توسط مشارکت کنندگان شاززز به وجود آمده است.
این کتاب عمومی است و تحت پروانه cc-by-sa در دسترس است.
آخرین به روز رسانی در ژوئن 09, 2022.
