Tôi có một bộ sưu tập các mặt hàng (hợp lý lớn) mà tôi sẽ được xử lý. Trong mỗi trường hợp, quá trình xử lý sẽ bao gồm việc xóa mục nhỏ nhất trong bộ sưu tập, thực hiện một số công việc và sau đó thêm 0-2 mục mới (sẽ luôn lớn hơn mục đã xóa). Bộ sưu tập sẽ được khởi tạo với một mục và công việc sẽ tiếp tục cho đến khi nó trống. Tôi không chắc chắn kích thước bộ sưu tập có khả năng đạt được, nhưng tôi mong đợi trong phạm vi các mục 1M-100M. Tôi sẽ không cần phải tìm bất kỳ mục nào khác ngoài mục nhỏ nhất.Cây đỏ đen có phải là cấu trúc dữ liệu lý tưởng của tôi không?
Tôi hiện đang có kế hoạch sử dụng cây đỏ đen, có thể được điều chỉnh để giữ con trỏ đến mục nhỏ nhất. Tuy nhiên tôi chưa bao giờ sử dụng một cái trước đây, và tôi không chắc liệu mô hình sử dụng của tôi có phù hợp với đặc điểm của nó hay không.
1) Có nguy cơ khi xóa mô hình chèn trái + ngẫu nhiên sẽ ảnh hưởng đến hiệu suất, ví dụ bằng cách yêu cầu số lần quay cao hơn đáng kể so với xóa ngẫu nhiên? Hoặc sẽ xóa và chèn các hoạt động vẫn là O (log n) với mẫu sử dụng này?
2) Một số cấu trúc dữ liệu khác sẽ cho tôi hiệu suất tốt hơn, do mô hình xóa hoặc lợi dụng thực tế tôi chỉ cần tìm mục nhỏ nhất?
Cập nhật: vui lòng tôi hỏi, đống nhị phân rõ ràng là giải pháp tốt hơn cho trường hợp này, và như đã hứa hóa ra rất dễ thực hiện.
Hugo
Trừ khi bạn biết chắc chắn rằng các nút bị xóa theo logic sẽ không cần thiết bởi các giá trị mới được tính toán, bạn có thể muốn bỏ qua hoặc trì hoãn xóa. Một cách tiếp cận Halt & Sweep nên làm việc cho sau này, nơi mà rễ của cây phụ đã nhận được quá lộn xộn được truy cập bởi các mã tái cân bằng để cân bằng en'masse. Điều này ngăn ngừa thoái hóa tổng thể, trong khi vẫn cung cấp triển vọng có khả năng về hiệu suất xóa ít hơn. – RocketRoy