[자료구조] 힙(Heap)

힙은 완전 이진 트리(complete binary tree)의 일종이며 partially ordered tree이고 우선순위 큐를 구현하기 위한 자료구조이다. 여러 개의 값들 중 최댓값이나 최솟값을 빠르게 찾아내는데 사용된다.

 

이진 트리(binary tree)는 트리 층에서 모든 노드가 최대 2개의 자식 노드를 가질 수 있는 구조를 말한다. 이진트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있다. 

 

complete tree는 왼쪽에서 오른쪽으로 채워져 있는 마지막 level을 제외한 tree의 모든 level이 완전히 채워져 있다.

complete tree

partially ordered tree는 각 내부 노드의 key가 하위 노드의 키보다 작거나(크거나) 같다. 따라서 제일 작은(큰) 값은 root에 위치해야 한다.

우선순위 큐

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

 

힙에는 최대힙과 최소힙 두 종류가 있다.

최대힙(max heap)

 - 부모 노드의 값은 항상 자식 노드의 값보다 큰 이진 트리 

 - 힙은 항상 루트 노드 부터 제거되기 때문에 큰 값이 먼저 제거됨.

최소힙(min heap)

 - 부모 노드의 값이 항상 자식 노드의 값보다 작은 이진 트리 

 - 힙은 항상 루트 노드부터 제거되기 때문에 작은 값이 먼저 제거됨. 

 

파이썬에는 heapq라는 min heap 라이브러리가 존재한다.

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

 

참고: https://ssung-22.tistory.com/30