Chuyển đổi heap thành BST trong thời gian O (n)?

Question

Tôi nghĩ rằng tôi biết câu trả lời và độ phức tạp tối thiểu là O (nlogn).

Nhưng có cách nào để tôi có thể tạo cây tìm kiếm nhị phân từ một đống trong O (n) phức tạp không?

Answer 1

Không có thuật toán để xây dựng BST từ một đống trong thời gian O (n). Lý do cho điều này là các phần tử n đã cho, bạn có thể xây dựng một đống từ chúng trong thời gian O (n). Nếu bạn có BST cho một tập hợp các giá trị, bạn có thể sắp xếp chúng trong thời gian O (n) bằng cách thực hiện quá trình truyền tải theo thứ tự. Nếu bạn có thể xây dựng một BST từ một đống trong thời gian O (n) thời gian, sau đó bạn có thể có một O (n) thuật toán sắp xếp bởi

1. Xây dựng đống trong thời gian O (n) thời gian,
2. Chuyển đổi các đống đến một BST trong thời gian O (n) và
3. Đi bộ BST trong thời gian O (n) để nhận chuỗi được sắp xếp.

Do đó, nó không phải là có thể chuyển đổi một đống đến một BST trong thời gian O (n) thời gian (hoặc trong o (n log n) thời gian, nơi o là little-o notation). Tuy nhiên, có thể xây dựng một BST từ một đống trong thời gian O (n log n) bằng cách lặp đi lặp lại giá trị lớn nhất từ ​​BST và chèn nó như là nút ngoài cùng bên phải trong cây. (Bạn sẽ cần phải lưu trữ một con trỏ ở đó để truy cập nhanh, chỉ cần chèn vào gốc lặp lại sẽ có thời gian O (n).)

Hy vọng điều này sẽ hữu ích!