binary heap 구현 시 indexing

binary heap 구현 시,

root 를 0 으로 하는 것과 1 로 하는 것의 차이를 보자.

* i 의 child 

	left child	right child
0-based	i * 2 + 1	(i+1) * 2
1-based	i * 2	i * 2 + 1

 

* i 의 parent

	i 가 left 일 때	i 가 right 일 때
0-based	i / 2	(i-1) / 2
1-based	i / 2	i / 2

root 의 index 를 1 로 하여 구현하는 것이 계산이 더 간단하다.

뿐만 아니라 다음과 같은 이점이 있다.

depth 0	1
depth 1	2	3
depth 2	4	5	6	7
depth 3	8	9	10	11	12	13	14	15

index 를 2 진수로 변환하면, 같은 depth 인 경우 자리 수가 같아진다.

depth 0	1
depth 1	10	11
depth 2	100	101	110	111
depth 3	1000	1001	1010	1011	1100	1101	1110	1111

또한 가장 왼쪽 node 의 index 는 항상 첫 자리가 1 이고 나머지 자리는 모두 0 이 된다.

가장 마지막 node 의 index 는 항상 모든 자리가 1 이다.

이런 이유로, index 값만으로 depth 를 알 수 있고 그 외 유용한 연산을 더 빠르고 간편하게 해 낼 수 있다.

특별한 이유가 없다면 binary heap 구현은 root index 를 1 로 하는 게 좋다.