힙 : 최소값을 구할때 적합한 자료구조

힙은 부모노드의 값이 자식 노드의 값보다 항상 적은 이진트리를 뜻한다.

조건 :

• 부모 노드의 값은 항상 하위 노드의 값보다 작다. (또는 부모 노드의 값은 항상 하위 노드의 값보다 크다)
• 자식 노드의 값은 둘 중 어느쪽이 크더라도 상관없다.(왼쪽 오른쪽 어느쪽이 크더라도 괜찮다)

따라서 뿌리 부분에 반드시 모든 값중에서 가장 작은 값(또는 가장 큰 값)이 배치된다.

 

=> 데이터 열 중에서 최소값(또는 최대값)을 효율적으로 구하는 용도에 적합하다.

 

실제로 힙을 구현할 때는 일반적으로 배열을 사용한다.

힙의 뿌리를 1번째  요소로, 그 다음은 아래의 절차를 따라 대입한다.

• '깊이'는 작은쪽에서 큰 쪽으로
• 노드의 왼쪽에서 오른쪽 방향으로

출처: 파이썬 알고리즘 인터뷰

이 그림을 배열로 나타내면?

인덱스   [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
값       5   9   11  14  18  19  21  33  17  27

 

참고도서 : 그림으로 배우는 알고리즘 Basic - 스기우라 켄