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 و ریشه را عوض میکنیم و حال این مرحله را برای زیر درختی که ریشه در آن قرار دارد انجام می دهیم.