Thuật Toán Heap Sort

   Chào mừng các bạn đến với chủ đề thuật toán lập trình

Hôm nay chúng ta cùng tìm hiểu về thuật toán Heap Sort (Thuật toán sắp xếp vun đống)
1. Nguyên lý cơ bản của Heap Sort.

Với một tập danh sách n phần từ T1 – T2 – T3… Tn. Ta coi nó như một cây nhị phân.

– Quy định cho cây nhị phân như nhau.

Nếu một node là tại vị trí = i. Thì node này có 2 nhánh trái và phải tương ứng như sau.

+ Nhánh trái là phần tử 2*i + 1 và nhánh phải là 2*i+ 2 với điều kiện là < n

– Nguyên lý được thực hiện như sau:

+ Xây dựng đống sao cho với mọi nút cha đều có giá trị lớn hơn nút con => nút gốc đầu tiên sẽ có giá trị lớn nhất.

+ Hoán vị nút gốc với nút thứ n-1 và xây dựng lại đống mới với n-2, sau đó tiếp tục hoán vị nút gốc với nút cuối của cây mới sau n-2.

 

2 Thực hành Thuật Toán Heap Sort

_________________________________________

Pass Pham

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.