Heap Sort là gì
Sắp xếp vun đống (Heap Sort) là một kỹ thuật sắp xếp phân loại dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Nó tương tự như thuật toán Sắp xếp chọn (Selection Sort)nơi phần tử lớn nhất sẽ được xếp vào cuối danh sách. Lặp đi lặp lại các bước này cho các phần tử còn lại của danh sách.
Khái niệm đống nhị phân (binary heap)Mỗi mảng a[1..n] có thể xem như một cây nhị phân gần đầy (có trọng số là các giá trị của mảng), với gốc ở phần tử thứ nhất, con bên trái của đỉnh a[i] là a[2*i] con bên phải là a[2*i+1] (nếu mảng bắt đầu từ 1 còn nếu mảng bắt đầu từ 0 thì hai nhánh con là a[2*i+1] và a[2*i+2]) (nếu 2*i n hoặc 2*i+1 n, khi đó các phần tử có chỉ số lớn hơn (int) (n/2) không có con, do đó là lá).
Kỹ thuật vun đốngViệc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống. Vun đống tại đỉnh thứ iNếu hai cây con gốc 2*i và 2*i+1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2*i] và a[2*i+1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2*i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đên khi hoặc gặp đỉnh lá. Vun một mảng thành đốngĐể vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j] với j = Int (n/2) ngược lên tới a[1]. Sắp xếp bằng vun đống
Ví dụVí dụ 01: Cho mảng a=(2,3,5,6,4,1,7), Ở đây n = 7. Các phần tử từ a[4] đến a[7] là lá. Tạo đống
Bây giờ a=(7,6,5,3,4,1,2) đã là đống. Sắp xếp vun đống
Ví dụ 02:Sắp xếp mảng{ 6, 5, 3, 1, 8, 7, 2, 4 } từ nhỏ đến lớn sử dụng phương pháp vun đống Tạo đống Sắp xếp (vun đống) HeapPhần tử hoán đổiXóa phần tửmảng sắp xếpchi tiết8, 6, 7, 4, 5, 3, 2,18, 1hoán đổi 8 và 1 để xóa 8 từ đống1, 6, 7, 4, 5, 3, 2,8số 8xóa 8 từ heap và thêm vào mảng đã sắp xếp1, 6,7, 4, 5, 3, 21, 7số 8hoán đổi 1 và 7 vì chúng không theo thứ tự trong đống7, 6,1, 4, 5,3, 21, 3số 8hoán đổi 1 và 3 vì chúng không theo thứ tự trong đống7, 6, 3, 4, 5, 1,27, 2số 8hoán đổi 7 và 2 để xóa 7 từ đống2, 6, 3, 4, 5, 1,77số 8xóa 7 từ heap và thêm vào mảng đã sắp xếp2,6, 3, 4, 5, 12, 67, 8hoán đổi 2 và 6 vì chúng không theo thứ tự trong đống6,2, 3, 4,5, 12, 57, 8hoán đổi 2 và 5 vì chúng không theo thứ tự trong đống6, 5, 3, 4, 2,16, 17, 8hoán đổi 6 và 1 để xóa 6 từ đống1, 5, 3, 4, 2,667, 8xóa 6 từ heap và thêm vào mảng đã sắp xếp1,5, 3, 4, 21, 56, 7, 8hoán đổi 1 và 5 vì chúng không theo thứ tự trong đống5,1, 3,4, 21, 46, 7, 8hoán đổi 1 và 4 vì chúng không theo thứ tự trong đống5, 4, 3, 1,25, 26, 7, 8hoán đổi 5 và 2 để xóa 5 từ đống2, 4, 3, 1,556, 7, 8xóa 5 từ heap và thêm vào mảng đã sắp xếp2,4, 3, 12, 45, 6, 7, 8hoán đổi 2 và 4 vì chúng không theo thứ tự trong đống4, 2, 3,14, 15, 6, 7, 8hoán đổi 4 và 1 để xóa 4 từ đống1, 2, 3,445, 6, 7, 8xóa 4 từ heap và thêm vào mảng đã sắp xếp1, 2,31, 34, 5, 6, 7, 8hoán đổi 1 và 3 vì chúng không theo thứ tự trong đống3, 2,13, 14, 5, 6, 7, 8hoán đổi 3 và 1 để xóa 3 từ đống1, 2,334, 5, 6, 7, 8xóa 3 từ heap và thêm vào mảng đã sắp xếp1,21, 23, 4, 5, 6, 7, 8hoán đổi 1 và 2 vì chúng không theo thứ tự trong đống2,12, 13, 4, 5, 6, 7, 8hoán đổi 2 và 1 để xóa 2 từ đống1,223, 4, 5, 6, 7, 8xóa 2 từ heap và thêm vào mảng đã sắp xếp112, 3, 4, 5, 6, 7, 8xóa 1 từ heap và thêm vào mảng đã sắp xếp1, 2, 3, 4, 5, 6, 7, 8hoàn thànhSắp xếp vun đống trong lập trình C++Sắp xếp một mảngarr[] = { 12, 11, 13, 5, 6, 7 } theo thứ tự tăng dần sử dụng phương pháp vun đống bằng ngôn ngữ lập trình C++. Nhấp đôi vào code để copy và chạy thử xem kết quả. #include |