همون طوری که اطلاع دارین Heap ساختاریه که تقریبا یک درخت دودویه کامل هستش
هر آرایه ای رو میشه به شکل یک Heap در نظر گرفت
مقلا اگر آرایه ما این باشه : {2,5,3,7,6,4}
میشه آرایه رو به این شکل در نظر گرفت :
ویژگی که این درخت داره اینه که :
1_ ریشه درخت خونه اول آرایست
2_فرزند سمت چپ i خونه 2i آرایست
3_ فرزند سمت راست خونه 2i+1 آرایست
Max heap یک نوع خاص از heap هستش که داخلش هر parent از child ها بزرگ تره یعنی ساختار بالا رو الان نمیشه به عنوان max heap در نظر گرفت .
برای تبدیل heap بالا به max heap از طبقه دوم از پایین شروع می کنیم و درخت هایی کوچک تری که تشکیل میدن رو به max_heap تبدیل می کنیم
برای تبدیل درخت های کوچیک تر هم فرض می کنیم که child ها هر 2 تاشون تشکیل max_heap میدن.
شبه کد چیزایی که گفتم اینه :
Function MAX_HEAP(A)
For i=sizeof(A)/2 down to 1
Max_heapify(A,i)
Function Max_heapify(A,i)
if 2i<sizeof(A) && A[i]<A[2i]
Swap A[i] and A[2i]
Max_heapify(A,2i)
if 2i+1<sizeof(A) && A[i]<A[2i+1]
Swap A[i] and A[2i+1]
Max_heapify(A,2i+1)
مثلا مراحل بالا برای تبدیل آرایه {2,5,3,7,6,4 به این شکله :
Max_Heapify(A,3
Max_Heapify(A,2
Max_Heapify(A,1
خروجی {7,6,4,2,5,3}