Cho phép nói rằng tôi đang viết Dijkstra's Algorithm và tôi có hàng đợi ưu tiên giữ nút khoảng cách ngắn nhất ở trên cùng. Tuy nhiên khi tôi đi qua biểu đồ, tôi sẽ cập nhật khoảng cách đến đỉnh đó. Tôi đã đặt tham chiếu đến tất cả các đỉnh trong hàng đợi ưu tiên được chứa trong cấu trúc dữ liệu. Bây giờ khi tôi cập nhật các đỉnh trong cấu trúc dữ liệu, tôi muốn cho dữ liệu trong hàng đợi ưu tiên thích ứng với những thay đổi đó, vì vậy nút gần nhất luôn ở trên cùng. Tuy nhiên, sau khi bước qua ứng dụng của tôi với trình gỡ lỗi, tôi đã nhận thấy rằng hàng đợi ưu tiên không tự cập nhật. Làm thế nào để làm cho nó để làm điều này, mà không cần chèn lại tất cả các đỉnh trở lại vào nó?Cập nhật Hàng đợi Ưu tiên STL khi sửa đổi tham chiếu đến dữ liệu nội bộ
5
A
Trả lời
4
STL priority_queue giả định rằng bạn chỉ sử dụng các phương thức push() và pop() để sửa đổi cấu trúc dữ liệu. Nó không theo dõi các thay đổi đối với cấu trúc dữ liệu.
Sau khi sửa đổi nội thất của vùng chứa bên dưới priority_queue, bạn cần gọi hàm make_heap() trên vùng chứa để khôi phục thuộc tính đống. STL priority_queue không cung cấp trình vòng lặp trên vùng chứa bên dưới. Thay vào đó, bạn cần phải quản lý thủ công một deque hoặc một véc tơ như một hàng đợi ưu tiên và gọi make_heap(), push_heap() và pop_heap() khi cần thiết.
Hoặc là thực hiện hoặc viết triển khai của riêng bạn, vì bạn biết những gì đã thay đổi và make_heap() thì không. –
@MtnViewJohn bạn có mẫu làm việc không? Hoặc một mã snip-bit? Không cần điều đầy đủ chỉ là một ví dụ rất nhỏ –
Đây là [link] [1] để SGI thực hiện priority_queue. Bạn có thể sao chép nó và mở rộng nó để bao gồm một phương thức sửa chữa gọi make_heap() để sửa đống sau khi thay đổi nội dung của nó. @NathanS gợi ý cũng rất tốt: khi bạn sửa đổi mỗi nút ngay lập tức thực hiện các hoạt động xoay heap cần thiết để duy trì tài sản heap. [1] http://www.sgi.com/tech/stl/stl_queue.h – MtnViewJohn