thời điểm đống sắp xếp, khi tất cả các yếu tố này là giống hệt nhau

Question

Chúng ta có thể nói rằng, khi tất cả các yếu tố này là giống hệt nhau trong một mảng A có kích thước n sau đó thời gian chạy của đống phân loại là O chạy (n)

-> Nếu đây là trường hợp, là O (n) trường hợp tốt nhất thời gian chạy của heapsort

Answer 1

Khi tất cả các phần tử bằng nhau xây dựng heap có O (n) bước. Bởi vì khi phần tử được thêm vào heap sau khi so sánh O (1), chúng ta thấy nó ở đúng vị trí.

Xóa gốc cũng là O (1), khi chúng tôi trao đổi đuôi và gốc, thuộc tính heap vẫn hài lòng.

Tất cả các phần tử được thêm vào heap trong O (n) và được loại bỏ trong O (n). Vì vậy, có trong trường hợp này trường hợp heapsort là O (n). Tôi không thể nghĩ ra một trường hợp tốt hơn vì vậy trường hợp tốt nhất heapsorts phải là O (n).

'Trường hợp tốt nhất Heapsorts là O (n)' có nghĩa là trong tiếng Anh một cái gì đó như: có tồn tại mảng kích thước n sao cho heapsort cần nhiều nhất k * n so sánh để sắp xếp nó. Đó là tốt đẹp trong lý thuyết nhưng trong thực tế nó không nói nhiều về cách heapsort tốt hay nhanh là.