python - 힙 큐 (heapq)

정의

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리입니다.

이 구현에서는 모든 k에 대해 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다,

요소는 0부터 셉니다. 비교를 위해, 존재하지 않는 요소는 무한으로 간주합니다. 힙의 흥미로운 특성은 가장 작은 요소가 항상 루트인 heap[0]이라는 것입니다.

시각화

아래와 같이 a[k] <= a[2*k+1]와 a[k] <= a[2*k+2]가 유지되는 배열

                               0

              1                                 2

      3               4                5               6

  7       8       9       10      11      12      13      14

15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

heapify 

리스트 x를 선형 시간으로 제자리에서 힙으로 변환합니다.

import heapq

numbers = [8, 2, 1, 3, 5, 4, 7, 6]
heapq.heapify(numbers)

while numbers:
    print(heapq.heappop(numbers))

1
2
3
4
5
6
7
8

heappush

힙 불변성을 유지하면서, item 값을 heap으로 푸시합니다.

import heapq

h = []
heapq.heappush(h, 8)
heapq.heappush(h, 2)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
heapq.heappush(h, 5)
heapq.heappush(h, 4)
heapq.heappush(h, 7)
heapq.heappush(h, 6)

while h:
    print(heapq.heappop(h))

heappush

힙 불변성을 유지하면서, heap에서 가장 작은 항목을 팝하고 반환합니다

import heapq

h = []
heapq.heappush(h, (8, '딸기'))
heapq.heappush(h, (2, '수박'))
heapq.heappush(h, (1, '참외'))
heapq.heappush(h, (3, '바나나'))
heapq.heappush(h, (5, '쥬스'))
heapq.heappush(h, (4, '키위'))
heapq.heappush(h, (7, '망고'))
heapq.heappush(h, (6, '포도'))

while h:
    print(heapq.heappop(h))

(1, '참외')
(2, '수박')
(3, '바나나')
(4, '키위')
(5, '쥬스')
(6, '포도')
(7, '망고')
(8, '딸기')

최대 힙 (Max Heap)

-1을 곱해서 리스트로 만든다음 heapq로 만들어주고 꺼낼때는 반대로 -1를 곱해서 양수로 만들어주면 최대 힙이 구현이 된다.

import heapq

# -1을 곱해서 리스트로 만든다음 heapq로 만들어준다.
numbers = [8, 2, 1, 3, 5, 4, 7, 6]
h = [num * - 1 for num in numbers]
heapq.heapify(h)

while h:
    # 꺼낼때는 반대로 -1를 곱해서 양수로 만들어준다.
    print(heapq.heappop(h) * -1)