파이썬 힙큐(heapq)

2020년 05월 05일

파이썬의 힙큐는 min heap을 구현한 내장 모듈이고, heap은 완전 이진 트리의 일종이므로 완전 이진 트리 -> heap -> 파이썬 힙큐 순으로 설명.

완전 이진 트리와 포화 이진 트리

이진 트리란 자식 노드가 최대 2개로 구성된 트리를 말한다. (참고로 이진 탐색 트리BST에 대한 포스팅은 여기) 이진 트리의 종류 중 균형 트리인 완전 이진 트리 와 포화 이진 트리 가 있는데, 우선 포화 이진 트리란 꽉 찬 이진 트리라고 생각하면 된다.

포화 이진 트리: 모든 잎새 노드(leaf, 자식 노드가 없는 노드)의 레벨이 같으며, 잎이 아닌 모든 노드들의 자식은 2개이다.
완전 이진 트리는 포화 이진 트리에서 오른쪽에서부터 잎새 노드를 제거하여 얻어진 트리이다.

힙(Heap)

힙이란 완전 이진 트리의 일종인데 다음과 같은 특징을 갖는다.

우선순위 큐를 구현하는 데에 쓰인다.
힙은 최대값이나 최소값을 찾는 데 유용하다.
힙은 느슨한 정렬 상태이다. 부모 노드의 값이 자식 노드의 값보다 항상 크거나(Max heap) 작다(Min heap).
힙은 중복된 값을 허용한다. (이진 탐색 트리는 중복을 허용하지 않는다)

힙의 삽입과 삭제

새로운 노드를 삽입하려고 할 때 일단 마지막 번호 다음의 자리에 삽입한다. 일단 먼저 삽입을 한 다음에 부모 노드와의 대소 비교와 교환을 통해서 자기 자리를 찾아간다.

반면 힙에서 노드를 삭제하는 것은, 맥스힙의 경우에는 최댓값을 삭제하는 것을 의미하고 민힙의 경우에는 최소값을 삭제하는 것을 의미한다. 즉 루트 노드를 삭제하는 것이다. 루트 노드를 제거한 다음에는 가장 마지막 번호를 가진 노드를 루트 노드에 가져다 놓는다. 그 다음 자식 노드와의 대소 비교를 통해 교환을 하며 자기 자리를 찾아간다.

파이썬의 힙큐

파이썬에서는 내장 모듈인 heapq를 제공하여 쉽게 민힙을 쓸 수 있게 해준다. (맥스힙은 공식 지원하지 않는다) 모든 정렬이 필요 없고 최소값만 효율적으로 구하고 싶을 때 유용하다.

import heapq

h = []
heapq.heapify(h) # 기존에 존재하는 h라는 배열을 heap으로 만듦
heapq.heappush(h, i) # i라는 원소 힙에 삽입. O(logN) 소요.
heapq.heappop(h) # 가장 작은 값을 가진 루트 노드 리턴. O(logN) 소요.
h[0] # 삭제하지 않고 루트 노드의 값만 읽어 오기

전체 노드의 개수가 N일 때 완전 이진 트리의 높이는 logN이다. 그러므로 힙에서 삽입과 삭제에 걸리는 시간 효율성은 O(logN) 이라고 할 수 있다. 자기 자리를 찾아가는 과정에서 최대한의 교환이 일어나도 높이를 넘지는 못하기 때문이다.

Heap Sort

힙을 응용해서 sort를 할 수도 있다. 배열을 heapify한 다음, heappop 하면 최소값을 뽑아낼 수 있다. 그리고 새로운 배열에 저장한다. 최소값을 뽑아낸뒤 append하는 작업을 반복하면 오름차순의 정렬된 배열을 가질 수 있다. heapify 메서드를 사용하면 O(n) 시간이 걸린다고 알려져 있고, heappop이 n번 일어나므로(logn이 n번) 결론적으로 O(nlogn) 의 복잡도를 가지는 소트이다.

import heapq

def heapsort(h):
    heapq.heapify(h)
    sorted_arr = []
    while len(h) > 0:
        sorted_arr.append(heapq.heappop(h))
    return sorted_arr

Ref

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html