CS 자료구조 Heap(힙)

 

힙은 완전 이진 트리 형태를 따르는 자료구조다. 주로 우선순위 큐를 구현하는데 사용된다. 

 

ㅇ 힙의 특성

• 완전 이진 트리(Complete Binary Tree) 
  힙은 모든 레벨이 꽉 차 있어야 하며(마지막 레벨은 제외), 마지막 레벨은 왼쪽에서부터 차례대로 채워져야 한다.
  항상 가장 왼쪽부터 빈 자리를 채워나가는 트리구조다.

 

• 힙 속성(Heap Property)
  
  최대 힙(Max Heap)
  부모 노드가 자식 노드보다 항상 크거나 같아야한다. 루트에 가장 큰 값이 위치한다.
  최대값을 빠르게 추출할 수 있다.
  
  최소 힙(Min Heap)
  부모 노드가 자식 노드보다 항상 작거나 같아야한다. 루트에 가장 작은 값이 위치한다.
  최소값을 빠르게 추출할 수 있다.

 

ㅇ 힙의 주요 연산

삽입(Insertion)

• 새로운 값을 삽입할 때는 트리의 마지막 자리에 추가된다.(완전 이진 트리의 속성)
  이후 부모 노드와 비교하여 힙 속성이 만족될 때까지 상향 조정(Bubble Up)을 한다.
  
  예를 들어 최대 힙에서는 부모 노드가 자식보다 작으면 두 값을 교체하는 식으로 조정한다.
• 시간 복잡도: O(log n)

최대 값 또는 최소 값 조회(Get Max/Min)

• 최대 힙에서는 루트 노드가 항상 가장 큰 값
• 최소 힙에서는 루트 노드가 항상 가장 작은 값
• 루트 노드를 조회하는 것은 O(1)의 시간 복잡도로 매우 빠르다.

삭제(Deletion)

• 힙에서 최대값(최소 힙의 경우 최소값)을 삭제하려면 루트 노드를 제거한다. 이 때 트리의 마지막 노드를 루트로 가져오고, 이후 자식들과 비교하면서 하향 조정(Bubble Down)을 수행하여 힙 속성을 복구한다.
• 시간 복잡도: O(log n)

힙 정렬(Heap Sort)

• 힙 정렬은 최대 힙이나, 최소 힙을 사용하여 정렬하는 방식이다. 데이터를 힙에 삽입 후 하나씩 값을 꺼내서 정렬된 리스트를 얻을 수 있다. 최대 힙의 경우 내림차순 정렬, 최소 힙의 경우 오름차순 정렬을 할 수 있다.
  
  데이터를 꺼낸다는 것은 삭제와 같은 의미라고 볼 수 있다. 힙에서 데이터를 꺼낼 때는 항상 루트 노드에서 값을 불러오고 하향조정 후 힙 속성을 복구하면 다시 루트 노드에서 값을 꺼낸다.
  
  
• 시간 복잡도: O(n log n)

 

ㅇ 힙의 주요 활용

• 우선 순위 큐(Priority Queue)
  우선순위 큐는 각 항목이 우선순위를 가지며, 우선순위가 높은 항목이 먼저 처리되는 자료구조다.
  힙을 사용하여 구현하면, 항목 삽입과 삭제 모두 O(log n) 시간안에 처리할 수 있다.
• 힙 정렬(Heap sort)
  힙을 기반으로 한 정렬 알고리즘으로, 데이터 삽입과 삭제를 반복하여 정렬한다. 
  안정적인 방법은 아니지만 최악의 경우에도 O(n log n)의 성능을 보장한다.
• 그래프 알고리즘
  힙은 다익스트라 알고리즘이나 프림 알고리즘 등에서 우선순위 큐로 사용되어 가중치가 낮은 경로나 최소 신장 트리를 찾는데 활용된다.

 

ㅇ 힙의 장단점

장점

• 빠른 최대값 또는 최소값 추출
  루트 노드에 항상 최대(소)값이 위치하기 때문에 빠르게 찾고 제거할 수 있다.
• 효율적인 삽입과 삭제
  완전 이진 트리 구조와 힙 속성 덕분에 삽입과 삭제가 O(log n)의 시간 복잡도로 이루어진다.

단점

• 정렬된 데이터를 효율적으로 처리하지 못함
  이미 정렬된 데이터에서는 성능이 떨어질 수 있다.
• 트리 순회가 어렵다
  완전 이진 트리 구조를 유지하는 것이 목적이므로, 순회하면서 데이터를 정렬된 순서대로 탐색하는 데는 적합하지 않다.