Cấu trúc xếp hàng ưu tiên được sử dụng?

Question

Trong khi tìm kiếm một số hàm trong tài liệu thư viện chuẩn C++, tôi đọc rằng việc đẩy và bật cho các hàng đợi ưu tiên cần thời gian không đổi.

http://www.cplusplus.com/reference/stl/priority_queue/push/

Constant (trong priority_queue). Mặc dù thông báo rằng push_heap hoạt động trong thời gian logarit.

Câu hỏi của tôi là loại cấu trúc dữ liệu nào được sử dụng để duy trì hàng đợi ưu tiên với O (1) để đẩy và bật?

Answer 1

tôi giả bạn đang đề cập đến cplusplus.com's page.

Đầu trên trang nó nói:

chức năng thành viên này có hiệu quả gọi hàm thành viên push_back của đối tượng chứa tiềm ẩn, và sau đó gọi các thuật toán push_heap phải duy trì nhà đống priority_queues.

Vì vậy, sau khi O(1) đẩy, cấu trúc dữ liệu đã bị mất tài sản đống của nó bất biến và sau đó sẽ luôn luôn làm theo điều đó với một O(log N) gọi để khôi phục lại tài sản đó. Nói cách khác, hoạt động O(1) chỉ là một phần của toàn bộ hoạt động; hoạt động đầy đủ là O(1) + O(log N) tương tự như O(log N). Tôi đoán lý do họ đề cập đến đó là hàng đợi ưu tiên là một bộ điều hợp và họ đang cố gắng nhấn mạnh sự khác biệt giữa những gì container cơ bản so với những gì bộ điều hợp làm.

Answer 2

Đẩy và Pop chạy trong thời gian Logarithmic theo

http://www.cppreference.com/wiki/stl/priority_queue/pop

http://www.cppreference.com/wiki/stl/priority_queue/push

Answer 3

Tôi hoài nghi về O (1) khẳng định ... nơi mà bạn đã nhìn thấy nó?

Trong mọi trường hợp, dưới đây là some notes on gcc's implementation of a priority queue.

Answer 4

Không có một loại heap như vậy. Họ đã viết rằng nó gọi push_heap là logarit nên nó là logn.

Answer 5

Bộ nhớ cơ bản cho priority_queue có thể là một véc tơ hoặc một deque hoặc bất kỳ thứ gì tương tự hỗ trợ trình vòng lặp truy cập ngẫu nhiên. Lưu trữ được duy trì như một đống, không phải là O (N) để đẩy, vì vậy tôi nghi ngờ bạn đã đọc sai số này

Answer 6

Tiêu chuẩn xác định các thành viên đó theo số push_heap và pop_heap, ngụ ý biên dịch.

Nếu điều gì that reference nói là đúng (nó nói top cũng không đổi), tại sao không ai thực hiện phân loại O (N) có mục đích chung bằng cách sử dụng std::priority_queue?

Vào thứ hai, mặc dù đây là những gì các tài liệu tham khảo có thể cố gắng để nói, theo một cách rất sai lầm: sự phức tạp là của push_back O (1) + push_heap (O (log N))