Tôi có một hàng đợi ưu tiên các sự kiện, nhưng đôi khi các ưu tiên sự kiện thay đổi, vì vậy tôi muốn duy trì các trình vòng lặp từ những người yêu cầu sự kiện vào heap. Nếu ưu tiên thay đổi, tôi muốn heap được điều chỉnh trong thời gian log (n). Tôi sẽ luôn có chính xác một trình vòng lặp trỏ tới từng phần tử trong heap.Có một lớp heap trong C++ hỗ trợ thay đổi mức độ ưu tiên của các phần tử khác với phần đầu?
Tôi rất vui mừng thông báo rằng Boost hiện đã thêm một số Boost.Heap library với một số stellar data structures.
Lợi thế của việc này là các mức Fibonacci hỗ trợ thay đổi ưu tiên trong thời gian khấu hao không đổi.
Thật không may, tất cả các vùng ẩn có thể thay đổi được dựa trên nút (nói cách khác, chúng có thêm sự gián tiếp như được đề xuất bởi @wilx). Câu trả lời của @ Feruccio về "đống có thể thay đổi" của Boost có mã cho phép người ta viết đống có thể biến đổi dựa trên vectơ nếu bạn sẵn sàng có con trỏ tới các tay cầm chứa trong loại giá trị của bạn.
Điều đó nghe có vẻ như bạn cần thêm hướng dẫn. Lưu trữ con trỏ tới các sự kiện trong hàng đợi ưu tiên thay thế. Khi ưu tiên của một số phần tử của hàng đợi thay đổi, hãy xóa nó và lắp lại.
Hãy xem Boost của mutable heaps.
Một cảnh báo ở đây là bạn kết thúc với sự kiện không ổn định phân loại, tức là Trật tự của các sự kiện với các ưu tiên như nhau là undefined (đọc 'họ sẽ được sắp xếp lại.)
Bạn có thể loại bỏ một phần tử tùy ý khỏi một đống trong thời gian nhật ký (n). –
Vâng, bạn đã đúng, đang nghĩ về điều gì khác :) –
không có vấn đề :) –
Cảm ơn, nếu tôi phải tự cuộn, tôi sẽ sử dụng đoạn mã đó để bắt đầu. –
đã kết thúc với giải pháp này –
@Ferruccio Cảm ơn, đã lưu 45 phút và một vài lỗi của tôi. –