힙큐 ( heapq )

안녕하세요 hp입니다 :)

오늘은 저번 포스팅에 연장선인 힙큐(heapq)에 대해서 배워보도록 하겠습니다.

📚 개념

힙큐는 이진 트리 기반의 최소 힙(min heap) 자료구조를 사용합니다.

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

키 값의 대소관계는 부모와 자식간에만 성립하고 형제 노드 사이에는 성립하지 않는다.

⭐️ 최소힙에 대한 간단한 설명 ( 5=>3=>2=>1=>4=>6=>7 순서로 삽입)

💡힙큐 메소드

• heapq.heappush(heap , item)
  item을 heap 리스트에 넣는다.
• heapq.heappop(heap) : heap에서 가장 작은 원소를 삭제하고 값을 반환합니다. ( 루트 노드의 값을 반환 )
• heapq.heapify(list) : list를 heap으로 변환시킨다.

heapq에 heappush()와 heappop()은 O(log n) heapify()는 O(n)의 시간복잡도를 가진다.

⚒️ heapq 모듈 사용하기

import heapq

heap = []

heapq.heappush(heap , 5)
heapq.heappush(heap , 3)
heapq.heappush(heap , 2)
heapq.heappush(heap , 1)
heapq.heappush(heap , 4)
heapq.heappush(heap , 6)
heapq.heappush(heap , 7)

print(heap) # [1,2,3,5,4,6,7]

⭐️ 위의 코드에서 heappop()을 이용해서 루트노드의 있는 값을 추출한다.

print(heapq.heappop(heap)) # 1
print(heapq.heappop(heap)) # 2
print(heapq.heappop(heap)) # 3
print(heapq.heappop(heap)) # 4
print(heapq.heappop(heap)) # 5
print(heapq.heappop(heap)) # 6
print(heapq.heappop(heap)) # 7

⭐️ heapify()를 통해 기존의 list를 heap으로 변경시킨다.

import heapq

example = [5,3,2,1,4,6,7]

heapq.heapify(example)

print(heapq.heappop(example)) # 1
print(heapq.heappop(example)) # 2
print(heapq.heappop(example)) # 3
print(heapq.heappop(example)) # 4
print(heapq.heappop(example)) # 5
print(heapq.heappop(example)) # 6
print(heapq.heappop(example)) # 7

⭐️ 최대힙 구현

파이썬에서는 최대힙을 나타낼때 heap을 이용하는데 item을 삽입할때 우선순위를 같이 삽입해야한다.

import heapq

heap = []

# 위와 같이 ( 5=>3=>2=>1=>4=>6=>7 순서로 삽입)
for i in range(7):
    item = int(input())
    heapq.heappush(heap , (-item , item))

print(heap) # [(-7, 7), (-4, 4), (-6, 6), (-1, 1), (-3, 3), (-2, 2), (-5, 5)]
print(heapq.heappop(heap)[1]) # 7
print(heapq.heappop(heap)[1]) # 6
print(heapq.heappop(heap)[1]) # 5
print(heapq.heappop(heap)[1]) # 4
print(heapq.heappop(heap)[1]) # 3
print(heapq.heappop(heap)[1]) # 2
print(heapq.heappop(heap)[1]) # 1

⭐️ heapq와 PriorityQueue의 속도 차이

PriorityQueue는 안전 클래스이고 스레드의 안전을 위한 잠금을 제공합니다. 이는 곧 반드시 확인 절차를 걸쳐야 함을 뜻합니다. heapq는 스레드의 안전을 보장하지 않고 또한 잠금 기능을 제공하지 않으며 스레드로부터 안전하지 않은 표준 list 객체에서 작동합니다. 그래서 잠금 오버헤드가 없는 heapq는 더 빨리 작동하게 됩니다.

끝까지 읽어주셔서 감사합니다. 😁

🎯 백준을 통한 문제 풀이

백준 1927번 최소힙 문제
백준 11279번 최대힙 문제

📌 참고

heapq와 priorityqueue의 차이