(Python/파이썬) 힙 자료구조, 힙큐(heapq)

최소 힙 : 부모 노드의 값이 자식 노드의 키값보다 항상 작은 힙

최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

이러한 속성을 이용하면, 힙에서는 가장 낮은(혹은 높은) 우선 순위를 가지는 노드가 항상 루트에 존재하게 된다. 이를 이용해서 우선 순위 큐와 같은 추상적인 자료형을 구현해낼 수 있다.

 

키 값의 대소관계는 부모/자식 간에만 성립하게 되고, 형제 노드 사이에는 대소 관계가 정해지지 않는다.

 

파이썬 힙 자료구조

파이썬 heapq 모듈은 heapq 우선 순위 큐 알고리즘을 제공한다.

인덱스 0에서 부터 시작해서 k번째 원소가 항상 자식 원소들 보다 작거나 같은 최소 힙의 형태로 정렬된다.

 

힙 함수 활용

• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
• heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (in linear time, O(N) )
• print(heap[0]) : 힙에서 최소값을 삭제하지 않고 단순히 읽기 위해서는 리스트의 첫번째 원소에 접근 하듯이 인덱스를 통해 접근 가능