Xóa phần tử khỏi phần giữa của tiêu chuẩn :: heap

Question

Tôi đang sử dụng hàng đợi ưu tiên làm bộ lập lịch với một yêu cầu bổ sung. Tôi cần có thể hủy các mục đã lên lịch. Điều này tương đương với việc loại bỏ một mục từ giữa hàng đợi ưu tiên.

Tôi không thể sử dụng std::priority_queue vì quyền truy cập vào bất kỳ phần tử nào khác ngoài phần đầu được bảo vệ.

Tôi đang cố sử dụng chức năng heap của algorithm. Nhưng tôi vẫn còn thiếu phần tôi cần. Khi tôi loại bỏ một phần tử tôi từ giữa đống, tôi muốn nó tự xây dựng lại hiệu quả. C++ cung cấp các chức năng này đống:

• std::make_heapO (3n)
• std::push_heapO (lg (n))
• std::pop_heapO (2 lg (n))

Tôi muốn có một chức năng mới như std::repair_heap với một lớn-O < 3n. Tôi sẽ cung cấp cho nó vị trí của lỗ mà mục bị hủy bỏ được sử dụng để cư trú và nó sẽ điều chỉnh đúng đống.

Dường như có sự giám sát rất lớn để không cung cấp chức năng std::repair_heap. Tôi có thiếu một cái gì đó hiển nhiên?

Có thư viện nào cung cấp tuân thủ STN std::repair_heap không?

Có cấu trúc dữ liệu tốt hơn để lập mô hình trình lên lịch không?

LƯU Ý:
Tôi không sử dụng std::map vì một vài lý do.

• Một đống có phí trên bộ nhớ không đổi.
• Một vùng có vị trí bộ nhớ cache tuyệt vời.

Answer 1

Thật không may, tiêu chuẩn thiếu chức năng này (khá quan trọng). Với g ++, bạn có thể sử dụng chức năng phi tiêu chuẩn std::__adjust_heap để thực hiện việc này, nhưng không có cách di chuyển dễ dàng nào - và __adjust_heap hơi khác trong các phiên bản khác nhau của g ++, vì vậy bạn thậm chí không thể thực hiện nó trên các phiên bản g ++ .

Answer 2

Dường như với tôi rằng loại bỏ từ giữa một đống có thể có nghĩa là toàn bộ đống phải được xây dựng lại: Lý do không có repair_heap là bởi vì nó sẽ phải làm như vậy công việc (lớn-oh) như make_heap .

Bạn có thể làm điều gì đó như đặt std::pair<bool, Item> trong heap và chỉ vô hiệu hóa các mục thay vì xóa chúng? Sau đó, khi họ cuối cùng nhận được để đầu chỉ cần bỏ qua các mục và di chuyển cùng.

Answer 3

Công việc repair_heap() của bạn hoạt động như thế nào? Đây là dự đoán của tôi:

Nếu heap của bạn được xác định bởi một số phạm vi trình lặp, hãy nói (heapBegin, heapEnd). Phần tử bạn muốn loại bỏ là thư mục gốc của một số subtree của heap, được định nghĩa bởi một số subrange (subHeapBegin, subHeapEnd).Sử dụng std::pop_heap(subHeapBegin, subHeapEnd), sau đó nếu subHeapEnd != heapEnd, hoán đổi các giá trị tại *(subHeapEnd-1) và *(heapEnd-1), sẽ đặt mục đã xóa của bạn ở cuối vùng chứa heap. Bây giờ bạn phải percolate phần tử tại * (subHeapEnd-1) lên trong subheap của bạn. Nếu tôi đã không bỏ lỡ một cái gì đó, đó là có thể, sau đó tất cả những gì còn lại là để cắt các yếu tố kết thúc ra khỏi container heap.

Trước khi gặp sự cố khi cố mã hóa chính xác (tôi đã bỏ qua một số chi tiết như tính subHeapBegin và subHeapEnd), tôi sẽ chạy một số kiểm tra để xác định xem make_heap() có thực sự làm chậm bạn không. Big-O là hữu ích, nhưng nó không giống như thời gian thực hiện thực tế.

Answer 4

Dưới đây là một số mã delphi tôi đã sử dụng để xóa các mục khỏi heap. Tôi không biết C++ trong đó bạn nói và không có chức năng sửa chữa, nhưng hey ..

đầu tiên pop, vì vậy bạn sẽ có được một ý tưởng về cách điều hoạt động:

function THeap.Pop: HeapItem; 
begin 
    if fNextIndex > 1 then begin 
    Dec(fNextIndex); 
    Result:= fBuckets[1]; //no zero element 
    fBuckets[1] := fBuckets[fNextIndex]; 
    fBuckets[fNextIndex] := nil; 
    FixHeapDown;   //this has a param defaulting to 
    end 
    else 
    Result:= nil; 
end; 

nay đến độ tương phản, việc xóa:

procedure THeap.Delete(Item: HeapItem); 
var 
    i:integer; 
begin 
    for i:=1 to pred(fNextIndex) do 
    if Item=fBuckets[i] then begin 
     dec(fNextIndex); 
     fBuckets[i] := fBuckets[fNextIndex]; 
     fBuckets[fNextIndex] := nil; 
     FixHeapDown(i); 
     break; 
     end; 
end; 

tất nhiên của nó một không-không ngay cả suy nghĩ về làm những gì chúng ta đang làm gì ở đây, nhưng hey, chi phí làm thay đổi đôi khi, công việc làm được hủy bỏ.

thưởng thức. tôi hy vọng điều này sẽ giúp.

Answer 5

Tôi đoán bạn biết phần tử nào trong vùng chứa heap (chỉ mục n) bạn muốn xóa.

1. Đặt giá trị v[n] = BIG; giá trị BIG thực sự lớn hơn bất kỳ giá trị nào khác trong vùng.
2. Gọi std::push_heap(v.begin(), v.begin()+n+1);
3. Gọi std::pop_heap(v.begin(), v.end());
4. Gọi v.pop_back();
5. Xong

Operation là O (ln (n))

RE: yêu cầu bằng chứng

Đầu tiên, một vòng loại: Phương pháp này giả định điều gì đó về gorithm được sử dụng bởi std push_heap.
Cụ thể, nó giả định rằng push_heap std (v.begin(), v.begin() + n + 1) sẽ chỉ thay đổi phạm vi [0, n]
cho những phần tử đó là n, tức là, chỉ số trong tập hợp sau:

A(n)={n,(n-1)/2,((n-1)/2-1)/2....0}. 

Dưới đây là một spec điển hình cho std push_heap:

http://www.cplusplus.com/reference/algorithm/push_heap/ "với một loạt đống [đầu tiên, cuối cùng-1), chức năng này mở rộng phạm vi được coi là một đống để [đầu tiên, cuối cùng) bằng cách đặt giá trị trong (last-1) vào vị trí tương ứng của nó trong đó. "

Ứng dụng có đảm bảo sử dụng "thuật toán heap thông thường" mà bạn đã đọc trong sách giáo khoa không? Bạn nói với tôi.

Dù sao, đây là mã mà bạn có thể chạy và xem, theo kinh nghiệm, rằng nó hoạt động. Tôi đang sử dụng VC 2005.

#include <algorithm> 
#include <vector> 
#include <iostream> 

bool is_heap_valid(const std::vector<int> &vin) 
{ 
    std::vector<int> v = vin; 
    std::make_heap(v.begin(), v.end()); 
    return std::equal(vin.begin(), vin.end(), v.begin()); 
} 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    srand(0); 
    std::vector<int> v; 
    for (int i=0; i<100; i++) 
    { 
     v.push_back(rand() % 0x7fff); 
    } 
    std::make_heap(v.begin(), v.end()); 

    bool bfail = false; 
    while(v.size() >= 2) 
    { 
     int n = v.size()/2; 
     v[n] = 0x7fffffff; 
     std::push_heap(v.begin(), v.begin()+n+1); 
     std::pop_heap(v.begin(), v.end()); 
     v.resize(v.size()-1); 
     if (!is_heap_valid(v)) 
     { 
      std::cout << "heap is not valid" << std::endl; 
      bfail = true; 
      break; 
     } 
    } 
    if (!bfail) 
     std::cout << "success" << std::endl; 

    return 0; 

} 

Nhưng tôi có một vấn đề khác, đó là làm thế nào để biết chỉ số "n" mà cần phải bị xóa. Tôi không thể nhìn thấy làm thế nào để theo dõi đó (biết nơi trong heap) trong khi sử dụng std push_heap và std pop_heap. Tôi nghĩ rằng bạn cần phải viết mã heap của riêng bạn và viết chỉ mục trong heap vào một đối tượng mỗi khi đối tượng được di chuyển trong heap. Thở dài.