Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Heap Sort, chuỗi DSA của Coddy.
Chúng ta sẽ xây dựng Heap Sort từ thao tác cốt lõi trở lên.
Thử thách
DễTrọng tâm của Heap Sort là thao tác sift-down. Trước tiên, ta hãy xây dựng thao tác này.
Viết một hàm có tên siftDown, nhận một mảng arr (được xem là một đống nhị phân) và một chỉ số i, rồi khôi phục tính chất đống cực đại tại nút đó bằng cách đẩy nút xuống. So sánh nút với hai nút con ở vị trí 2*i + 1 và 2*i + 2; nếu nút con lớn hơn có giá trị lớn hơn nút hiện tại, hãy hoán đổi với nút đó rồi tiếp tục từ vị trí của nút con. Trả về mảng.
Ví dụ, siftDown([1, 10, 5, 3, 2], 0) trả về [10, 3, 5, 1, 2].
Tự làm thử
#include <stdlib.h>
int* siftDown(int* arr, int arr_size, int i, int* returnSize) {
// Viết code ở đây
*returnSize = arr_size;
return arr;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Heap Sort, chuỗi DSA
2Thuật toán
Nó hoạt động như thế nào?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online