Triển khai hàng đợi ưu tiên bằng cách sử dụng đống tối đa so với BST cân bằng
BST cân bằng và đống tối đa đều thực hiện chèn và xóa vào O(logn). Tuy nhiên, việc tìm kiếm giá trị tối đa trong một đống tối đa là O(1)nhưng điều này nằm O(logn)trong BST cân bằng.
Nếu chúng tôi loại bỏ giá trị tối đa trong một đống tối đa, thì điều đó sẽ xảy ra O(logn)vì đó là một thao tác xóa.
Trong BST cân bằng, xóa phần tử max = tìm giá trị max + xóa; nó bằng logn + logn giảm thành O(logn). Vì vậy, thậm chí xóa giá trị tối đa trong BST cân bằng là O(logn).
Tôi đã đọc một ứng dụng như vậy của đống tối đa là một hàng đợi ưu tiên và mục đích chính của nó là loại bỏ giá trị tối đa cho mọi hoạt động xếp hàng. Nếu xóa phần tử tối đa O(logn)cho cả khối tối đa và BST cân bằng, tôi có các câu hỏi sau
Mục đích của đống tối đa trong hàng đợi ưu tiên là gì chỉ vì nó dễ triển khai hơn là sử dụng BST cân bằng có thể tìm kiếm đầy đủ là gì?
Vì không có phép tính hệ số cân bằng, đống tối đa có thể được gọi là cây nhị phân không cân bằng?
Mọi BST cân bằng đều có thể được sử dụng làm hàng đợi ưu tiên và cũng có thể tìm kiếm được trong
O(logn)tuy nhiên tìm kiếm đống tối đa cóO(n)đúng không?
Tất cả những phức tạp về thời gian đều được tính toán cho trường hợp xấu nhất. Bất kỳ trợ giúp nào cũng được đánh giá rất cao.
Trả lời
Mục đích của đống tối đa trong hàng đợi ưu tiên là gì chỉ vì nó dễ triển khai hơn là sử dụng BST cân bằng có thể tìm kiếm đầy đủ là gì?
Một số ưu điểm của heap là:
Cho một mảng đầu vào không được sắp xếp, một đống vẫn có thể được tạo trong thời gian O (n) , trong khi một BST cần thời gian O (nlogn) .
Nếu đầu vào ban đầu là một mảng, thì cùng một mảng đó có thể phục vụ như một đống, nghĩa là không cần thêm bộ nhớ cho nó. Mặc dù người ta có thể nghĩ ra cách tạo BST bằng cách sử dụng dữ liệu tại chỗ trong mảng, nhưng nó sẽ khá kỳ quặc (đối với các kiểu nguyên thủy) và tốn nhiều chi phí xử lý hơn. Một BST thường được tạo từ đầu, sao chép dữ liệu vào các nút khi chúng được tạo.
Thực tế thú vị: một mảng được sắp xếp cũng là một đống, vì vậy nếu biết rằng đầu vào đã được sắp xếp, thì không cần phải làm gì để xây dựng đống.
Một đống có thể được lưu trữ dưới dạng một mảng mà không cần lưu trữ các tham chiếu chéo , trong khi một BST thường bao gồm các nút với các tham chiếu trái và phải. Điều này có ít nhất hai hệ quả:
- Bộ nhớ được sử dụng cho một BST lớn hơn khoảng 3 lần so với một đống.
- Mặc dù một số hoạt động có độ phức tạp về thời gian như nhau cho cả heap và BST, chi phí để điều chỉnh BST lớn hơn nhiều, do đó thời gian thực tế dành cho các hoạt động này là một hệ số (không đổi) lớn hơn trong trường hợp BST.
Vì không có phép tính hệ số cân bằng, đống tối đa có thể được gọi là cây nhị phân không cân bằng?
Trên thực tế, một đống là một cây nhị phân hoàn chỉnh , vì vậy nó luôn cân bằng nhất có thể: các lá sẽ luôn được định vị ở mức cuối cùng hoặc một nhưng cuối cùng. Một BST tự cân bằng (như AVL, red-black, ...) không thể đánh bại mức độ cân bằng cao đó, nơi bạn thường sẽ có những chiếc lá xảy ra ở ba cấp độ hoặc thậm chí nhiều hơn.
Mọi BST cân bằng đều có thể được sử dụng làm hàng đợi ưu tiên và hàng đợi này cũng có thể tìm kiếm được trong O (logn) tuy nhiên tìm kiếm đống tối đa là O (n) có đúng không?
Đúng vậy đây là sự thật. Vì vậy, nếu ứng dụng cần tính năng tìm kiếm, thì một BST là vượt trội.
Mục đích của đống tối đa trong hàng đợi ưu tiên là gì chỉ vì nó dễ triển khai hơn là sử dụng BST cân bằng có thể tìm kiếm đầy đủ là gì?
Không. Max heap phù hợp hơn, vì nó được thiết kế cẩn thận để trả lại phần tử tiếp theo (tôn trọng mức độ ưu tiên) càng sớm càng tốt, trong thời gian O (1). Đó là những gì bạn muốn từ hàng đợi ưu tiên đơn giản nhất có thể.
Vì không có phép tính hệ số cân bằng, đống tối đa có thể được gọi là cây nhị phân không cân bằng?
Không. Có một sự cân bằng là tốt. Tóm lại, việc cân bằng một đống được thực hiện bằng các hoạt động shift-up hoặc shift-down (hoán đổi các phần tử không theo thứ tự).
Mọi BST cân bằng đều có thể được sử dụng làm hàng đợi ưu tiên và hàng đợi này cũng có thể tìm kiếm được trong O (logn) tuy nhiên tìm kiếm đống tối đa là O (n) có đúng không?
Vâng! Cũng như danh sách liên kết có thể được sử dụng hoặc mảng. Nó chỉ là sẽ đắt hơn về ký hiệu O và chậm hơn nhiều trong thực tế.