C++ 힙 (heap with any element methods)

Question

최소 또는 최대 값을 제외한 모든 숫자를 제거하는 메서드로 자체 힙을 구현하려고하지만 한 가지 문제를 해결할 수 없습니다. 그 제거 기능을 쓰려면, 힙에있는 요소들에 대한 포인터가 있어야합니다 (주어진 원소를 제거하는 O (logn) 시간을 가짐). 하지만 내가 이런 식으로 시도했을 때 :

vector<int*> ptr(n); 

물론 작동하지 않았다.

아마도 int를 포함하는 다른 클래스 나 구조체를 내 힙에 삽입해야하지만 지금은 int를 사용하여 솔루션을 찾고 싶습니다 (int를 사용하여 이미 구현했기 때문에).

Answer 1

루트가 아닌 다른 오브젝트를 제거 (또는 우선 순위를 변경)해야하는 경우 d- 힙이 반드시 이상적인 데이터 구조는 아닙니다. 노드가 계속 위치를 변경하고 다양한 이동을 추적해야합니다 . 그러나 그것은 가능합니다. 이와 같이 힙을 사용하려면 새로 삽입 된 객체에 대한 핸들을 반환합니다.이 핸들은 놓여있는 일종의 노드를 식별합니다. d-heap 알고리즘은 트리가 완벽하게 균형 잡힌 트리에 의존하므로 실제로 배열을 사용하여 구현해야합니다. 이 두 가지 요구 사항 (배열을 사용하고 노드 유지 상태 유지)은 상호 배타적이므로 둘 다 수행하고 노드에서 배열로 색인을 가져야합니다 (배열에서 객체의 위치를 ​​찾을 수 있음) 및 노드에 대한 배열 (위치가 변경 될 때 노드를 업데이트 할 수 있도록). 거의 확실하게 노드를 많이 이동하지 않으려 고합니다. 즉, 여러 노드를 검색하여 노드를 이동하는 올바른 방향을 찾는 것, 즉 ad> 2를 사용하려고합니다.

본질적으로 노드 기반의 힙. 특히 피보나치 힙 (heap)은 특정 사용 패턴에 대해 일반적인 O (ln (n)) 복잡성보다 더 나은 상각 된 복잡성을 산출합니다. 그러나 노드의 우선 순위를 자주 변경해야하거나 상당히 큰 데이터 세트를 필요로하는 경우 구현하기가 다소 어려우며 실제 효율성은 저하됩니다.

Answer 2

힙은 특별한 종류의 데이터 구조입니다. 요소는 2 진 트리에 저장되며, 요소를 추가하거나 제거하는 잘 정립 된 절차가 있습니다. 많은 구현에서는 배열을 사용하여 트리 노드를 보유하고 log (n) 요소를 이동하는 요소를 제거합니다. 일반적으로 배열이 사용되는 방식으로 배열 위치 n에있는 노드의 자식 노드는 2n 및 2n + 1에 저장됩니다. 요소 0은 비어 있습니다.

This Wikipedia page 알고리즘을 잘 설명합니다.