배열을 heap으로 만드는데 O(N)이면 충분하다

파이썬에서 주어진 리스트 배열 A를 heap으로 만드는 방법은 적어도 2가지가 있다. 첫번째는 빈 리스트를 만들고 heappush를 이용해서 하나씩 집어넣는 방법 A의 원소를 하나씩 순회해서 heappush하므로 O(NlogN)이다. 두번째 방법은 heapq에서 지원하는 heapify()를 사용하는 것이다. 집어넣기만 하면 주어진 배열을 바로 heap으로 만들어준다. 이 방법의 시간복잡도는... 놀랍게도 O(N)이다. 실제로 두 방법의 시간을 비교해보면.. import heapqimport randomimport time# 테스트할 데이터 크기 목록 (1만, 10만, 100만, 500만)data_sizes = [10000, 100000, 1000000, 5000000]print(f"{'Data Si..