C++의 이항 힙?

이항 힙은 이진 힙에서 제공하는 다른 작업과 함께 더 빠른 병합 또는 통합 작업을 제공하는 이진 힙의 확장으로 정의됩니다.

이항 힙은 이항 트리 모음으로 처리됩니다.

이항 트리란 무엇입니까?

k차의 이항 트리는 k-1차의 이항 트리 두 개를 가져와서 하나를 가장 왼쪽의 자식 또는 다른 것으로 처리하여 만들 수 있습니다.

k차의 이항 트리에는 다음과 같은 속성이 있습니다.

• Binomial Tree의 노드 수는 정확히 2 ^k 입니다. .

• 이항 트리의 깊이는 k입니다.

• i =0, 1, 인 깊이 i에 정확히 kCi 노드가 있습니다. . . , k.

• 차수가 k인 루트와 루트의 자식은 왼쪽에서 오른쪽으로 k-1, k-2,..0 차수가 있는 이항 트리로 처리됩니다.

이항 힙 -

이항 힙은 각 이항 트리가 MinHeap 속성을 따르는 이항 트리 집합으로 정의됩니다. 차수가 있으면 차수에 관계없이 최대 하나의 이항 트리가 있을 수 있습니다.

예 이항 힙 -

12개의 노드가 있는 이항 힙. 2개의 컬렉션으로 처리됩니다.

왼쪽에서 오른쪽으로 차수 2와 3의 이항 트리

숫자의 이항 힙 및 이진 표현

m개의 노드를 갖는 이항 힙은 m의 이진 표현에서 세트 비트 수와 동일한 이항 트리 수를 갖습니다. 예를 들어, m이 13이라고 가정하고 m(00001101)의 이진 표현에 3개의 세트 비트가 있으며 이는 3개의 이항 트리를 나타냅니다. 우리는 또한 이러한 이항 트리의 차수를 설정된 비트의 위치와 연관시킬 수 있습니다. 이 관계의 도움으로 'm' 노드가 있는 BinomialHeap에 O(logm) Binomial Tree가 있다고 결정하거나 결론을 내릴 수 있습니다.

이항 힙의 연산 -

Union()은 Binomial Heap의 주요 연산이며 다른 모든 연산은 주로 이 연산을 구현합니다. Union() 연산은 두 개의 Binomial Heap을 하나로 결합하는 역할을 합니다.

• insert(h, K)- 이항 힙 'h'에 키 'K'를 삽입합니다. 처음에 이 작업은 단일 키 'K'를 사용하여 이항 힙을 생성한 다음 h와 새로운 이항 힙에서 합집합을 호출할 수 있습니다.

• getMin(h)- getMin()의 간단한 방법은 이항 트리의 루트 목록을 방문하여 가장 작은 키를 반환하는 것입니다.

  이 응용 프로그램은 O(logm) 시간이 필요합니다. 가장 작은 키 루트에 대한 포인터를 유지하여 O(1)로 개선할 수 있습니다.

• extractMin(h)- 이 작업은 또한 union()을 구현합니다. 먼저 getMin()을 호출하여 가장 작은 키 이항 트리를 계산하고 다음으로 노드를 제거하고 제거된 가장 작은 노드의 모든 하위 트리를 결합하여 새 이항 힙을 만듭니다. 마지막으로 h와 새로 생성된 Binomial Heap에 대해 union()을 호출합니다. 이 작업에는 O(logm)시간이 필요합니다.

• delete(h)- 이진 힙과 동일합니다. 처음에 삭제 작업은 키를 마이너스 무한대로 줄이고 다음에는 extractMin()을 호출합니다.

• reduceKey(h)- reductionKey()도 바이너리 힙과 동일합니다. 처음에는 감소 키를 부모와 비교하고 부모의 키가 더 크면 키를 교환하고 부모를 반복합니다. 마지막으로 부모가 더 작은 키를 가진 노드에 도달하거나 루트 노드에 도달하면 중지합니다. reduceKey()의 시간 복잡도는 O(logm)입니다.