힙이란?
- 힙은 트리기반 자료구조이다.
- 파이썬에서 우선순위 큐를 사용할때 heapq 모듈을 통해 구현한다.(최소힙만 가능)
- 최소힙은 항상 부모가 자식보다 작다. 즉 추출은 항상 루트를 가져온다.
- 힙은 주로 배열로 구현 된다. 거의 완전한 트리(almost complete tree)이기에 부모나 자식의 접근을 인덱스로 효율적이게 가능하기 때문이다.
- 상하로만 관계있지, 좌우로는 관계 없다.
힙 vs 정렬
힙과 정렬의 차이로는 값의 삽입과 추출이 잦다면, 힙을 사용해 좀더 효율적으로 min or max를 유지할 수 있다. 반면 수정 삭제가 잦지 않다면 내장 라이브러리를 통한 sort를 사용하는게 더 직관적이고 용이하다.
힙의 활용 :
힙은 항상 균형을 유지하는 특성 때문에 다양한 분야에 널리 활용된다.
- 우선순위큐
- 다익스트라 알고리즘 (힙을 통해 O(V^2) 에서 O(ElogV)로 개선가능)
- 힙정렬
- 최소신장트리를 구현하는 Prim's Algoritm 등에도 활용
- 중앙값의 근사치를 빠르게 구하는데도 활용 (레벨의 중간노드를 추출하면 근사치로 가능)
Python을 통한 BinaryHeap 구현
class BinaryHeap(object) :
def __init__(self) :
self.items = [None]
def __len__(self) :
return len(self.items)-1
# 삽입 시 실행, 반복 구조 구현
def _percolate_up(self) :
i = len(self)
parent = i // 2
while parent > 0 :
if self.items[i] < self.items[parent] :
self.items[parent] , self.items[i] = \
self.items[i] , self.items[parent]
i = parent
parent = i // 2
def insert(self,k) :
self.items.append(k)
self._percolate_up()
# 추출시 실행, 재귀 구조 구현
def _percolate_down(self,idx) :
left = idx * 2
right = idx * 2 + 1
smallest = idx
if left <= len(self) and self.items[left] < self.items[smallest] :
smallest = left
if right <= len(self) and self.items[right] < self.items[smallest] :
smallest = right
if smallest != idx :
self.items[idx] , self.items[smallest] = \
self.items[smallest] , self.items[idx]
self._percolate_down(smallest)
def extract(self) :
extracted = self.items[1]
self.items[1] = self.items[len(self)]
self.items.pop()
self._percolate_down(1)
return extracted
특징 :
index 1은 비워둔다. (계산의 용이성)
시간복잡도 :
- 추출,삽입시 힙을 유지하기 위해 log(n)의 시간 복잡도를 가진다.
- 추출 후 힙을 유지할 필요가 없다면 추출은 O(1)만에 가능하다.
이진힙 vs 이진탐색트리(BST)
이름이 비슷해 헷갈릴 수도 있지만 이 둘은 엄연히 다른 개념이다.
가장 직관적인 차이점은 힙은 상하관계를 보장하고, BST는 좌우관계를 보장한다.
파이썬의 Priority Queue 와 heapq의 차이
파이썬에서 우선 순위 큐는 heapq 뿐만 아니라, queue 모듈의 PriorityQueue를 통해 구현 할 수 도있다. 왜 같은기능을 하는 라이브러리가 2개나 있을까 궁금해서 찾아 보았다.
결론부터 말하자면, 파이썬의 PriorityQueue 조차 내부적으로 heapq를 사용하도록 구현되어있다.
Cpython에서 PriorityQueue의 내부를 보면, 아래와 같다.
class PriorityQueue(queue) :
...
def _put(self,item) :
heappush(self.queue,item)
def _get(self) :
return heappop(self.queue)
그렇다면 둘의 차이점은 무엇일까?
차이점은 PriorityQueue는 스레드 세이프(멀티 스레드에서도 안전한 프로그래밍 개념 : 만약 스레드 세이프 하지 않다면, 1번 스레드에서 2번 스레드의 값을 바꿀 수 있다.) 하다는 점이다. heapq 모듈은 스레드 세이프를 보장하지 않는다.
그러나, 스레드 세이프 하다는 점은 Locking을 제공한다는 의미이고, 이는 오버헤드를 발생시킨다. 따라서 굳이 멀티 스레드로 구현할 게 아니라면 PriorityQueue를 사용하지 말자.
실무에서도 heapq로 우선순위 큐가 구현되고 있다고 한다.
참고자료 : '파이썬 알고리즘 인터뷰 - 박상길'
