[CS - 자료구조] 힙(heap)

#. 힙(heap)

---

##1. 힙(heap)이란?

힙(heap) 은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree) 를 기본으로 한 자료구조이다.
부모 노드가 자식 노드보다 크거나 같은 완전 이진 트리를 최대 힙, Max Heap,
부모 노드가 자식 노드보다 작거나 같은 완전 이진 트리를 최소 힙, Min Heap 으로 구분할 수 있다.

---

##2. 힙(heap)의 특징

• 힙은 '완전 이진 트리' 형태를 가진다.
• 힙의 부모 노드는 자식 노드보다 크거나 같은 값을 가진다.
• 힙은 루트 노드가 최댓값(최대 힙의 경우) 또는 최솟값(최소 힙의 경우)을 가진다.
• 힙은 배열로 표현할 수 있다.
• 힙은 중복을 허용한다.

---

##3. 힙(heap)의 장점과 단점

##3.1 장점

힙은 최대값 또는 최소값을 찾아내는 연산을 빠르게 수행할 수 있다. 이는 우선순위 큐와 같은 추상적 자료형의 구현에 매우 유용하다.

##3.2 단점

힙은 정렬된 구조가 아니므로, 특정 값을 검색하는데는 적합하지 않다.

---

##4. 힙(heap)의 동작

###4.1 구현

• insert : 힙에 새로운 요소를 추가한다.
• delete : 힙에서 가장 큰 요소를 제거한다.
• peek : 힙에서 가장 큰 요소를 반환한다.
• size : 힙의 크기를 반환한다.
• isEmpty : 힙이 비어있는지 확인한다.
• maxHeapify : 힙의 특성을 유지한다.

###4.2 삽입

1. 새로운 요소를 힙의 마지막 노드에 추가
2. 추가된 새로운 노드를 부모 노드와 비교하여
   추가된 노드가 부모 노드 보다 크다면, 위치를 교환한다.
   추가된 노드가 부모 노드 보다 작거나 같다면, 삽입을 종료한다.

###4.3 삭제

최대값을 알아내 삭제하기 위해서는

1. 힙의 루트 노드를 삭제한 후, 힙의 마지막 노드를 루트 노드 자리로 이동한다.
2. 루트 노드와 자식 노드를 비교하여
   루트 노드가 자식 노드 보다 작다면, 자식 노드 중 가장 큰 노드와 위치를 교환한다.
   루트 노드가 크다면, 삭제를 종료한다.

###4.4 Heapify

위의 삽입과 삭제 수행 과정에서 구조의 변화로 인해 힙의 속성이 깨질 수 있기 때문에
위치를 교환하며 힙의 재구조화를 수행하는 Heapify 메서드를 사용한다.

---

##5. 힙(heap)의 사용

###5.1 우선순위 큐

힙은 우선순위 큐 구현에 가장 일반적으로 사용되는 자료구조이다.

###5.2 힙 정렬

힙은 힙 정렬(Heap Sort)이라는 효율적인 정렬 알고리즘에 사용된다.

###5.3 그래프 알고리즘

힙은 최소 신장 트리를 찾는 프림 알고리즘, 최단 경로를 찾는 다익스트라 알고리즘 등의 그래프 알고리즘에서 활용된다.

---

References

• https://codingmoon.io/posts/data-structure-algorithms/heap/