파이썬 모듈 - heapq

힙큐

• Heapq 란, 우선순위 큐 를 의미한다. 최소값 부터 오름차순 으로 이루어진 큐

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리입니다.
이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다

출처 - https://python.flowdas.com/library/heapq.html

Heapq 모듈을 사용해서 heappush, heappop 을 이용하면 힙 불변성을 유지하며 메소드가 실행 된다.

1. heappop 을 이용하면, 맨 뒤엣 값이 빠져나가는 것이 아니라, 최솟값 이 힙에서 빠져나가고 최솟값 을 반환한다

2. heappush 를 이용하면 맨 뒤에 값이 들어가는 것이 아니라, 우선순위를 지키며 순서에 맞는 위치에 들어간다.
   (정렬 안정성을 보장하지는 않는다.)

3. heapify 리스트 를 선형시간 n 을 지키며, 제자리 힙으로 변형 시킨다.

우선순위큐를 이용해서 배열을 정렬 해보자!

>>> def heapsort(iterable):
...     heap = []
...     for value in iterable:
...         heappush(heap, value)
...     return [heapq.heappop(heap) for _ in range(len(heap))]

>>> heapsort([5, 2, 3, 4, 1])
#[1,2,3,4,5]