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

파이썬에서 주어진 리스트 배열 A를 heap으로 만드는 방법은 적어도 2가지가 있다.

 

첫번째는 빈 리스트를 만들고 heappush를 이용해서 하나씩 집어넣는 방법

 

A의 원소를 하나씩 순회해서 heappush하므로 O(NlogN)이다.

 

두번째 방법은 heapq에서 지원하는 heapify()를 사용하는 것이다.

 

집어넣기만 하면 주어진 배열을 바로 heap으로 만들어준다.

 

이 방법의 시간복잡도는... 놀랍게도 O(N)이다.

 

 

 

 

실제로 두 방법의 시간을 비교해보면..

 

import heapq
import random
import time

# 테스트할 데이터 크기 목록 (1만, 10만, 100만, 500만)
data_sizes = [10000, 100000, 1000000, 5000000]

print(f"{'Data Size (N)':>15} | {'heappush Loop (s)':>20} | {'heapify (s)':>15} | {'Speedup':>10}")
print("-" * 70)

for n in data_sizes:
    # 동일한 조건 비교를 위해 무작위 리스트 생성
    raw_data = [random.randint(1, 10000000) for _ in range(n)]

    # 1. heappush() 반복 사용 - O(N log N)
    data_copy1 = []
    start_time = time.perf_counter()
    for item in raw_data:
        heapq.heappush(data_copy1, item)
    heappush_time = time.perf_counter() - start_time

    # 2. heapify() 사용 - O(N)
    data_copy2 = raw_data.copy()
    start_time = time.perf_counter()
    heapq.heapify(data_copy2)
    heapify_time = time.perf_counter() - start_time

    # 속도 차이 계산 (배수)
    speedup = heappush_time / heapify_time if heapify_time > 0 else 0

    print(f"{n:>15,} | {heappush_time:>20.6f} | {heapify_time:>15.6f} | {speedup:>9.2f}x")

 

 

 

몇번 돌려보면 3~4배 정도로 유의미하게 차이가 난다

 

 

 

 

 

그러면 무슨 차이가 있는걸까?

 

heappush로 하나씩 넣는 과정은 빈 공간에서 하나씩 넣을때마다 넣은 원소는 맨 아래에서 맨 위에까지 비교하면서 자리를 찾아 올라온다.

 

그 트리 높이는 O(logN)이기 때문에 N개를 넣으면 O(NlogN)

 

 

heapify는 이미 배열인 상태에서 시작한다.

 

참고로 배열은 원소의 크기와 상관없이 완전 이진트리로 생각할 수 있다.

 

 

 

그러면 heapify는 이 완전 이진트리를 min heap으로 바꿔주는 과정을 적용한다.

 

부모 노드가 자식 노드보다 작아야한다.

 

위에 있는 노드부터 아래에 있는 노드랑 비교해서 min heap 조건을 만족하도록 자리 바꾸기를 적용함.

 

여기서 핵심은 대부분의 원소는 leaf쪽에 배치되어있고, 일부 원소가 위쪽에 배치되어 있다는 것.

 

즉, 대부분의 원소는 그 아래쪽에 자식 노드가 별로 없다보니, 비교 연산을 별로 하지 않는다.

 

하나씩 heappush할때는 n개의 모든 원소가 O(logN)의 연산을 하지만, 위의 경우는 원소마다 연산 횟수가 차이난다.

 

그리고 이때 실제 연산 횟수 합을 계산하면 수학적으로 O(N)임을 증명할 수 있다고함