[WEEK02] 힙

힙 (Heap)

[출처] https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap

 

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 우선순위 큐(Priority Queue)를 구현하는 자료구조다.

• 최대 힙(Max Heap): 부모 노드가 자식 노드보다 항상 크거나 같은 값을 가짐 → 최댓값을 빠르게 찾을 수 있음
• 최소 힙(Min Heap): 부모 노드가 자식 노드보다 항상 작거나 같은 값을 가짐 → 최솟값을 빠르게 찾을 수 있음

힙의 규칙

1. 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다. (레벨 순서로 노드를 삽입한다.)

[출처] https://wikidocs.net/194445

 

• 위 그림에서 (a)는 힙이지만, (b)는 왼쪽부터 채워야 한다는 규칙에서 벗어났기 때문에 힙이 아니다.

2. 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야 한다. 파이썬의 heapq 모듈은 최소 힙(min heap)이다. (최대 힙은 부모 노드가 자식 노드의 값보다 크거나 같다.)

[출처] https://wikidocs.net/194445

• (a)는 힙이지만, (b)는 부모 노드인 5가 자식 노드인 4보다 크기 때문에 힙이 아니다.

이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

 

이때 키 값의 대소 관계는 부모/자식 간에만 성립하고, 형제 노드 사이에는 대소 관계가 정해지지 않는다.

 

힙은 O(log n)의 시간 복잡도로 삽입과 삭제가 가능하기 때문에, 우선순위가 중요한 다양한 알고리즘에서 사용된다.

최소 힙 구현 (파이썬)

import heapq

def min_heap_example():
    heap = []
    heapq.heappush(heap, 3)
    heapq.heappush(heap, 1)
    heapq.heappush(heap, 4)
    heapq.heappush(heap, 2)
    
    print("최소 힙에서 원소를 순서대로 꺼내기:")
    while heap:
        print(heapq.heappop(heap), end=" ")  # 1 2 3 4

min_heap_example()

최대 힙 구현 (파이썬)

import heapq

def max_heap_example():
    heap = []
    heapq.heappush(heap, -3)
    heapq.heappush(heap, -1)
    heapq.heappush(heap, -4)
    heapq.heappush(heap, -2)
    
    print("최대 힙에서 원소를 순서대로 꺼내기:")
    while heap:
        print(-heapq.heappop(heap), end=" ")  # 4 3 2 1

max_heap_example()

---

힙큐 (Heapq)

파이썬 내장 모듈인 heapq는 우선순위 큐 알고리즘인 힙을 제공한다. 내부적으로 최소 힙의 형태로 정렬된다. 최대 힙을 구현하려면 값의 부호를 반전하여 사용한다.

• heapq.heappush(heap, item) : heap에 item을 추가
• heapq.heappop(heap) : heap에서 최솟값을 제거하고 반환
• heapq.heappushpop(heap, item) : item을 추가한 후 최솟값을 제거하고 반환
• heapq.heapify(iterable) : 기존 리스트를 힙으로 변환
• heapq.nlargest(n, iterable) : iterable에서 상위 n개의 큰 값을 반환
• heapq.nsmallest(n, iterable) : iterable에서 상위 n개의 작은 값을 반환