S p x p vun đ ngắ ế ố
Heap sort
S p x p vun đ ng - Heap sort ắ ế ố
•Khi tìm ph n t nh nh t b c i, ph ng pháp s p ầ ử ỏ ấ ở ướ ươ ắ
x p ch n tr c ti p không t n d ng đ c các thông tin ế ọ ự ế ậ ụ ượ
đã có đ c do các phép so sánh b c i-1. Vì lý do ượ ở ướ
trên ng i ta tìm cách xây d ng m t thu t toán s p x p ườ ự ộ ậ ắ ế
có th kh c ph c nh c đi m này.ể ắ ụ ượ ể
•M u chôt đ gi i quy t v n đ v a nêu là ph i tìm ra ấ ể ả ế ấ ề ừ ả
đ c m t c u trúc d li u cho phép tích lũy các thông ượ ộ ấ ữ ệ
tin v s so sánh giá tr các ph n t trong qua trình s p ề ự ị ầ ử ắ
x p. ế
•Gi s d li u c n s p x p đ c b trí theo quan h so ả ử ữ ệ ầ ắ ế ượ ố ệ
sánh và t o thành s đ d ng cây nh sau :ạ ơ ồ ạ ư
heap
Các ph n t t t nh t (x u nh t) s đ c ầ ử ố ấ ấ ấ ẽ ượ
d i lên trênờ
C u trúc heapấ
•Heap là m t c u trúc d li u d ng hình ộ ấ ữ ệ ạ
cây có tính ch t sau:ấ
•M i m t ph n t s có nhi u nh t 2 ph n ổ ộ ầ ử ẽ ề ấ ầ
t là con c a nó (ph n t liên đ i)ử ủ ầ ử ớ
•B t kỳ Ph n t trên (cha) s có giá tr ấ ầ ử ở ẽ ị
l n h n giá tr 2 ph n t con c a nó ớ ơ ị ầ ử ủ
•Ph n t đ u (ph n t g c) s là ph n t ầ ử ầ ầ ử ố ẽ ầ ử
có giá tr l n nh t trong heapị ớ ấ
C u trúc heapấ
16
12 14
11 4
67 12
9 13
80 103
5
12
cha
11
Con
(ph n t liên đ i)ầ ử ớ 4
Con
(ph n t liên đ i)ầ ử ớ
12 > 11, 12 > 4
16
g cố
16 là giá tr l n nh t trong ị ớ ấ
heap