위로 sift, 아래로 sift: push, pop, build

"힙은 작은 동작 두 개로 자기를 유지해. 너무 작은 원소를 루트 쪽으로 띄우거나, 너무 큰 원소를 리프 쪽으로 가라앉히거나. 모든 힙 연산이 그 둘 중 하나를 O(log n)번 반복하는 것뿐이야."

Push: 끝에 추가하고 위로 sift

힙에 값을 넣으려면 이렇게 해. 새 값을 배열 끝에 떨어뜨리고, 그러니까 다음 리프 자리라 완전성이 유지되는 위치에 놓고 위로 sift하는 거야. 부모보다 작은 동안 자리를 바꿔가며 루트 쪽으로 올라가다가, 더 이상 부모보다 작지 않거나 꼭대기에 닿으면 멈춰. 올라가는 거리가 많아야 트리 높이니까 push는 O(log n)이야. 루트에서 리프까지 이어지는 경로 하나만 따라 힙 속성을 회복하고 나머지는 건드리지도 않아.

Pop: 교환하고, 줄이고, 아래로 sift

언제나 루트에 있는 최솟값을 꺼내려면 이래. 루트를 따로 저장하고, 마지막 원소를 루트 자리로 옮기고, 배열 길이를 하나 줄이고, 아래로 sift해. 더 작은 자식보다 크면 그 자식과 자리를 바꿔가며 리프 쪽으로 가라앉는 거야. 이것도 많아야 트리 높이니까 pop은 O(log n)이고. 빼지 않고 최솟값만 보는 건 인덱스 0을 읽기만 하면 되니까 O(1)이야. push와 pop은 서로 거울상이야. 하나는 위로 띄우고 하나는 아래로 가라앉히는데, 둘 다 경로 하나만 손보거든.

Push는 끝에 추가하고 위로 sift하는 거고 O(log n)이야. Pop은 루트를 가져오고 마지막 원소를 올린 다음 아래로 sift하는 거고 역시 O(log n)이고. Peek은 인덱스 0을 읽기만 하니 O(1)이야. 모든 힙 연산이 루트에서 리프로 이어지는 경로 하나를 따라 순서를 회복해.

놀라운 사실: 힙 만들기는 O(n log n)이 아니라 O(n)이야

순서 없는 배열을 힙으로 바꾸고 싶다고 하자. 원소를 하나씩 push하는 당연한 방법은 O(n log n)이야. 그런데 훨씬 아름답고 빠른 방법이 있어. 마지막 부모에서 시작해 루트 쪽으로 거슬러 올라가며 모든 노드를 아래로 sift하는 것. 이러면 유효한 힙이 O(n)에 만들어져. 선형로그가 아니라 선형이야. 직관은 이래. 노드 대부분이 바닥 근처에 있고, 리프가 트리의 절반이거든, 그런 노드는 sift-down 거리가 아주 짧아. 루트 근처의 소수만 멀리 내려가고. 그 거리를 전부 합하면 O(n log n)이 아니라 O(n)이 나와. 정말 놀라운 결과이고, 일을 하는 순서가 복잡도를 바꿀 수 있다는 걸 보여주는 사랑스러운 예시야. Python의 heapq.heapify가 정확히 이 방법을 써.

피파의 고백

나는 힙 만들기가 O(n log n)일 수밖에 없다고 확신했어. 삽입이 n번이고 각각 O(log n)이니 당연하잖아. 아빠가 아래에서 위로 sift-down하는 방식과 그게 O(n)인 이유를 보여줬는데, 합산 결과에 설득당하기까지 10분을 우겼어. 남은 교훈은 이거야. 내가 '당연하다'고 여긴 복잡도는 모든 노드에 최악의 경우를 매기고 있었어. 실제로는 대부분이 거의 안 움직이는 리프였는데 말이야. 비용 분석은 모든 단계가 비싸다고 가정하는 게 아니라 일이 어떻게 분포돼 있는지 보는 쪽에 보상을 줘.

Code

Push, pop, 그리고 O(n) build-heap·python

def sift_up(heap, i):
    while i > 0:
        p = (i - 1) // 2
        if heap[i] < heap[p]:           # 부모보다 작아? 올라가
            heap[i], heap[p] = heap[p], heap[i]
            i = p
        else:
            break

def push(heap, value):                  # O(log n)
    heap.append(value)                  # 끝에 추가 (다음 리프)
    sift_up(heap, len(heap) - 1)

def sift_down(heap, i):
    n = len(heap)
    while True:
        l, r, smallest = 2*i+1, 2*i+2, i
        if l < n and heap[l] < heap[smallest]: smallest = l
        if r < n and heap[r] < heap[smallest]: smallest = r
        if smallest == i: break
        heap[i], heap[smallest] = heap[smallest], heap[i]
        i = smallest

def pop_min(heap):                      # O(log n)
    heap[0], heap[-1] = heap[-1], heap[0]   # 루트랑 마지막 swap
    m = heap.pop()                          # 끝에서 옛 루트 제거
    if heap: sift_down(heap, 0)
    return m

def build_heap(arr):                    # O(n) — 놀람!
    for i in range(len(arr)//2 - 1, -1, -1):   # 마지막 부모 -> 루트
        sift_down(arr, i)
    return arr

h = []
for x in [5, 3, 8, 1, 9, 2]: push(h, x)
print("pops:", [pop_min(h) for _ in range(6)])   # [1, 2, 3, 5, 8, 9] 정렬됨!
print("O(n) build:", build_heap([5, 3, 8, 1, 9, 2]))  # 유효한 힙, 루트=최소

Exercise

최소 힙 [1, 4, 2, 8, 5]에서 시작해 값 3을 push해 봐. sift-up을 단계별로 따라가면서 3이 처음 어디에 놓이고 힙 속성이 회복될 때까지 어떤 교환이 일어나는지 적어. 그다음 push가 왜 O(n)이 아니라 O(log n)인지 말해.

Hint

3은 인덱스 5에 추가돼. 그 부모는 인덱스 2고 값이 2야. 3이 2보다 크니까 교환할 필요가 없어서 바로 멈춰. push가 O(log n)인 이유는 sift-up이 많아야 트리 높이만큼, 그러니까 루트에서 리프까지 경로 하나만 올라가고 배열 전체를 훑는 일은 절대 없기 때문이야.

Push: 끝에 추가하고 위로 sift

Pop: 교환하고, 줄이고, 아래로 sift

놀라운 사실: 힙 만들기는 O(n log n)이 아니라 O(n)이야

피파의 고백

Code

External links

Exercise

Progress

댓글 0