힙(Heap)(면접을 위한 CS 전공지식 노트)

힙(Heap)

힙(Heap)

힙(Heap)은 비선별형 자료구조 중 하나로, 주로 우선순위 큐(priority queue)를 구현하는 데 사용되는 

자료구조입니다.

 

힙의 특징

부모-자식 관계: 

힙은 일반적으로 이진 트리(binary tree) 구조를 가집니다. 

각 노드는 최대 두 개의 자식 노드를 가지며, 

부모 노드와 자식 노드 간에는 특정한 순서(최소 힙 또는 최대 힙)가 유지됩니다.

최소 힙과 최대 힙: 

힙은 두 가지 주요 유형이 있습니다.

최소 힙(Min Heap): 

각 부모 노드는 그 자식 노드보다 작거나 같은 값을 가집니다. 

따라서 루트 노드는 전체 트리에서 가장 작은 값을 가집니다.

최대 힙(Max Heap): 

각 부모 노드는 그 자식 노드보다 크거나 같은 값을 가집니다. 

따라서 루트 노드는 전체 트리에서 가장 큰 값을 가집니다.

삽입과 삭제 연산: 

힙은 주로 두 가지 주요 연산을 지원합니다.

삽입(Insertion): 

새로운 요소를 힙에 추가할 때, 

일반적으로 힙의 마지막 위치에 요소를 추가하고 필요에 따라 부모와 비교하여 힙 속성을 복원합니다.

삭제(Deletion): 

루트 노드를 삭제하는 것이 일반적이며, 삭제 후 힙의 속성을 복원하여 새로운 루트를 결정합니다. 

최소 힙에서는 최소값을, 최대 힙에서는 최대값을 빠르게 찾을 수 있습니다.

우선순위 큐: 

힙은 우선순위 큐를 구현하는 데 효과적으로 사용됩니다. 

우선순위 큐는 요소를 우선순위에 따라 삽입하고 삭제할 수 있는 자료구조로, 

힙을 기반으로 구현하면 O(log N) 시간복잡도로 삽입과 삭제 연산을 수행할 수 있습니다.

힙 속성 유지: 

힙은 삽입 및 삭제 연산 시에도 항상 힙 속성을 유지해야 합니다. 

이를 위해 상향식(Bottom-up) 또는 하향식(Top-down) 방법을 사용하여 힙 속성을 유지합니다.

힙은 다양한 응용 분야에서 사용되며, 정렬 알고리즘에서도 중요한 역할을 합니다. 

가장 흔하게 사용되는 힙 종류 중 하나는 이진 최소 힙(Binary Min Heap)입니다.

 

힙 자세히 알기!!

가장 흔한 사용 사례 중 하나는 우선순위 큐(priority queue)입니다. 

우선순위 큐는 다양한 작업 또는 데이터 요소를 우선순위에 따라 다루는 자료구조입니다. 

힙은 이러한 우선순위 큐를 구현하는 데 사용됩니다.

예를 들어, 병원 응급실에서 환자가 도착하고 의료진이 그들의 상태를 처리하는 상황을 생각해봅시다. 

각 환자는 응급 상태에 따라 우선순위가 다를 것입니다. 힙을 사용하여 이 상황을 모델링할 수 있습니다.

환자 1: 응급 상태 3 (가장 높은 우선순위)
환자 2: 응급 상태 2
환자 3: 응급 상태 1
환자 4: 응급 상태 2
환자 5: 응급 상태 4 (가장 높은 우선순위)

이러한 환자를 힙에 저장한다고 가정해보겠습니다. 

최소 힙(Min Heap)을 사용하면 환자 3이 루트 노드에 위치하게 됩니다. 

루트 노드에 있는 환자가 가장 높은 우선순위를 가집니다. 따라서 의료진은 환자 3을 가장 먼저 처리합니다.

이제 환자 3이 처리되었으므로 힙에서 루트 노드(환자 3)를 제거하고 남은 환자들 중에서 다시 가장 높은 

우선순위를 가진 환자를 루트로 이동합니다. 

그 결과, 환자 2가 루트 노드로 이동하게 됩니다.

이와 같은 방식으로 최소 힙을 사용하면 항상 가장 높은 우선순위를 가진 요소를 

루트로 빠르게 찾을 수 있으며, 새로운 요소를 추가하거나 우선순위가 변경되는 상황에서도 

효율적으로 관리할 수 있습니다.

마찬가지로 최대 힙(Max Heap)을 사용하면 가장 낮은 우선순위를 가진 요소를 찾는 것이 

효율적으로 수행됩니다.