bài viết này tôi nói về cách thức hoạt động của thuật toán Heap Sort.

I. Khái niệm

1. Định nghĩa Heap

– Định nghĩa Heap sơ khởi: Heap là 1 cây nhị phân đầy đủ.
+ vd1:

– Mỗi node trong Heap chứa 1 giá trị có thể so sánh với giá trị của node khác
2. Tính chất Heap

+ Max Heap: Giá trị của mỗi node >= giá trị của các node con nó
=> Node lớn nhất là node gốc
+ Min Heap: Giá trị của mỗi node <= giá trị của các node con nó
=> Node nhỏ nhất là node gốc

+ vd3:

3. Biểu diễn Heap bằng mảng

– Thứ tự lưu trữ trên mảng được thực hiện từ trái => phải
– Nếu ta biết được chỉ số của 1 phần tử trên mảng, ta sẽ dễ dàng xác định được chỉ số của node cha và các node con của nó.
– Node gốc ở chỉ số 0
– Node cha của node i có chỉ số (i – 1)/2
– Các node con của node i (nếu có) có chỉ số [2i + 1] và [2i + 2]
– Node cuối cùng có con trong 1 Heap có n phần tử là: [n/2 – 1]

4. Thao tác điều chỉnh 1 phần tử (Heapify)

4.1/ Chạy từng bước (Debug)

– Tôi sẽ tiến hành Heapify theo Max Heap. Tức là node con của node đang xét mà lớn hơn node cha thì tiến hành đổi chỗ

4.2/ Cài đặt

5. Xây dụng Heap (BuildHeap)

5.1/ Khái niệm

– Tất cả các phần tử trên mảng có chỉ số [n/2] đến [n – 1] đều là node lá
– Mỗi node lá được xem là Heap có duy nhất 1 phần tử
– Thực hiện thao tác Heapify trên các phần tử có chỉ số từ [n/2 – 1] => 0 ta sẽ tạo được 1 Heap có n phần tử
5.2/ Cài đặt

5.3/ Xây dựng mảng sau thành Heap

– Ở mục này tôi sẽ tiến hành chay từng bước hàm BuildHeap
– Lưu ý: Tôi sẽ Build Heap trên mảng với Max Heap
– Ví dụ:

– Theo hàm BuildHeap khởi tạo biến i = n/2 – 1
+ Ta thấy mảng trên có 10 phần tử
=> i = 10/2 – 1 = 4
=> Vậy ta sẽ bắt đầu ở vị trí 4 của mảng trên

– Ta thấy vị trí 4 có giá trị là 7 và con của nó là 9
+ Ta nhận thấy 9 > 4 => Ta đổi chỗ 2 thằng này

+ Sau khi hoán vị xong ta giảm i (i–). Theo hàm BuildHeap

+ Sau khi xây dụng Heap xong => Ta nhận thấy còn 1 vị trí ko tuân theo quy luật Max Heap: 5 và con của 5 là 15 và 1: 15 > 5 và 15 > 1
=> Đổi chỗ 15 và 1

=> Kết quả của mảng:

6. Thuật toán HeapSort

6.1) Tư tưởng thuật toán HeapSort

-B1: Xây dựng Heap
=> Sử dụng thao tác Heapify để chuyển đổi mảng bình thường thành Heap

-B2: Sắp xếp
+ Hoán vị phần tử cuối cùng của Heap với phần tử đầu tiên của Heap
+ Loại bỏ phần tử cuối cùng
+ Thực hiện thao tác Heapify để điều chỉnh phần tử đầu tiên

6.2) Cài đặt HeapSort