Làm thế nào để thay đổi phần tử tối đa trong một heap trong thư viện chuẩn C++?

Nếu tôi có một vùng tối đa và nếu tôi cần thay đổi phần tử tối đa, nó sẽ đi xuống một thuật toán bong bóng đơn. Có cách nào để làm điều này thông qua thư viện chuẩn C++, mà không cần mã hóa thuật toán bằng tay?Làm thế nào để thay đổi phần tử tối đa trong một heap trong thư viện chuẩn C++?

Tôi hiểu nó phải tương đương với pop_heap + push_heap, nhưng đó là 2 hoạt động bong bóng xuống thay vì chỉ một.

Vậy - thuật toán bong bóng này có được hiển thị qua API thư viện không?

Nguồn

2015-04-15 rincewind

Gần nhất bạn sẽ nhận được là std::make_heap, có nghĩa là có lẽ chậm hơn chỉ đơn giản là bật/tắt.

Tuy nhiên, tăng heap (s?) Có "Giao diện sửa lỗi" cho phép sửa đổi như bạn mong muốn. http://www.boost.org/doc/libs/1_51_0/doc/html/heap/concepts.html#heap.concepts.mutability

Nguồn

2015-04-15 23:43:48

Tôi nghĩ rằng 'std :: make_heap' sẽ chậm hơn một chút so với pop và đẩy cho một đống lớn. Đối với một đống nhỏ, nó cũng có thể nhanh hơn. – rici

@rici: Tôi không biết làm thế nào 'make_heap' được thực hiện, nhưng nó là _possible_ rằng nó có thể siêu nhanh đối với những thứ đã là một đống trừ một phần tử. Đó là _possible_ nó thậm chí còn tối ưu cho tình huống đó. Phụ thuộc vào việc thực hiện mặc dù. Và tôi hoàn toàn suy đoán, nó có thể là việc thực hiện make_heap là nhiều hơn hoặc ít hơn cần thiết để được cùng một thời gian chạy không có vấn đề bố trí ban đầu. –

Tuy nhiên nó được thực hiện, nó cần phải kiểm tra mọi yếu tố để biết rằng những gì bạn cung cấp cho nó đã là một đống trừ một yếu tố. Đó là O (N). Pop và push là O (log N) với một hệ số không đổi lớn hơn một chút (có lẽ không quá hai hoặc ba), vì vậy đối với một đống lớn, 'make_heap' sẽ không mở rộng. – rici

Nếu bạn sẵn sàng để gọi std::pop_heap() trên container của riêng bạn v, sau đó bạn có thể chỉ đầu tiên v.push_back() trên thùng sơn các yếu tố "chỉnh sửa" trước khi popping đống. Sau đó, thu nhỏ v.

// Precondition is that v is already a heap. 
void change_max_element (std::vector<int> &v, int modified_value) { 
    v.push_back(modified_value); 
    std::pop_heap(v.begin(), v.end()); 
    v.pop_back(); 
}

Điều này "hoạt động" vì std::pop_heap() được xác định để hoán đổi thành phần đầu tiên và cuối cùng và bong bóng xuống. Tuy nhiên, yêu cầu cũng được tuyên bố rằng chuỗi đầu vào phải là một đống hợp lệ. Nếu chúng ta có thể xác định một hoạt động so sánh chuyên biệt sẽ cho phép mục quay lại mới được báo cáo nằm ở vị trí cuối cùng nếu nó đã ở vị trí cuối cùng, thì nó có thể đáp ứng yêu cầu về mặt kỹ thuật.

Nguồn

2015-04-16 00:18:48 jxh

Có một sự báo trước mặc dù (nhưng tôi không nghĩ rằng đó là một vấn đề). Các tài liệu của std :: pop_heap() yêu cầu [đầu tiên, cuối cùng) là một đống, nhưng khi bạn push_back một giá trị mới như là cuối cùng, không có đảm bảo rằng [đầu tiên, cuối cùng) là một đống. Tôi không nghĩ rằng điều này quan trọng bởi vì yếu tố cuối cùng được chuyển đến đầu tiên và heapify được thực hiện. – szli

@szli: Đó là một điểm tốt. Việc triển khai trong tương lai có thể tận dụng yêu cầu đó và vẫn tạo ra các hiệu ứng được chỉ định. Tuy nhiên, nó nói rằng các hiệu ứng đã được mô tả cụ thể như vậy. – jxh

Tôi đã xem xét việc triển khai GNU/Clang/SGI của STL, giả định duy nhất là [first, last-1) là một đống. Bước đầu tiên là trao đổi đầu tiên và cuối cùng-1, sau đó heapify [đầu tiên, cuối cùng-1). Nó an toàn, ít nhất là bây giờ. – szli

Làm thế nào để thay đổi phần tử tối đa trong một heap trong thư viện chuẩn C++?

Trả lời

Các vấn đề liên quan