[자료구조] 힙(Heap)이란?

• 힙(Heap)은 트리 기반의 자료구조로, 부모 노드와 자식 노드 간의 관계에 따라 정의되며, 최소 힙과 최대 힙으로 나뉩니다. 최소 힙에서는 부모가 항상 자식보다 작은 값을 가지며, 최대 힙에서는 그 반대입니다.

• 힙의 기본 동작은 삽입과 삭제로, 삽입은 힙에 새로운 요소를 추가하고, 삭제는 루트 노드를 제거하고 반환하는 과정입니다. 이때 힙의 특성에 따라 재배열하여 힙 속성을 유지합니다.

• 최소 힙(Min Heap)은 부모 노드가 자식 노드보다 작은 값을 가지는 힙으로, 가장 작은 값이 루트 노드에 위치합니다. 반면, 최대 힙(Max Heap)은 부모 노드가 자식 노드보다 큰 값을 가지는 힙으로, 가장 큰 값이 루트 노드에 위치합니다.

• 힙은 우선순위 큐와 같은 응용에서 사용되며, 데이터를 효율적으로 관리하는 데 사용됩니다. 힙의 시간 복잡도는 삽입과 삭제 모두 O(log n)입니다.