[자료구조] heapq module

힙이란?

완전 이진 트리의 일종으로 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 자료구조이다.

• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.

라는 성질은 만족하며 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며,
특히 형제 사이에는 대소관계가 정해지지 않는다.

모듈 설정
import heapq
heapq의 경우 내장되어 있는 모듈이기 때문에 바로 import하여 사용할 수 있다.

 

힙 PUSH
list를 heap처럼 사용할 수 있게 하는 것으로 빈 리스트에 인자를 넣는 것으로 heap을 구현할 수 있다.

import heapq

#힙을 만들 빈 리스트 생성
heap = []

heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)

print(heap)

#결과 
#[1,2,3]

heapq.heappush( list_name , eleelement ) 를 이용하여 원하는 힙에 값을 삽입할 수 있다.

 

 

힙 POP

import heapq

#힙을 만들 빈 리스트 생성
heap = []

heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)


#min heap이기 때문에 가장 작은 1이 pop되어 나온다.
temp = heapq.heappop(heap)

print(temp)

#결과 : [1]

print(heap)

#결과 : [2,3]

heapq.heappop(list_name) 를 이용하여원하는 힙에서 root에 있는 값(최소값)을 가져올 수 있다.

POP을 하는 경우에는 root의 값이 삭제되고 다음 최소값이 root로 올라오기 때문에 heap[0]을 조회하는 것으로
최소값을 삭제하지 않고 가져올 수 있다.

 

이미 생성된 리스트를 힙으로 변경

import heapq

heap = [4, 1, 7, 3, 8, 5]
heapq.heapify(heap)
print(heap)

#결과 : [1, 3, 5, 4, 8, 7]

이미 값이 존재하는 리스트를 한번에 힙으로 변환 시키기 위해서는 
heapq.heapify(list_name) 를 이용하면 된다.

 

최대 힙 생성
heapq의 기본은 최소힙을 생성하기 때문에 최대 힙을 생성하기 위해서는 추가적인 작업이 필요하다. 

import heapq

heap = []


# 0번째는 정렬 기준
# 1번째는 값
heapq.heappush(heap, (-1, 1))
heapq.heappush(heap, (-2, 2))
heapq.heappush(heap, (-3, 3))





# 1번째에 들어 있는 것이 값이기 때문에 1번 항목을 조회한다.
while heap:
  print(heapq.heappop(heap)[1])



#결과 :
#3
#2
#1

heapq는 0번째 값을 기준으로 최소 힙을 설정하기 때문에 0번째에 있는 값을 조절하는 것으로
최대힙을 생성할 수 있다.