힙 자료구조의 구현에 대해 공부해보셨나요?
heapq는 리스트에 원소를 삽입할 때마다 전부 정렬해주는 것이 아닙니다. 대신 리스트의 제일 앞에 가장 작은 원소가 위치하는 것이 언제나 보장됩니다.
heapq는 나머지 원소들의 위치에 대해선 아무것도 보장해주지 않습니다. 이 원소들의 순서는 각각이 삽입된 순서에 따라서 매우 쉽게 바뀝니다.
삽입 및 삭제의 시간복잡도가 O(logN)인데 언제나 모든 원소가 정렬된 상태이길 원한다면 BBST(Balenced Binary Search Tree)를 사용해야 합니다. (C++에선 std::set, std::map이 그 역할을 해주지만 파이썬에선 통상적으로 어떻게 하는지 저는 모릅니다.)
passiontom 2년 전
제가 잘 이해가 안돼서 그러는데 heappush를 쓰면 리스트에 크기순으로 들어가야 한다고 알고 있습니다. 그런데 arr을 출력해보면 분명 heappush를 사용하였는데 리스트가 크기순이 아닙니다. 그 이유가 무엇인가요