[Heap]31. Vector(array) Based Heap(벡터(배열)기반 힙)

목차

1. Vector(array) Based Heap

 

1. Vector(array) Based Heap

 

 Heap(힙)은 Complete Binary Tree이기 때문에, 배열 혹은 벡터에 충분히 저장 가능합니다. 배열 혹은 벡터로 구현한 heap은 다음과 같은 특성을 가집니다.

 

1) heap의 key 개수가 n이라면, 벡터의 크기는 n+1이다.

2) index i의 벡터 자리를 배정받은 node의 left child는 2i, right child는 2i + 1에 위치한다.

3) index 0번째는 실제로 사용되지 않는다(임시변수로 보통 활용함)

4) 마지막 node의 위치를 쉽게 알 수 있다