힙 (Heap)

• 힙(heap)이란? 우선순위 큐를 위해 만들어진 자료구조이다.

• 힙은 완전 이진 트리(Complete Binary Tree)의 일종이다.

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

  • 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 우선순위가 크거나 같아야 한다 (or 작거나 같아야한다).
  • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 or 작은 이진 트리를 말한다.

• 여러 개의 값들 중에서 최댓값 or 최솟값을 빠르게 찾아내도록 해주는 자료구조이다.

• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값 허용 X)

힙(heap)의 종류

• 최대 힙(Max Heap) : 루트 노드로 올라갈수록 값이 커지는 완전 이진 트리.
  key(부모 노드) >= key(자식 노드)

• 최소 힙(Min Heap) : 루트 노드로 올라갈수록 값이 작아지는 완전 이진 트리.
  key(부모 노드) <= key(자식 노드)

사진 출처 : 링크

표준적으로 배열을 이용하여 힙을 구현한다.

힙(heap)의 삽입

1. 힙에 새로운 요소가 들어오면 --> 새로운 요소를 힙의 제일 마지막 노드에 삽입한다.

2. 새로운 노드(요소)를 부모 노드들과 비교한 후 교환을 통해 힙의 성질을 만족시킨다.

아래 그림은 최대 힙(Max Heap)에 새로운 데이터를 삽입하는 경우이다.

사진 출처 : 링크

최소 힙(Min Heap)에 새로운 데이터를 삽입하는 경우에는 기준key(부모 노드) <= key(자식 노드)만 다르며 로직은 같다!

힙(heap)의 삭제

1. 최대 힙(Max Heap)에서 최댓값은 루트 노드이다. 따라서 루트 노드가 삭제된다.

   • 최대 힙(Max Heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다. (반대로, 최소 힙(Min Heap)에서 삭제 연산은 최솟값을 가진 요소를 삭제하는 것이다.)

2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져와 넣는다.

3. 힙의 성질을 만족시키도록 힙을 재구성한다.

아래 그림은 최대 힙(Max Heap)에서 데이터를 삭제하는 경우이다.

사진 출처 : 링크