힙(Heap) : 우선순위 큐를 위해 고안된 완전이진트리 형태의 자료구조이다. 여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다.

힙의 특징

• 완전이진트리 형태로 이루어져 있다.
• 부모 노드와 서브트리간 대소 관계가 성립된다. (반정렬 상태)
• 이진탐색트리와 달리 중복된 값이 허용된다.

힙의 종류

• 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이다.

  • key(부모노드) ≥ key(자식노드)

    

• 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드보다 작거나 같은 완전이진트리이다.

  • key(부모노드) ≥ key(자식노드)

    

우선순위 큐의 연산

• insert(x) : 우선순위 큐에 요소 x 추가
• remove() : 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
• find() : 우선순위 큐에서 가장 우선 순위가 높은 요소를 반환

힙의 구현

• 힙은 일반적으로 배열을 이용하여 구현한다.

  

• 위 그림과 같이 트리의 각 노드에 번호를 붙이고, 이 번호를 배열의 인덱스로 생각하면 효과적으로 힙을 구현할 수 있다. 배열로 구현하였기 때문에 부모 또는 자식을 찾아가는 연산이 간단하다.

• 자식 노드 탐색

  • 왼쪽 자식노드 index = (부모 노드 index) * 2
  • 오른쪽 자식노드 index = (부모 노드 index) * 2 + 1