O (logn) 시간에 STL 힙을 사용하여 감소 키를 구현

Question

STL 힙은 감소 키를 지원하지 않지만 벡터에서 직접 값을 변경하고 O (n) 시간 인 make_heap을 다시 호출 할 수 있습니다. 그러나 이것은 O (logn) 시간이 걸리는 바이너리 힙 감소 키만큼 효율적이지 않습니다.

STL 힙 함수를 사용하여 O (logn) 시간을 달성하는 방법이 있습니까?

Answer 1

당신은 push_heap 다음 값을 감소시키는 뒤에 pop_heap 사용할 수 있습니다

int main() { 
    //Create the heap 
    std::vector<int> heap{1,2,3,4,5,6,7}; 
    std::make_heap(heap.begin(), heap.end()); 

    //Decrease key 
    std::pop_heap(heap.begin(), heap.end()); 
    --*(std::prev(heap.end())); 
    std::push_heap(heap.begin(), heap.end()); 
} 

을 편집 :이 사람이 말은, 또는 당신이에 어떤 요소의 키를 줄일 수 있도록하려면 무엇을 더미?

가 감소/증가 - 키 조작

갈 않지만에 대한 표준 지원이 없습니다 : Wikipedia says so too -

Answer 2

나는 그 일을 전혀 표준 준수 방법이 없습니다 확신 이 라이브러리는 gheap 라이브러리를 가리 키기에 충분합니다.

여기에서 문제는 표준이 힙 구조가 취하는 양식이나 조작이 얼마나 정확하게 수행되는지를 요구하지 않는다는 것입니다. (일반적으로 이것은 좋은 것입니다.)

구현이 표준 바이너리 힙을 사용하는 경우에는 heap[i]에서 요소를 단순히 줄이고 push_heap(heap.begin(), heap.begin() + i + 1)을 호출하면 필요한 힙 힙 작업을 수행 할 수 있다고 생각합니다. 위치 i에서 끝나는 요소는 원래의 값보다 크지 않아야하며 따라서 전체 힙의 힙 속성이 유지됩니다. 그러나 일부 구현에서 가끔 작동하더라도 표준에 의해 지원되지는 않습니다.