Cách dễ nhất để sử dụng hàng đợi ưu tiên tối thiểu với cập nhật quan trọng trong C++

Question

Đôi khi trong khi thực hiện các cuộc thi lập trình, chúng tôi cần thực hiện thao tác đơn giản với hàng đợi ưu tiên tối thiểu bằng phím giảm để thực hiện thuật toán Dijkstra vv .. Tôi thường sử dụng cặp < đặt < key_value, ID > > và một mảng (ánh xạ ID -> key_value) với nhau để đạt được điều đó.

• Việc thêm phần tử vào tập hợp sẽ mất thời gian O (log (N)). Để xây dựng một hàng đợi ưu tiên trong số các phần tử N, chúng ta chỉ cần thêm chúng từng cái một vào tập hợp. Điều này có tổng thời gian O (N log (N)).

• Phần tử có min key_value chỉ đơn giản là phần tử đầu tiên của tập hợp. Việc thử nghiệm phần tử nhỏ nhất sẽ mất thời gian O (1). Loại bỏ nó mất thời gian O (log (N)).

• Để kiểm tra xem một số ID = k có trong tập hợp không, trước tiên chúng tôi tra cứu key_value = v_k trong mảng và sau đó tìm kiếm phần tử (v_k, k) trong tập hợp. Điều này có thời gian O (log (N)).

• Để thay đổi key_value của một số ID = k từ v_k thành v_k ', trước tiên chúng tôi tra cứu key_value = v_k trong mảng và sau đó tìm kiếm phần tử (v_k, k) trong tập hợp. Tiếp theo chúng ta loại bỏ phần tử đó khỏi tập và sau đó chèn phần tử (v_k ', k) vào tập hợp. Chúng tôi sau đó cập nhật mảng, quá. Điều này có thời gian O (log (N)).

Mặc dù cách tiếp cận trên hoạt động, hầu hết sách giáo khoa thường khuyên bạn sử dụng đống nhị phân để triển khai hàng đợi ưu tiên, khi xây dựng đống nhị phân chỉ là O (N). Tôi nghe nói rằng có một cấu trúc dữ liệu xếp hàng ưu tiên được xây dựng sẵn trong STL của C++ sử dụng đống nhị phân. Tuy nhiên, tôi không chắc chắn cách cập nhật key_value cho cấu trúc dữ liệu đó.

Cách dễ nhất và hiệu quả nhất khi sử dụng hàng đợi ưu tiên tối thiểu với cập nhật khóa trong C++ là gì?

Answer 1

Tôi không nghĩ rằng lớp std::priority_queue cho phép thực hiện hiệu quả hoạt động theo phong cách decrease-key.

Tôi cuộn đống nhị phân cấu trúc của riêng tôi dựa trên dữ liệu có hỗ trợ này, bascially dọc theo các đường rất giống với những gì bạn đã mô tả cho hàng đợi ưu tiên dựa std::set bạn có:

• Duy trì một đống nhị phân, được sắp xếp theo value lưu trữ các phần tử của pair<value, ID> và một mảng bản đồ ID -> heap_index. Trong các thói quen heap heapify_up, heapify_down vv, nó cần thiết để đảm bảo rằng mảng ánh xạ được giữ đồng bộ với vị trí heap hiện tại của các phần tử. Điều này cho biết thêm một số chi phí thêm O(1).
• Việc chuyển đổi mảng thành một đống có thể được thực hiện trong O(N) theo thuật toán chuẩn được mô tả here.
• Nhìn trộm ở phần tử gốc là O(1).
• Kiểm tra xem ID hiện có trong vùng heap hay không chỉ yêu cầu tra cứu O(1) trong mảng ánh xạ. Điều này cũng cho phép O(1) xem trước phần tử tương ứng với bất kỳ ID nào.
• Decrease-key yêu cầu tra cứu O(1) trong mảng ánh xạ, theo sau là bản cập nhật O(log(N)) tới heap qua heapify_up, heapify_down.
• Đẩy một vật phẩm mới lên heap là O(log(N)) khi đang popping một mục thoát ra từ heap.

Do đó thời gian chạy tiệm cận được cải thiện đối với một vài thao tác so với cấu trúc dữ liệu dựa trên std::set. Một ứng dụng quan trọng khác là đống nhị phân có thể được triển khai trên một mảng, trong khi các cây nhị phân là các thùng chứa dựa trên nút. Vị trí dữ liệu bổ sung của heap nhị phân thường chuyển thành thời gian chạy được cải thiện.

Một vài vấn đề với việc thực hiện này là:

• Nó chỉ cho phép số nguyên mục ID 's.
• Giả định phân phối chặt chẽ mục ID, bắt đầu từ số không (nếu không thì độ phức tạp của mảng ánh xạ sẽ thổi lên!).

Bạn có khả năng khắc phục những vấn đề này nếu bạn duy trì bảng băm bản đồ, chứ không phải mảng bản đồ, nhưng có thêm một chút thời gian chạy. Để sử dụng, số nguyên ID luôn là đủ.

Hy vọng điều này sẽ hữu ích.

Answer 2

Vâng, như Darren đã nói, std::priority_queue không có phương tiện để giảm mức độ ưu tiên của một phần tử và không loại bỏ phần tử khác với phần tử hiện tại. Nhưng mặc định std::priority_queue không có gì hơn một bộ điều hợp container đơn giản xung quanh một std::vector sử dụng chức năng heap thứ cấp từ <algorithm> (std::push_heap, std::pop_heap và std::make_heap). Vì vậy, cho Dijkstra (nơi bạn cần cập nhật ưu tiên), tôi thường chỉ làm điều này bản thân mình và sử dụng một đơn giản std::vector.

Một push là sau đó chỉ là O (log N) hoạt động

vec.push_back(item); 
std::push_heap(vec.begin(), vec.end()); 

Tất nhiên để xây dựng một hàng đợi một lần nữa từ các yếu tố N, chúng tôi không đẩy tất cả chúng sử dụng O này (log N) hoạt động (làm cho toàn bộ điều O (nlog N)) nhưng chỉ cần đặt tất cả chúng vào vector theo sau là một O đơn giản (N)

std::make_heap(vec.begin(), vec.end()); 

Yếu tố min là một O đơn giản (1)

vec.front(); 

Một pop là O đơn giản (log N) chuỗi

std::pop_heap(vec.begin(), vec.end()); 
vec.pop_back(); 

Cho đến nay đây là chỉ là những gì std::priority_queue thường không dưới mui xe. Bây giờ để thay đổi ưu tiên của một mục chúng ta chỉ cần thay đổi nó (tuy nhiên nó có thể được đưa vào loại của mục) và làm cho chuỗi một đống có giá trị một lần nữa

std::make_heap(vec.begin(), vec.end()); 

Tôi biết đây là một O (N) hoạt động, nhưng mặt khác, điều này sẽ loại bỏ bất kỳ nhu cầu nào về việc theo dõi vị trí của mục trong vùng heap với cấu trúc dữ liệu bổ sung hoặc thậm chí tệ hơn là tăng thêm loại của các mục. Và hình phạt hiệu suất trên bản cập nhật ưu tiên logarit không thực sự đáng kể, xem xét việc sử dụng bộ nhớ dễ sử dụng, nhỏ gọn và tuyến tính của std::vector (cũng ảnh hưởng đến thời gian chạy) và thực tế là tôi thường làm việc với các đồ thị có ít các cạnh (tuyến tính trong số đỉnh).

Nó có thể không phải trong mọi trường hợp là cách nhanh nhất, nhưng chắc chắn là dễ nhất.

EDIT: Oh, và kể từ khi thư viện tiêu chuẩn sử dụng max-đống, bạn cần phải sử dụng tương đương với > để so sánh ưu tiên (tuy nhiên bạn nhận được chúng từ các mục), thay vì các nhà điều hành mặc định <.

Answer 3

Mặc dù câu trả lời của tôi không trả lời được câu hỏi ban đầu, tôi nghĩ nó có thể hữu ích cho những người tiếp cận câu hỏi này khi cố gắng thực hiện thuật toán Dijkstra trong C++/Java (như bản thân mình), cái gì đó được OP,

bình luận

priority_queue bằng C++ (hoặc PriorityQueue bằng Java) không cung cấp hoạt động decrease-key như đã nói trước đây. Một mẹo hay để sử dụng các lớp đó khi triển khai Dijkstra đang sử dụng "xóa bỏ lười". Vòng lặp chính của thuật toán Dijkstra trích xuất nút tiếp theo sẽ được xử lý từ hàng đợi ưu tiên và phân tích tất cả các nút lân cận, cuối cùng thay đổi chi phí của đường dẫn tối thiểu cho một nút trong hàng đợi ưu tiên. Đây là điểm cần có decrease-key để cập nhật giá trị của nút đó.

Bí quyết là không thay đổi nó. Thay vào đó, một "bản sao mới" cho nút đó (với chi phí mới tốt hơn) được thêm vào hàng đợi ưu tiên. Có chi phí thấp hơn, bản sao mới của nút sẽ được trích xuất trước bản sao gốc trong hàng đợi, vì vậy nó sẽ được xử lý trước đó.

Vấn đề với việc xóa "lười biếng" này là bản sao thứ hai của nút, với chi phí xấu cao hơn, cuối cùng sẽ được trích xuất từ ​​hàng đợi ưu tiên. Nhưng điều đó sẽ luôn xảy ra sau khi bản sao được thêm vào thứ hai, với chi phí tốt hơn, đã được xử lý. Vì vậy, điều đầu tiên rằng vòng chính Dijkstra phải làm khi giải nén nút tiếp theo từ hàng đợi ưu tiên là kiểm tra xem nút đã được truy cập trước đó chưa (và chúng tôi biết đường đi ngắn nhất đã có). Chính trong khoảnh khắc chính xác đó khi chúng ta sẽ thực hiện "xóa bỏ lười biếng" và phần tử đó phải được bỏ qua một cách đơn giản.

Giải pháp này sẽ có chi phí cả về bộ nhớ và thời gian, vì hàng đợi ưu tiên lưu trữ "phần tử chết" mà chúng tôi chưa xóa. Nhưng chi phí thực sẽ khá nhỏ và lập trình giải pháp này là IMHO, dễ dàng hơn bất kỳ phương án thay thế nào khác cố gắng mô phỏng hoạt động thiếu decrease-key.