ساختن max heap از روی آرایه

Question

سلام دوستان

چطوری میشه ساختار max heap رو از روی یک آرایه غیر مرتب ساخت ؟

Answer 1

همون طوری که اطلاع دارین 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}

Answer 2

کد ++C :

#include <iostream>
#include <vector>

void maxHeapify(std::vector<int>& arr, int loc)
{
	const int parentLoc = loc;
	const int leftChildLoc = 2 * loc + 1;
	const int rightChildLoc = 2 * loc + 2;

	if (leftChildLoc<arr.size()&&arr[parentLoc] < arr[leftChildLoc])//left child
	{
		std::swap(arr[parentLoc], arr[leftChildLoc]);
		maxHeapify(arr, leftChildLoc);
	}
	if (rightChildLoc<arr.size() && arr[parentLoc] < arr[rightChildLoc])//right child
	{
		std::swap(arr[parentLoc], arr[rightChildLoc]);
		maxHeapify(arr, rightChildLoc);
	}

}
void maxHeap(std::vector<int>& arr)
{
	for (int i = arr.size() / 2; i >= 0; i--)
		maxHeapify(arr, i);
}

int main()
{
	std::vector<int> arr = { 2, 5, 3, 7, 6, 4 };

	maxHeap(arr);

	for (const auto& elem : arr)
		std::cout << elem;//7 6 4 2 5 3
}