heapq

heapq.py 내의 설명

# 아래 숫자는 k를 의미하며, a[k]가 아니다
                                0
              1                                 2
      3               4                5               6
  7       8       9       10      11      12      13      14
15 16   17 18   19 20   21 22   23 24   25 26   27 28   29 30

external_merge_sort

heapq의 함수들

heapq.py의 heappush

def heappush(heap, item):
    """Push item onto heap, maintaining the heap invariant."""
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)

# `heap`: 모든 인덱스가 `startpos`보다 크거나 같은 heap
# `pos`: 정리되지 않은(out-of-order) 값을 가질 가능성 있는 리프 노드
# 힙의 invariant 복구
def _siftdown(heap, startpos, pos):
    newitem = heap[pos] # 새로운 항목은 heap.append()로 항상 끝에 추가된다
    # 끝에서 루트까지, 새로운 항목이 들어 맞는 위치를 찾을 때까지 부모를 찾아 간다
    while pos > startpos:
        # k는 2*k+1과 2*k+2의 부모
        # 즉, 0은 1,2, 1은 3,4, 2는 5,6의 부모로, 리프 노드에서 부모를 찾으려면
        # (자식 인덱스 - 1)을 1비트 우로 움직여서 2로 나눈다
        parentpos = (pos - 1) >> 1 
        parent = heap[parentpos]
        if newitem < parent: # 새로운 항목이 기존의 부모 값보다 작다?
            heap[pos] = parent # 부모 값을 자식 위치로 보내고
            pos = parentpos # 다음 위치를 부모 인덱스로 변경한다
            continue
        break
    heap[pos] = newitem

heappush(heap, 3)
# [3]
heappush(heap, 4)
# [3, 4]
heappush(heap, 5)
# [3, 4, 5]
heappush(heap, 6)
# [3, 4, 5, 6]
heappush(heap, 2)
# [3, 4, 5, 6, 2] heap 끝에 새로운 항목 추가
# [3, 4, 5, 6, 4] ((5-1)-1)/2=부모 위치=1. heap[1]=4. 4가 더 크므로 자식 위치로 보낸다. 2는 미정.
# [3, 3, 5, 6, 4] while문 돌아서 pos는 1, 부모는 0, a[0]=3 < 2이므로 a[1]=3으로 치환. 2는 미정.
# [2, 3, 5, 6, 4] while문 돌아서 pos는 0, 부모는 0, while문 종료, a[0]=2
""" 
      2
  3      5
6   4
"""
heappush(heap, 1)
# [2, 3, 5, 6, 4, 1]
# [2, 3, 5, 6, 4, 5]
# [2, 3, 2, 6, 4, 5]
# [1, 3, 2, 6, 4, 5]
"""
      1
  3       2
6   4   5 
"""