[자료구조] Heap

언어 별 자료구조 보기 전에 일단 Heap 개념 먼저 잡고 가자!

---

Heap

최대 힙 vs 최소 힙

• Complete Binary Tree(완전 이진 트리)를 기본으로 갖는 자료구조로, 우선순위 큐를 위해 만들어진 자료구조이다
• 여러 개의 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다
• Heap은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다
  • 큰 값이 상위 레벨, 작은 값이 하위 레벨에 있다는 정도만 유지
  • 즉, 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리이다
  • 키의 대소 관계는 오직 부모노드와 자식노드 간에만 성립하며, 형재(sibillng)사이에는 대소관계가 정해지지 않는다
• Heap 트리에서는 이진 탐색 트리와 달리 중복된 값을 허용한다
• 시간 복잡도는 O(logN)으로 빠른 편이다
• 일반적으로 배열로 구현하는 것이 좋다

---

 

Max Heap (최대 힙)

부모노드의 키 값이 자식노드의 키 값보다 항상 크거나 같은 완전 이진 트리(Heap)

최대 힙

최대 힙의 노드 삽입

• max heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한다
• 그 다음 parent node와 값을 비교하며 root node까지 자리를 바꿔 나간다

 

 

최대 힙의 노드 삭제

• max heap에서 노드 삭제는 항상 root node를 지운다
• 그 다음 complete binary tree를 유지하기 위해 tree를 재조정한다
• 말단의 맨 오른쪽 노드를 지운 후, root node 자리에 옮기고 child node와 비교하며 자리를 바꿔나간다

 

---

 

Min Heap(최소 힙)

부모노드의 키 값이 자식노드의 키 값보다 항상 작거나 같은 완전 이진 트리(Heap)

 

 

 

(참고) Priority Queue

• 일반적인 queue는 FIFO 구조이기 때문에 들어온 데이터가 먼저 나가는 반면, prioirty queue는 우선순위가 높은 데이터가 먼저 나가는 구조이다
• 새로운 노드가 삽입되면 우선순위에 맞는 위치에 삽입되고(enqueue), 삭제할 때는 우선순위가 가장 높은 맨 앞의 노드를 삭제한다(dequeue)

 

---

Heap의 구현

힙 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다
• 구현을 쉽게 하기 위해 배열의 첫번째 인덱스인 0은 사용하지 않는다
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다
• 힙에서의 부모노드와 자식노드의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

 

---

Heap의 삽입

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

[ 삽입 예시 ]

힙의 삽입

 

---

 

Heap의 삭제

1. 최대 힙에서 최댓값은 root node이기 때문에 root node가 삭제된다
   • 최대 힙에서는 최댓값이, 최소 힙에서는 최솟값이 삭제된다
2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져온다
3. 힙을 재구성한다

[ 삭제 예시 ]

힙의 삭제