[Algorithm] 힙(Heap)?

힙

힙이란 완전 이진 트리의 일종으로 우선순위 큐를 구현하기 위한 자료구조입니다. 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내는데 사용됩니다.

 

이진 트리는 그림과 같이 트리 층에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조를 말합니다. 이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있습니다. 

 

 

 

완전이진트리

우선순위 큐

 

우선순위 큐는 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조를 말합니다. 우선순위 큐는 단순히 리스트를 이용하여 구현할 수도 있고 힙을 이용하여 구현할 수도 있습니다. 우선순위 큐를 단순히 리스트를 이용하여 구현하면 삽입하는 시간 복잡도는 O(1)이고 삭제할 때 시간 복잡도는 가장 우선순위가 높은 데이터를 찾기 위해 걸리는 시간이 포함되어 선형적인 탐색 시간이 소요됩니다. O(N) 하지만 힙을 이용하면 삽입, 삭제 모두 O(logN)의 시간이 걸리게 되기 때문에 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동이랗고 이 경우 시간복잡도는 O(NlogN)으로 표현할 수 있습니다. 

 

 

힙 종류

힙에는 두 개의 종류가 있습니다.

 

• 최대힙(max heap)
  • 부모 노드의 값은 항상 자식 노드의 값보다 큰 이진 트리 
  • 힙은 항상 루트 노드 부터 제거되기 때문에 큰 값이 먼저 제거됨.
• 최소힙(min heap)
  • 부모 노드의 값이 항상 자식 노드의 값보다 작은 이진 트리 
  • 힙은 항상 루트 노드부터 제거되기 때문에 작은 값이 먼저 제거됨. 

 

힙 구성 절차

최소힙 기준으로

• 상향식
  • 자식 노드에서 부모 노드로 올라가며, 부모보다 자신의 값이 더 작은 경우에 위치를 교체하는 방식.
• 하향식
  • 부모 노드에서 자식 노드로 내려가며, 자신의 값이 자식보다 더 큰 경우에 위치를 교체하는 방식.

 

삽입

아래와 같은 최소힙에 1을 삽입하려고 한다면 다음과 같은 과정으로 인해 삽입됩니다.

 

 

 1. 힙은 완전 이진 트리의 일종이기 때문에 2를 9의 자식 노드로 연결합니다.

 

2. 2와 부모노드 9를 비교한 후 2가 더 작기 때문에 노드 값을 교체합니다.

 

3. 2와 부모노드 3과 비교한 후 2가 더 작기 때문에 교체합니다.

 

4. 삽입된 노드 2와 함께 최소힙 구성이 완료됩니다.

 

 

삭제

아래와 같은 힙이 있을 때 2를 삭제한다고 가정하면 다음과 같은 절차를 따릅니다.

1. 2를 제외하고 가장 마지막 노드인 9를 2자리에 올린다. 

 

2. 하향식 방식을 이용해서 자식노드들과 비교해가며 최소힙을 구성한다. 

 

 

삭제는 가장 우선순위가 높은 것이 빠져나간 후에 힙을 새로 구성하는 절차로 보시면 됩니다.

 

 

파이썬으로 함수 구현

 

import heapq   # 최소힙 구조로 동작이 기본 

def heapsort(nums):
    heap = []
    # heappush: heap에 모든 원소를 담음 
    for value in nums:
        heapq.heappush(heap, value)
        
    result = []
    # heappop: 힙에 삽입된 원소를 차례대로 꺼내기 
    for i in range(len(heap)):
        result.append(heapq.heappop(heap))
        
    return result

 

 

프로그래머스 더 맵게 문제 풀어보기