đã là ĐỐNG rồi. Cây được lưu trữ trên mảng K có n phần tử (từ 0-n) */ int Key = K[root]; while(root * 2 <= n-2){ //chừng nào nút chưa phải lá (root *2 < n-1) int c = root*2 + 1; vị trí nút con trái if(c+1 < n && K[c] < K[c+1]){ c = c+1; } if(K[c] < Key){ break; } K[root] = K[c]; root = c; } K[root] = Key; } Đánh giá thời gian thực hiện với dãy n phần tử Ta sẽ chỉ chú ý vào trường hợp xấu nhất: Ta thấy ở vòng for đầu tiên ta phải gọi hàm ADJUST xấp xỉ n/2 lần. Vòng for thứ 2 gọi hàm ADJUST n lần.
Ta thấy cây được xét ở hàm ADJUST là cây đầy đủ, nghĩa là chiều cao của nó cao nhất cũng chỉ là log2(n+1), xấp xỉ log2n -> Số lần so sánh giá trị khoá khi thực hiện hàm ADJUST cũng chỉ là log2n lần (bằng chiều cao của cây tương ứng)
Vậy ta có thể nói số lần thực hiện phép so sánh cùng lắm sẽ là: 3/2 * nlog2n
Suy ra T(x) = O(nlog2n)
Đây là ưu điểm của Heap Sort so với Quicksort, trường hợp xấu nhất của Heap Sort cũng chỉ có đỘ phức tạp là O(nlog2n), còn Quicksort là O(n^2)
14. Trình bày (bằng ngôn ngữ tựa C) giải thuật sắp xếp hoà nhập (Merge Sort). Đánh giá thời gian thực hiện giải thuật với dãy có n phần tử. //giải thuật hoà nhập 2 đường Merge(K, b, m, n, X){ /* K: mảng chứa 2 mảng con X: Mảng chứa 1 mảng to được gộp bởi 2 mảng trên b: vị trí bắt đầu của mảng con 1 m: vị trí kết thúc mảng con 1 n: vị trí kết thức mảng con 2 */ i = b; //i và j là biến chạy ở mảng con 1 và 2 của K
