python 의 heapq 모듈에 대하여 잘못 알고 있었던 점으로 인해 문제를 푸는 과정에서 많은 시행착오를 겪었다. (프로그래머스 “운영 체제” 문제)
iterative 한 자료형을 heap 에 넣을 경우, 첫번째 원소에 대해서만 heapified 한 형태가 유지되고 두 번째 이후의 원소에 대해서는 그렇지 않은 것으로 알고 있었다. 하지만, 마치 정렬에서 여러 가지 기준으로 정렬할 경우 여러 기준에 순차적으로 정렬이 되듯이 heap 또한 첫번째 원소 기준에 중복되는 데이터가 여러 개 있다면 그 이후의 원소들에 대해서 순차적으로 정렬이 된다.

이러한 부분을 확실히 파악하는 것이 어려운 이유는 heapq 라는 모듈이 heap 을 구현하는 작동 방식을 철저히 분석하지 않고는 알 수 없기 때문이다. 이미 여러 번 heapq module docs 를 왔다갔다 했지만 이 부분을 파악하지 못한 이유는 해당 부분이 명시적으로 기술되어 있지 않기 때문이다. heapq module 의 실제 구현 코드를 보면 이 부분에 대해 “각 원소에 대해 순차적으로 순차적으로 비교하게 될 것이라는 점” 을 추론할 수 있을 것 같다. (혹은 직접 테스트 데이터를 넣어보거나)

모르는 것보다 잘못 알고 있는 지식이 가장 무섭다는 점을 문제 풀이를 통해서도 체감하게 된다. 확실하지 않은 부분을 최대한 구체적으로 생각하고 모르는 지식으로 분류하여 stereotype 을 깨는 것이 좋은 프로그래머가 되는 길이 아닌가 싶다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from heapq import heappush, heappop

a = [(1, 2), (2, 1), (2, 7), (2, 3), (1, 1), (1, 3)]
b = []

for item in a:
    heappush(b, item)
    
while b:
    print(heappop(b))
    
print('-------------------------')
a = [(1, 1, 2), (1, 1, 3), (1, 1, 1), (1, 1, 7)]
b = []

for item in a:
    heappush(b, item)
    
while b:
    print(heappop(b))

테스트 결과

아래와 같이 iterative 한 데이터에 대해서도 순차적으로 두번째, 세번째 원소에 대해 heapified 함이 보장됨을 확인할 수 있었다.