[Algorithm] 이진 최소 힙 (heapq)

1. 이진최소힙 개념

2. 삽입과 삭제 과정

3. 각 경우의 시간복잡도 정리

---

개념

완전이진트리 형태의 힙이며, 각 노드가 부모 <= 자식을 만족 (루트 = 최솟값)

보통 배열로 구현 (인덱스 i의 왼/오 자식 : 2i, 2i+1)

* python의 heapq 모듈은 이진 최소 힙을 기반으로 동작함

 

삽입 과정

def insert_min_heap(heap, value):
        heap.append(value)
        idx = len(heap) - 1
        while idx > 0 and heap[(idx-1)//2] > heap[idx]:
            heap[idx], heap[(idx-1)//2] = heap[(idx-1)//2], heap[idx]
            idx = (idx-1)//2
        
heap = []
values = [10, 7, 11, 5, 4, 13]
for value in values:
        insert_min_heap(heap, value)
        print(f'Inserted {value} into the min-heap: {heap}')

Inserted 10 into the min-heap: 10 
Inserted 7 into the min-heap: 7 10 
Inserted 11 into the min-heap: 7 10 11 
Inserted 5 into the min-heap: 5 7 11 10 
Inserted 4 into the min-heap: 4 5 11 10 7 
Inser...

• 시간 복잡도 : O(log(n))
• 공간 복잡도 : O(n)

 

삭제 과정

def delete_min_heap(heap, value):
        idx = -1
        for i in range(len(heap)):
            if heap[i] == value:
                idx = i
                break
        if idx == -1:
            return
    
    heap[idx] = heap[-1]
    heap.pop()
    while True:
    	left_child = 2 * idx + 1
        right_child = 2 * idx + 2
        smallest = idx
        if left_child < len(heap) and heap[left_child] < heap[smallest]:
        	smallest = left_child
        if right_child < len(heap) and heap[right_child] < heap[smallest]:
        	smallest = right_child
        if smallest != idx:
        	heap[idx], heap[smallest] = heap[smallest], heap[idx]
            idx = smallest
        else:
        	break
            
heap = []
values = [13, 16, 31, 41, 51, 100]
for value in values:
	insert_min_heap(heap, value)
    
delete_min_heap(heap, 13)

• 시간 복잡도 : O(log n)
• 공간 복잡도 : O(n)

시간복잡도

연산	설명	시간복잡도	비고
삽입 (Insert)	마지막에 원소 추가 후 sift-up	O(log n)	트리 높이만큼 비교/교환
최솟값 삭제 (Delete-Min)	루트 삭제 후 마지막 원소를 루트로 올리고 sift-down	O(log n)	항상 높이만큼 내려감
최솟값 조회 (Get-Min)	루트(heap[0]) 확인	O(1)	배열 인덱스 접근
임의 원소 삭제	해당 원소를 찾은 뒤 재정렬	O(n)	위치 탐색이 O(n)
힙 만들기 (Heapify)	배열을 힙으로 변환	O(n)	bottom-up 방식
힙 정렬 (Heap Sort)	모든 원소를 하나씩 pop하여 정렬	O(n log n)	안정정렬 아님