[파이썬] 힙큐(heapq) 이해하기
tree
힙큐 모듈은 이진 트리 기반의 자료구조이기 때문에 일단 트리를 이해해야 한다. 트리는 그래프와 함께 비선형 자료구조이고 루트 노드로부터 밑으로 가지를 뻗어나가는 형태를 하고 있다. _트리의 종류 중 이진 트리(binary tree)는 최대 2개까지만 자식 노드를 가질 수 있다. _(왼쪽 자식 노드, 오른쪽 자식 노드)
이진 트리 중 완전 이진 트리(complete binary tree)는 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워진다.
heap
힙은 기본적으로 완전 이진 트리를 기본으로 한 자료 구조이다. 일반적으로 배열로 구현되며, 파이썬의 경우에는 리스트이다.
힙에는 max heap과 min heap이 있는데, max heap(최대힙)은 부모 노드의 키값이 자식노드의 키값보다 항상 큰 힙이며, min heap(최소힙)은 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙이다.
heapq
파이썬의 힙큐 모듈은 완전 이진 트리 기반의 최소 힙 자료구조이다. 그러니까 루트노드는 heapq에서 가장 작은 값이다. 즉, 가장 작은 값을 알고 싶을 때에 heapq는 유용할 수 있다.
내가 궁금했던 점은 sort와의 차이였는데, 소트와 달리 힙큐는 전체를 정렬하는 것이 아니다. 힙큐는 가장 작은 값을 가지는 원소를 리스트의 맨 앞에 정렬한다.
heap 이라는 리스트가 있다고 하자. 힙큐 모듈을 이용하려면
heap = []
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
이런 식으로 heappush 메서드를 사용하여 heap에 푸시하거나,
heap = [4,3,2,1]
heapq.heapify(heap)
기존에 빈 리스트가 아닌 리스트를 heapq로 만드는 메서드(heapify)를 사용한다. 둘 다 리스트가 최소힙의 규칙을 만족시키도록 정렬해준다.
위에서 언급하였듯이, heapq는 모든 원소를 하나하나 정렬하는 것이 아니기 때문에, heap[0]이 해당 리스트의 최소값인 것은 확실하지만 heap[1]이 두번째로 작은 원소라고는 할 수 없다. 그러므로 두번째 작은 값을 얻고 싶다면 heap[1]이 아니라 heapq.heappop(heap)을 통해 가장 작은 원소를 삭제한 후, 그 다음에 heap[0]으로 접근해야 한다.