[자료구조] Heap이란?

Heap 완전 이진 트리 구조

 

• Heap이란 완전 이진 트리의 일종으로, 대표적으로 앞서 포스팅한 PS 알고리즘에서 사용한 우선순위 큐의 구현에 사용된다.
• 여러 개의 값들 중에서 min 값 혹은 max 값을 효율적으로 찾아내기 위해 고안된 자료구조이다.
• Heap은 엄밀하게 정렬되어 있는 상태는 아니다.
  • index의 접근을 통해 정렬되어 있는 것처럼 보이게 한다.
• 노드 개념을 사용하며, 부모 노드의 값은 항상 자식 노드의 값보다 큰 상태를 유지한다.
• 완전 이진 트리에서는 중복되는 값을 허용하지 않지만, Heap에서는 허용한다는 차이점이 존재한다.

 

index 할당을 통한 정렬 구현

---

• Heap을 정렬하기 위해서는 배열 구조체를 일반적으로 사용하면 된다.
• 배열의 경우 당연히 자동 sort가 되어 있지 않지만, 접근 자체를 정렬 된 것처럼 접근하면 된다.
• index의 할당은 다음의 규칙을 따른다.
  • left child index = (parent index) * 2
  • right child index = (parent index) * 2 + 1
  • parent index = (any child index) / 2
    
    

새로운 데이터 삽입 (minHeap)

---

minHeap 데이터 삽입 과정

1. 맨 끝 노드에 우선 값을 집어넣는다.
2. 연결된 부모 노드와 값을 비교하며 위로 차곡차곡 swap하며 올라간다.
3. 더 이상 부모 노드보다 값이 작아지지 않았다면, 그 자리에 머무른다.

 

기존 데이터 삭제 (minHeap)

---

 

minHeap 데이터 삭제 과정

1. 루트 노드에 있는 값을 삭제한다.
2. 맨 끝 노드에 있던 값을 불러와서 루트 노드에 놓는다.
3. minHeap이므로, 맨 위 루트 노드로 불려온 노드와 자식 노드를 비교해 아래로 점점 내려간다 (swap)
4. 이 때 오른쪽과 왼쪽 자식 노드 모두 루트 노드보다 작다면, 더 작은 자식 노드와 swap한다.
5. 위 과정을 반복한다.

 

Reference

---

힙 트리 - 나무위키 (namu.wiki) (그림 참조)