[Python] 오류해결노트: heapq 자료구조 시 NoneType은 있으면 안 된다.

TypeError: '<' not supported between instances of 'int' and 'NoneType'

 

1. heapq는 O(log N)의 시간복잡도로 리스트 내 최솟값을 구할 수 있게 해주는 고마운 친구이다.

혹시 이 원리를 모르겠다면, 그리고 sort()랑 뭐가 다른지 모르겠다면,

min heap 자료구조를 공부하면 된다. 코드 외우지만 말고 반드시 공부하자.

import heapq

a = [3, 2, 1, 5, 9, 4, 7]

heapq.heapify(a)
heapq.heappop(a)	#1

단, 처음부터 heappush()로 구축한 게 아닌 이상 heapify()로 반드시 초기화 진행해야 함.

 

2. 심지어 원소가 int가 아니라 tuple, list여도 된다.

그래서 BFS에서 매우매우매우 유용하게 쓰인다.

import heapq

a = [(1, 30), (1, 20), (1, 10)]

heapq.heapify(a)
heapq.heappop(a)	#(1, 10)

import heapq

a = [[1, 30], [1, 20], [1, 10]]

heapq.heapify(a)
heapq.heappop(a)	#[1, 10]

 

 

3. 그런데 BFS의 queue에는 가끔 None값을 저장해야 할 때가 있다. (이러면 에러뜸)

뭐 이런 식으로...

queue = [(0, 0, r, c, board_, None)]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

while queue :
    succ_cnt, move_cnt, cx, cy, current_map, flip = heapq.heappop(queue)

 

이렇게 하며 이제 에러가 뜬다. 왜냐하면 None값의 크기를 비교할 수 없기 때문이다.

 

그러니까 사실 다 None이면 상관이 없는데,

import heapq

a = [[1, 30, None], [1, 20, None], [1, 10, None]]

heapq.heapify(a)
heapq.heappop(a)	#[1, 10, None]

 

그리고 사실 None을 비교하기 전에 이미 최솟값이 결정되어 있으면 상관이 없는데,

import heapq

a = [[1, 30, None], [1, 20, 1], [1, 10, None]]

heapq.heapify(a)
heapq.heappop(a)	#[1, 10, None]

 

다만 None값과 비-None 값을 비교해야 하면 에러가 뜨는 것이다!

import heapq

a = [[1, 30, None], [1, 10, 1], [1, 10, None]]

heapq.heapify(a)
heapq.heappop(a)

"""
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-19-89f9fba9a2e1> in <cell line: 5>()
      3 a = [[1, 30, None], [1, 10, 1], [1, 10, None]]
      4 
----> 5 heapq.heapify(a)
      6 heapq.heappop(a)

TypeError: '<' not supported between instances of 'int' and 'NoneType'
"""