2분 힙

2분 힙은 2분 트리를 이용한 데이터 구조의 하나로, 우선 순위 큐를 효율적으로 실현한다.
2분 힙에서는 2분 트리를 포인터로 표현하는 것이 아니라, 2분 트리의 노드에 번호를 붙여 배열에서도 같이 구현되는 것이 자주 있다.

배열에서 구현할 때 노드 번호 매기기

이진 트리의 각 노드에 대해 그림과 같이 번호를 흔들어 라.


이 때, 자신의 노드에 대해서 아이 번호와 부모 번호는 이하와 같이 되지만, 이것의 설명.

왼쪽 아이: $2n$ 오른쪽 아이: $2n + 1$

부모 : $floor(\frac{n}{2})$

[1. 설명]
이진 트리의 깊이 $ d $의 노드 수는 $ 2 ^ d (d = 0, 1, 2, ...) $이며 깊이 $ d $ 이하의 모든 노드 수는

2^0 + 2^1 + … + 2^d = \frac{(1 - 2^(d+1))}{(1-2)} = 2^(d+1) - 1

된다. 따라서 각 깊이 $d$에서 가장 왼쪽 노드의 index는 $(2^d-1)+1 = 2^d$이며,
이 가장 왼쪽 노드 $2^d$에 대한 왼쪽 아이는 $2^(d+1)=2*2^d$, 오른쪽 아이는 $2*2^d + 1$로 1.이 성립한다.

깊이 $d$의 왼쪽에서 $i-1$번째의 노드 $n-1$에 대해 1.이 성립한다고 가정한다.
깊이 $d$의 왼쪽에서 $i$번째 노드 $n$에 대한 왼쪽 자식의 번호는 왼쪽에서 $i-1$번째 노드의 오른쪽 자식의 다음이므로
$(2(n-1) + 1) + 1 = 2n$가 되어 1.이 노드 $n$에 대해서도 성립한다.
따라서 귀납적으로 임의의 깊이 $d$의 모든 노드에 대해 1.이 성립한다.

[2. 설명]
깊이 d의 가장 왼쪽의 노드에 대해서는, 노드 번호가 $2^d$로 부모는 $2^(d-1)$이므로 2.가 성립한다.
또한 다음 노드의 부모는 동일한 부모이며 $floor(\frac{2^d + 1}{2}) = floor(2^(d-1) + 0.5)=2^(d-1) $이므로 2.가 성립한다.

깊이 $d$의 왼쪽에서 $2i-1$번째의 노드에 대해서 2.가 성립한다고 가정한다.
왼쪽에서 $2i+1$번째 노드 $n$에 대한 부모 번호는 왼쪽에서 $2i-1$번째 부모의 다음이므로,
$floor(\frac{n-2}{2}) + 1 = floor(\frac{n-2}{2} + 1) = floor(\frac{n}{2})$
되어 2.가 성립한다.
마찬가지로 왼쪽에서 $2i$번째 노드에 대해 2.가 성립한다고 가정하면 왼쪽에서 $2i+2$번째 노드 $n$에 대해서도 2.가 성립한다.
따라서 귀납적으로 임의의 깊이 $d$의 모든 노드에 대해 2.가 성립한다.

0 시작 노드 번호를 지정하는 경우

다음과 같이 0 시작 번호를 붙인다.


1 시작 노드 번호를 n, 0 시작 노드 번호를 $n'$로 설정하면 $n' = n - 1$
한 노드에 대한 왼쪽의 아이는 1 시작의 번호에서는, $2n = 2(n'+1)$로, 이것을 0 시작에 고쳐 $2(n' +1) -1 = 2n' + 1$, 오른쪽 의 아이는 $2n'+2$가 된다.
부모에 대해서도 1 시작의 번호에서는, $floor(\frac{n}{2})=floor(\frac{n'+1}{2})$로, 이것을 0 시작에 고쳐 $floor(\frac{n'+1}{2}) - 1 = floor(\frac{n'+1}{2} - 1) = floor(\frac{n'-1}{2})$

끝에

프로그래밍 콘테스트 챌린지 북을 읽고 왜 이런 일이 일어나는지 잠시 생각해 버렸기 때문에 메모