Nếu hoạt động tìm kiếm của bạn tương đối không thường xuyên (và vùng heap của bạn khá nhỏ), tôi chỉ thực hiện tìm kiếm tuyến tính. Nếu nó là tương đối thường xuyên, hoặc đống là rất lớn, hãy xem xét theo dõi thành viên heap (để làm 'tìm' kiểm tra của bạn) với một cấu trúc dữ liệu riêng biệt hoặc một lá cờ đối tượng. Niềm vui của việc lập chỉ mục bên ngoài là có thể đưa đối tượng của bạn vào bao nhiêu vùng chứa tùy thích.
Nếu bằng cách 'tìm' bạn thực sự có nghĩa là 'tìm và sửa đổi' (tôi thấy tôi thường cần xóa mọi thứ khỏi hàng đợi ưu tiên độc lập với insert/del-min), đây là ba phương pháp tôi đã sử dụng:
Với tỷ lệ chèn/del-min cao (100k/s liên tục) và tỷ lệ tìm kiếm xóa thấp (nói 1/s) trên một nhóm làm việc khá nhỏ (500-1000), tôi đã thực hiện tìm kiếm tuyến tính cho phần tử và sau đó xóa nó khỏi cây theo cách tiêu chuẩn.
Với tỷ lệ chèn/del-min cao cộng với tìm kiếm xóa thường xuyên, tôi chỉ đơn giản là đánh dấu các đối tượng đã xóa là "không quan tâm" sau khi tìm chúng gián tiếp. Việc miễn phí thực tế đã được hoãn lại cho đến khi đối tượng được dequeued như bình thường.
Cho một tiêu chuẩn nhỏ :: priority_queue (không có phương thức truy cập bên ngoài chèn/del-min) chỉ một vài yếu tố và xóa thường xuyên, tôi vừa sao chép toàn bộ hàng đợi vào một std :: vector và sao chép tạm thời phần được sửa đổi/mong muốn trở lại hàng đợi. Sau đó tôi đã khóc khi ngủ.
Nguồn
2010-10-20 04:03:47
"trung bình tôi sẽ thực hiện nhiều lần chèn hơn xóa" - đó là _really_ ý của bạn là gì? Nếu đó là trường hợp, cuối cùng bạn sẽ hết bộ nhớ, phải không? – paxdiablo
hàng đợi ưu tiên dành cho thuật toán tìm đường dẫn. khi tôi đạt được mục tiêu của mình, tôi chỉ có thể xóa phần còn lại của hàng đợi ưu tiên mà không cần phải cân bằng lại. – Harry
@paxdiablo - cách vòng khác chỉ đơn giản là không thể ... không phải mọi chương trình đều chạy dài – tobyodavies