Dãy gồm các số sau: 8, 12, 20, 04, 27, 22, 25, 05, 15 : Dựng cây nhị phân: cây nhị phân hoàn chỉnh

tải về 15.22 Kb.

Chuyển đổi dữ liệu	29.11.2023
Kích	15.22 Kb.
	#55810

Cay

/ \ / \ 6 14 10 20 / \ 2 3: Sắp xếp bằng Heap Sort

BÀI TẬP
Dãy gồm các số sau: 28, 12, 20, 04, 27, 22, 25, 05, 15
1 :Dựng cây nhị phân:
cây nhị phân hoàn chỉnh
6
/ \
1 19
/ \ / \
96 14 10 20
/ \
26 2

2 :Hiệu chỉnh về Heap
96
/ \
26 19
/ \ / \
6 14 10 20
/ \

3: Sắp xếp bằng Heap Sort

Hoán đổi nút cuối cùng với nút gốc của cây và giảm kích thước cây đi 1.
2
/ \
26 19
/ \ / \
6 14 10 20
/
1

Hiệu chỉnh cây với nút gốc mới để đảm bảo tính chất Heap.
26
/ \
2 19
/ \ / \
6 14 10 20
/
1
Lặp lại quá trình trên cho đến khi cây chỉ còn một nút.
20
/ \
2 19
/ \ / \
6 14 10
/
1
Mảng đã được sắp xếp theo thứ tự tăng dần từ cuối lên đầu.
Dãy số đã được sắp xếp theo phương pháp Heap Sort là: 1, 2, 6, 10, 14, 19, 20, 26, 96.

tải về 15.22 Kb.

Chia sẻ với bạn bè của bạn: