완전 이진 트리의 일종이다.

여러 개 값들 중 최대 값이나 최소 값을 빠르게 찾아내도록 만들어진 자료구조이다.

C++ STL에서는 prioriry_queue가 힙 자료구조로 되어있다.

그러므로 우선순위 큐를 만들 때 주로 사용된다 (최대 힙, 최소 힙)

힙은 반정렬 상태 (느슨한 정렬 상태) 를 유지한다.

1. 큰 값이 상위 노드에 존재하고 그 노드의 자식들은 하위 레벨이다. (여기서 레벨은 기준따라 다르다, 최소 값 최대 값)
2. 힙에서는 중복된 값을 허용한다 (일반적인 이진 트리에서는 중복을 허용하지 않는다.)

힙의 종류

• 최대 힙 (Max Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • Key(부모노드) ≥ Key(자식노드)
• 최소 힙 (Min Heap)
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모노드) ≤ Key(자식노드)

힙의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.

• 구현을 쉽게 하기 위해서 배열의 첫번 째 인덱스 0은 사용하지 않는다.

• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. (루트노드의 왼쪽은 항상2, 오른쪽은 3)

• 힙에서의 부모노드와 자식 노드와의 관계

  • 왼쪽 자식의 인덱스 = (부모노드의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모노드의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

  

힙의 삽입 연산

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족 시킨다.

• 최대 힙에 새로운 요소 8를 넣는다고 가정 했을 때

힙의 삭제연산

1. 최대 힙에서 최대 값은 항상 루트 노드 이므로 루트 노드가 삭제 된다.
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3. 힙을 재 구성한다.