Cách hoạt động của heap trong thuật toán sắp xếp?

[Long_Long]

Cho dãy số như sau: 15, 37, 12, 58, 7, 24, 67
Nếu các bước tạo Heap từ dãy số trên.
sao đây mọi người trước giờ chỉ code thôi bây giờ cô bảo phải làm cái này, giờ e phải làm sao đây hic

[vietha0996 (Ha)]

Coi mảng a[] chưa dãy số có chỉ số bắt đầu từ 1…
Số phần tử n = 7 -> j = (int) n/2 = 3.

Ta tạo heap từ phần tử a[j] ngược lên a[1], từ a[4] trở đi là các lá.
vun đống tại a[3] -> 15, 37, 67, 58, 7, 24, 12.
tại a[2] -> 15, 58, 67, 37, 7, 24, 12.
tại a[1] -> 67, 58, 24, 37, 7, 15, 12. (vì trong các con của a[3] có a[6] = 24 > a[1] = 15)
Heap : 67, 58, 24, 37, 7, 15, 12.

Update thêm cái Tree Structure cho dễ hiểu.

Để hiểu rõ về heap sort thì bạn làm theo cấu trúc cây (Tree Structure) sẽ dễ hiểu hơn là đọc công thức, hoặc xem code.

dãy ban đầu, vun tại a[3] = 12 :

		 		(15)
		               /    \
			   (37)      (12)		vì 12 < max(24, 67) -> đổi chỗ 12 và 67
                          /   \     /    \		được dãy bên dưới
                       (58)   (7) (24)   (67)  
          
vun tiếp a[2]
 			        (15)
			       /    \
		           (37)      (67)		vì 37 < max(58, 7) -> đổi chỗ 37 và 58
                           /   \     /   \		được dãy bên dưới
                        (58)   (7) (24)   (12)  
              
                  

vun tiep a[1] 			(15)
	                       /    \
			   (58)      (67)		vì 15 < max(58, 67) -> đổi chỗ 15 và 67
                          /   \     /    \		nhưng vẫn chưa xong vì trong các con của
                       (37)   (7) (24)    (12)  	67 có phần tử > 15 nên ta đổi chỗ
                                                        phần từ đó với 15
												
							-> thằng con không được lớn hơn thằng bố
							   nếu con lớn hơn cho lên làm bố, bố xuống làm con              
              
dãy cuối cùng	 		(67)
			       /    \
			   (37)      (24)
                          /   \     /    \
                       (58)   (7) (15)    (12)  

-> Heap : 67, 37, 24, 58, 7, 15, 12