[heapq] 파이썬 최소힙 pop()에서 최솟값이 안나올 때

문제

힙은 heapq를 사용하여 구현하는데 pop()을 했을 때, 최솟값이 나오지 않는 현상이 발생했다.

2차원에서는 2차원의 1번째 원소 값을 비교하여 최소값을 결정한다.

disk [[3, 0]]
[3, 0]

disk [[8, 1], [4, 2]]
[8, 1]

disk [[4, 2]]
[4, 2]

2번째 disk에서는 [4, 2]가 나와야하는데 [8, 1]이 나왔다.

이는 disk에 list 형태로 값을 넣어줘야해서 heapq 모듈의 push()가 아닌 list의 + 연산자를 사용했기 때문이다.

 

list 연산자를 사용한 순간 list로 취급된다.

---

해결

heapq.heapify(disk)

list 연산후에 다시 heap으로 바꿨다.