데이터 구조의 이항 힙

이항 힙은 이항 트리의 모음입니다. 이항 트리 Bk는 재귀적으로 정의된 순서 트리입니다. 이항 트리 B0은 단일 노드로 구성됩니다.

이항 트리 Bk는 두 개의 이항 트리 Bk-1로 구성됩니다. 서로 연결되어 있는 것입니다. 하나의 루트는 다른 루트의 가장 왼쪽 자식입니다.

일부 이항 힙은 다음과 같습니다. -

이항 트리의 일부 속성은 다음과 같습니다. -

• B_k가 있는 이항 트리 2_k가 있습니다. 노드.

• 나무의 높이는 k입니다.

• 범위 0에서 k까지의 모든 i에 대해 깊이 i에 정확히 $$\left(\begin{array}{c}k\\ j\end{array}\right)$$ 노드가 있습니다.

이항 힙

이항 힙 H는 이항 트리의 집합입니다. 속성이 있습니다.

• H의 각 이항 트리는 힙 정렬됩니다. 따라서 노드의 키는 상위 노드의 키보다 크거나 같습니다.

• H에는 루트가 주어진 차수를 갖는 최대 하나의 이항 트리가 있습니다.

이항 힙의 예

이 이항 힙 H는 이항 트리 B0, B2 및 B3으로 구성됩니다. 각각 1, 4 및 8 노드가 있습니다. 그리고 총 n =13개 노드입니다. 이항 트리의 루트는 차수가 오름차순으로 연결된 목록으로 연결됩니다.