HEAP SORT
HEAP SORT
Heap sort
Heap sort
Gii thiu:
- Sp xp vun "ng (heapsort) là 1 trong các phương
pháp sp xp ch$n (ch$n phn tln nht (ho>c
nh?nht)>t vào cu"i (ho>c u) danh sách, sau
ó tip tc vi phn còn li ca danh sách).
- Sp xp ch$n có phc tp O(n
2
). Nhưng
Heapsort sdng cu trúc dliu >c bit ưc
g$i là"ng (heap)  phc tp O(nlgn)
Heap sort
Heap sort
Gii thiu:
- Khái nim heap và@.ươ%/@.áp sp xp Heapsort
do J.Williams 3 xut.
-"ng là cây nhphân mà giá tr m i !nh cha ln
hơn ho>c b&ng giá trcác !nh con.
- Mt khi danh sách dliu ã ưc vun thành
"ng, g"c ca nó là phn tln nht, thut toán s
gii phóng nó kh?i "ng >t vào cu"i danh
sách.
Heap sort
Heap sort
Gii thut:
- Xem danh sách n phn tlà cây nhphân.
- Cây nh@.A%ưc xác nh như sau: ti nút th,
tương ng vi ch!s"thi ca mng có con trái là
nút 2*(i+1)-1 và con phi 2*(i+1) nu 2*(i+1)-1 và
2*(i+1) nh?.ơ%%.
- Xây dng Heap: m$i nút cha 3u có giá trln hơn
nút con.B.,ó nút g"c là nút có giá trln nht.
- Hoán vnút g"c vi nút thn – 1 và xây dng li
Heap mi vi n – 2 nút.
Heap sort
Heap sort
Ví d: Cho dãy 11 3 5 4 9 15 19 7
XD Heap 8
Swap XD Heap 7
(A[0],A[7])